The Scheduler That Never Converged — JavaScript Bug Hunt

Briefing

Modelled on the Southwest Airlines meltdown (December 2022): a storm produced far more crew reassignments than the scheduling system could resolve. The solver could not converge, staff fell back to phoning crews individually, and nearly 17,000 flights were cancelled.

scheduler.js iterates until it converges — and returns whatever half-finished state it happens to hold if it does not.

Fix solveSchedule so a run that fails to converge reports failure and returns the last known-good assignment instead of a partial one.

Bug report

BUG-SWA1222 · Priority: Critical · Reported by: crew ops

solveSchedule(assignments, maxIterations) must return { converged, schedule }:

• it repeatedly resolves conflicts; a schedule is valid when no crew is double-booked
• if it converges within maxIterations, return { converged: true, schedule }
• if it does not, return { converged: false, schedule: <the last VALID state> }, never a partially rewritten one

Observed: on a hard input the loop exhausts its budget and hands back a schedule with crews double-booked, which downstream systems then act on.

Logs

[crew] solver exhausted 500 iterations; emitted schedule with 214 conflicts
[crew] 16700 flights cancelled

The code as shipped

src/crew/scheduler.js (editable)

function conflicts(schedule) {
  var seen = {};
  var n = 0;
  for (var i = 0; i < schedule.length; i++) {
    var key = schedule[i].crew + "@" + schedule[i].slot;
    if (seen[key]) n++;
    seen[key] = true;
  }
  return n;
}
exports.conflicts = conflicts;

exports.solveSchedule = function (assignments, maxIterations) {
  var schedule = assignments.slice();
  for (var it = 0; it < maxIterations; it++) {
    if (conflicts(schedule) === 0) return { converged: true, schedule: schedule };
    // Nudge one conflicting assignment into the next slot and try again.
    for (var i = 0; i < schedule.length; i++) {
      var key = schedule[i].crew + "@" + schedule[i].slot;
      var dup = false;
      for (var j = 0; j < i; j++) {
        if (schedule[j].crew + "@" + schedule[j].slot === key) dup = true;
      }
      if (dup) {
        schedule[i] = { crew: schedule[i].crew, slot: schedule[i].slot + 1 };
        break;
      }
    }
  }
  return { converged: false, schedule: schedule };
};

Read-only context: src/crew/SAFETY.js.