The Scheduler That Never Converged

Hard

· Backend

Incident

SEV-1

BUG-SWA1222

Priority: Critical · reported by crew ops

Time to fix: 35 min

Failing checks on the shipped build

  • a failed run returns a valid schedule, not a partial one

    a non-converged run must not emit a conflicting schedule: expected 0 but got 6

How to work this incident

  1. Read the report: write down the expected behaviour and the actual one in a sentence each.
  2. Reproduce it: run the visible tests and find the failing check that matches the report.
  3. Read the logs and the failing checks for the first value that is wrong — the earliest wrong value is nearer the cause than the loudest error.
  4. Follow the request through the handler, the validation and the service it calls; find the first step whose output disagrees with the report.
  5. Fix the cause rather than the symptom, run the visible tests again, and submit against the hidden ones — then write the root cause down.

Inspired by

Southwest Airlines · 2022

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.

Code map

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 };
};

Sign in to edit the file, run the tests and submit a fix

A free account — no card, no trial clock. You come straight back here.

The Scheduler That Never Converged — JavaScript Bug Hunt

Modelled on the Southwest Airlines meltdown (December 2022): a storm produced far more crew reassignments than the scheduling system could resolve.

  • Language: JavaScript
  • Layer: Backend
  • Difficulty: Hard
  • Concepts: Optimisation, Fallbacks
  • Modelled on: Southwest Airlines · 2022
  • Visible tests: a clean schedule converges immediately; a solvable conflict is resolved; a failed run returns a valid schedule, not a partial one
  • Reward: 50 XP for a complete fix

Incident

  • Severity: SEV-1 (priority: Critical)
  • Ticket: BUG-SWA1222
  • Reported by: crew ops
  • Time to fix: 35 minutes, the target for a hard incident

Failing checks on the shipped build

  • a failed run returns a valid schedule, not a partial one — a non-converged run must not emit a conflicting schedule: expected 0 but got 6

How to work this incident

  1. Read the report: write down the expected behaviour and the actual one in a sentence each.
  2. Reproduce it: run the visible tests and find the failing check that matches the report.
  3. Read the logs and the failing checks for the first value that is wrong — the earliest wrong value is nearer the cause than the loudest error.
  4. Follow the request through the handler, the validation and the service it calls; find the first step whose output disagrees with the report.
  5. Fix the cause rather than the symptom, run the visible tests again, and submit against the hidden ones — then write the root cause down.

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.

Open the hunt to start the incident clock, edit the files, run the visible tests and submit against the hidden ones, then write the root cause down. More JavaScript bug hunts.