Flight Crew Scheduling
Last year I waited six hours for a return flight to San Francisco. The departure board pushed the time four times before the airline cancelled outright. The inbound aircraft arrived late, and the crew operating it had exceeded their legal duty hours. No replacement crew available. I got home eventually, but the experience stuck with me. After writing about graph-based satellite scheduling, I wondered whether the same approach could prevent this kind of failure. Build better crew schedules, and flights stop cancelling for staffing reasons. That saves airlines real money — in rebookings, hotel vouchers, and the quieter cost of passengers who stop choosing you.
The scheduling problem has clear inputs. Flights carry a route, time window, aircraft type, and minimum crew count. Crew members carry certifications, availability windows, a current location, and regulatory limits — maximum flight hours and duty hours per duty period, with mandatory rest between periods. The goal: assign crew to flights so every departure has sufficient staff, no one exceeds their limits, and rest periods prevent the kind of cascading timeout that cancelled my flight. Industry solves this with mixed integer programming and column generation — thousands of variables, hours of compute. I wanted to see how far a graph could go. Flights as nodes, valid connections as edges, one filtered subgraph per crew member. The structure mirrors the satellite scheduling work: find the longest feasible path through a DAG under accumulating constraints.
The implementation uses F# — my primary language for optimization work — with QuikGraph for graph construction. QuikGraph handles adjacency lists, topological sorting, and edge filtering, which kept the focus on scheduling logic rather than graph plumbing.
Inputs
Two CSV files define the problem. Flights cover a 20-day window — long enough for crew to plan personal lives around their availability, long enough for the airline to spot staffing gaps before they become gate-side cancellations:
flight_id,departure_airport,arrival_airport,departure_time,arrival_time,aircraft_type,min_crew
FL0001,JFK,LAX,2026-01-20T06:05,2026-01-20T09:35,B737,5
FL0002,JFK,LAX,2026-01-20T13:49,2026-01-20T17:19,A320,6
...
Six hubs (JFK, LAX, ORD, DEN, SFO, SEA), two aircraft types, 980 flights. The min_crew column varies by aircraft and route — five for a domestic B737, up to seven for an overnight A320.
Crew members appear once per availability window — a person with three work blocks produces three rows:
crew_id,name,home_base,current_location,aircraft_certs,available_start,available_end,max_flight_hours,max_duty_hours
C0001,Alice,SFO,SFO,B737,2026-01-20T05:00,2026-01-24T23:00,10,14
C0001,Alice,SFO,SFO,B737,2026-01-27T06:00,2026-01-31T22:00,10,14
C0001,Alice,SFO,SFO,B737,2026-02-03T05:00,2026-02-08T21:00,10,14
...
Two hundred crew with varying certifications (B737, A320, or both), home bases proportional to hub traffic, and current locations that may differ from home base — simulating mid-rotation crew. These numbers are arbitrary; a real carrier would have thousands of crew and different fleet compositions. The point is to test the algorithm's structure, not match production scale.
The crew CSV represents a point-in-time snapshot. Producing it in practice requires its own pipeline. Crew submit availability windows ahead of the planning cycle — the 20-day horizon gives them lead time. Current location updates as crew complete flights, which means the schedule itself modifies future inputs. Gate check-ins, sick calls, and reassignments all trigger updates to the underlying data. An operational system would need an ingestion layer — collecting availability submissions, tracking real-time position through flight completion events, reconciling changes against the published schedule — before the graph ever sees the data. That pipeline is beyond this article's scope, but it's where much of the operational complexity lives. The scheduler assumes clean inputs which is a separate discipline.
One further simplification: this experiment treats all crew as interchangeable within their certification. Pilots and cabin crew follow different regulatory frameworks and would need separate scheduling passes. The graph supports this — run the same algorithm with different constraint sets — but the sample data doesn't distinguish the two.
Graph Construction
The master graph connects every flight pair where a physical transition is possible:
fsharp
let canConnect (a: Flight) (b: Flight) =
a.ArrivalAirport = b.DepartureAirport
&& b.DepartureTime >= a.ArrivalTime.AddMinutes(minConnectionMinutes)
Same airport, at least 60 minutes between arrival and departure. For 980 flights this produces around 79,000 edges. Build it once — individual crew graphs derive from it by filtering.
Construction checks every flight pair, so it scales quadratically. At 980 flights that's under a second. At 6,000 flights — a major carrier's daily volume — the pair count hits 36 million. Manageable for a planning tool that builds the graph once per scheduling cycle. For tighter time horizons, partitioning by hub cluster or time block keeps the graph tractable.
Each crew member sees only flights matching their certifications and availability:
fsharp
let isFeasible (crew: CrewMember) (flight: Flight) =
crew.AircraftCerts.Contains(flight.AircraftType)
&& crew.Windows |> List.exists (fun w ->
flight.DepartureTime >= w.Start && flight.ArrivalTime <= w.End)
A B737-only pilot never sees A320 flights. Someone off-duty Jan 25-26 never sees those days. The subgraph encodes individual constraints implicitly.
Schedule Generation
The graph is a DAG — time flows forward — so longest-path is tractable via dynamic programming. Each crew member gets a DP pass over their filtered subgraph. The traversal carries state:
fsharp
type TraversalState = {
CurrentFlight: string
FlightHours: float
DutyHours: float
DutyPeriods: int
Path: string list
}
Short connections (under 12 hours) accumulate flight and duty hours within a duty period. Long gaps trigger a rest period — accumulators reset, a new duty period begins. Transitions that would exceed limits get pruned. The path maximizing flight coverage wins.
Starting points constrain to the crew member's current location — not necessarily home base, since they may be mid-rotation or repositioned after a disruption.
The rest-aware traversal addresses timeouts directly. Every crew path includes sufficient rest between duty periods. No path dead-ends at a remote airport with a crew member near hour 13 of a 14-hour limit. The schedule never sets up the failure that cancelled my flight — a crew arriving at their limit with no valid continuation.
Coordination
Individual schedules are straightforward. The hard part: flights need full crews. A B737 needs five; an overnight A320 needs seven.
Before any assignment, the algorithm analyzes contention — how many crew can feasibly cover each flight:
fsharp
let analyze (crewFeasible: (CrewMember * Set) array) =
crewFeasible
|> Array.collect (fun (crew, flights) ->
flights |> Set.toArray |> Array.map (fun fid -> (fid, crew.CrewId)))
|> Array.groupBy fst
|> Array.map (fun (fid, pairs) ->
{ FlightId = fid
CrewCount = pairs.Length
CrewIds = pairs |> Array.map snd |> Array.toList })
|> Array.sortBy _.CrewCount
Flights with one or two possible crew are critical — assign those first or risk leaving them unstaffed. Flights coverable by dozens of crew are flexible. This sorting drives the assignment order: most constrained crew get scheduled first, claiming scarce flights before flexible crew absorb them.
The assignment loop tracks a coverage map — how many crew are assigned to each flight against its requirement. A flight stays in the pool until it reaches min_crew. Each iteration builds a fresh subgraph for the next crew member, excluding only fully-staffed flights. The DP algorithm runs on this reduced graph, and the resulting path updates the coverage map.
The assignment is greedy. Each crew member gets the best available path when they're processed. Flights aren't exclusive — multiple crew share them until the minimum staffing requirement is met. Once a flight reaches full crew, it drops from subsequent subgraphs. That removal can break routing options for crew processed later, forcing them into shorter or less efficient paths. Ordering by most constrained first reduces this effect — crew with fewer options get first pick, while crew with many options can absorb the loss of a routing node. Changing the processing order is trivial; the sort key could be seniority, base proximity, or cost instead of constraint count. What's less trivial: changing which path a crew member selects. The program currently maximizes coverage (most flights per crew member). A weighted function during traversal — factoring in deadhead cost, positioning value, or crew preference — would change path selection itself, not just processing order. That's a meaningful extension to be considered.
Output
Individual schedules show each crew member's itinerary with connection types — short turnarounds in minutes, rest breaks in hours:
--- Alice (C0001, starts at SFO, B737) ---
FL0037 SFO -> LAX Jan 20 07:40 - 09:10 (B737)
FL0015 LAX -> SFO Jan 20 10:56 - 12:26 (B737) [conn 106m]
FL0086 SFO -> LAX Jan 21 07:16 - 08:46 (B737) [REST 18.8h]
FL0064 LAX -> SFO Jan 21 10:53 - 12:23 (B737) [conn 127m]
FL0135 SFO -> LAX Jan 22 07:25 - 08:55 (B737) [REST 19.0h]
FL0113 LAX -> SFO Jan 22 11:08 - 12:38 (B737) [conn 133m]
FL0286 SFO -> SEA Jan 25 11:04 - 13:04 (B737) [REST 70.4h]
FL0290 SEA -> LAX Jan 25 15:48 - 18:18 (B737) [conn 164m]
FL0308 LAX -> DEN Jan 26 08:35 - 11:05 (B737) [REST 14.3h]
FL0322 DEN -> JFK Jan 26 15:06 - 18:36 (B737) [conn 241m]
...
FL0870 SFO -> LAX Feb 06 07:39 - 09:09 (B737) [REST 17.6h]
FL0848 LAX -> SFO Feb 06 11:05 - 12:35 (B737) [conn 116m]
>> 28 flights, 14 duty periods
Duty periods emerge from the rest threshold — no explicit period modeling required. Longer gaps like the 70.4-hour break in Alice's schedule reflect her availability windows — days off between work blocks, not idle time.
Flight assignments show staffing levels against requirements:
FL0001 JFK -> LAX Jan 20 06:05 [4/5] Beth, Kyle3, Zara, Irene3
FL0002 JFK -> LAX Jan 20 13:49 [6/6] Henry1, Wendy3, Fiona2, ...
FL0005 JFK -> DEN Jan 20 07:50 [5/5] Karen1, Yuri2, Vera2, ...
...
FL0174 DEN -> JFK Jan 23 07:10 [0/5] UNSTAFFED
Coverage across the full schedule:
Fully staffed: 772 / 980 flights (78.8%)
Partially staffed: 179 flights
Unstaffed: 29 flights
Staffing Gaps
The unstaffed flights follow a clear pattern:
FL0174 DEN -> JFK Jan 23 07:10 [0/5]
FL0176 DEN -> LAX Jan 23 07:48 [0/6]
FL0181 DEN -> SEA Jan 23 11:27 [0/5]
FL0182 SFO -> JFK Jan 23 06:03 [0/5]
FL0203 JFK -> SFO Jan 24 16:53 [0/5]
FL0207 LAX -> JFK Jan 24 19:47 [0/7]
FL0208 LAX -> ORD Jan 24 06:58 [0/5]
FL0223 DEN -> JFK Jan 24 06:48 [0/5]
FL0231 SFO -> JFK Jan 24 06:03 [0/5]
FL0239 SEA -> JFK Jan 24 06:24 [0/5]
FL0276 DEN -> ORD Jan 25 09:15 [0/5]
FL0278 DEN -> SFO Jan 25 10:05 [0/6]
FL0279 DEN -> SEA Jan 25 11:16 [0/5]
FL0288 SEA -> JFK Jan 25 06:24 [0/5]
FL0337 SEA -> JFK Jan 26 06:28 [0/5]
FL0427 SFO -> JFK Jan 28 06:11 [0/5]
FL0475 DEN -> SEA Jan 29 11:34 [0/5]
FL0484 SEA -> JFK Jan 29 06:18 [0/5]
FL0525 SFO -> JFK Jan 30 05:53 [0/5]
FL0533 SEA -> JFK Jan 30 06:16 [0/5]
FL0573 DEN -> SEA Jan 31 11:26 [0/5]
FL0720 DEN -> SEA Feb 03 11:18 [0/5]
FL0769 DEN -> SEA Feb 04 11:35 [0/5]
FL0818 DEN -> SEA Feb 05 11:16 [0/5]
FL0819 SFO -> JFK Feb 05 05:52 [0/5]
FL0862 DEN -> LAX Feb 06 07:46 [0/6]
FL0916 DEN -> SEA Feb 07 11:35 [0/5]
FL0942 LAX -> JFK Feb 08 19:54 [0/7]
FL0962 DEN -> ORD Feb 08 09:38 [0/5]
DEN and SEA departures dominate — the DEN→SEA midday slot and early morning eastbound flights in particular. These hubs carry less traffic than JFK or LAX, so fewer crew are based there. The 179 partially staffed flights follow a similar distribution, most sitting one or two crew short.
These gaps reflect staffing levels, not algorithm limits. With 200 crew covering 980 flights at 5-7 crew each, the math is tight. A real carrier would staff proportionally higher, and these gaps would close. The flights that remain unstaffed are candidates for cancellation, consolidation, or repositioned crew — operational decisions outside the scheduler's scope.
Performance
The graph separates two concerns: structure and scheduling. The master graph captures all valid flight connections. Individual crew schedules and coordination run on top of it. This separation is where the performance story lives.
When something changes — a flight cancels, a crew member calls in sick, weather delays cascade — the master graph needs a small patch: remove a few vertices, add or drop edges at the boundary. The structure survives. Rerun affected crew subgraphs, re-coordinate, done. Contrast this with MIP, where any input change means reformulating constraints and resolving the entire model.
Individual crew runs are independent DP passes over separate subgraphs. They parallelize trivially — spread 200 crew across available cores and the wall-clock time divides accordingly. Coordination requires the computed output from all individual runs, so it stays sequential, but the expensive work distributes cleanly.
A full rebuild — reconstructing the master graph from scratch — is the fallback for major disruptions or when patches accumulate past the point of usefulness. For a 20-day horizon, rolling the window forward carries over 90% of existing edges. But full rebuilds aren't the normal operating mode. They're the recovery option when surgical patching isn't enough.
Conclusion
This started as a thought experiment: could graph techniques transfer to crew management. I think it can: The core model (flights as nodes, connections as edges, constraint-aware traversal) produces workable schedules; rest periods emerge from gap detection; and crew coordination works through contention analysis and greedy assignment. Every generated path guarantees sufficient rest between duty periods — the kind of schedule that would have prevented the timeout that stranded me in that departure lounge.
Production use would need refinement. The traversal needs tighter checks around cumulative limits — weekly and monthly caps that FAR 117 mandates beyond per-duty-period limits. Pilot scheduling must run separately from cabin crew, each with distinct regulatory constraints. The upstream data pipeline — collecting availability, tracking crew position, reconciling changes — is a system in its own right. And the greedy assignment, while fast, leaves room for a global optimizer to improve coverage and cost.
The exercise proved the core idea. A graph encodes scheduling constraints structurally — through edges and subgraphs — rather than as hundreds of inequality constraints in a solver. Individual crew schedules parallelize trivially. The master graph persists across changes, absorbing patches without full reconstruction. That combination — structural encoding, parallelism, incremental updates — is worth exploring further.
Data: flights.csv | crew_members.csv | output.txt