OR in Aerospace and Crew Scheduling

From WFM Labs

OR in Aerospace and Crew Scheduling examines the airline crew scheduling problem — the application domain that drove many of the OR innovations now used in workforce management. Column generation was developed for airline crew pairing. Branch-and-price was refined for crew rostering. Disruption management for Irregular Operations (IROPS) pioneered real-time re-optimization under uncertainty. The parallels between airline crew scheduling and contact center workforce scheduling are not analogies — they are the same mathematical structures with different vocabulary.

Overview

Airline crew pairing parallels contact center shift generation

Airlines face a scheduling problem of extraordinary complexity. A major carrier operates 3,000+ daily flights across hundreds of airports. Each flight requires a specific crew complement (captain, first officer, flight attendants). Crews must satisfy FAA duty-time regulations, contractual work rules, qualification requirements, and rest provisions. The crew cost is the second-largest operating expense after fuel.

The airline solved this problem decades before contact centers reached comparable mathematical maturity — and the methods they developed are directly applicable to WFM. This page maps the airline OR toolkit to WFM, explains why the mathematical structures are shared, and argues that WFM practitioners should study airline scheduling as a source of proven methods.

Mathematical Foundation

The Airline Scheduling Pipeline

Airlines decompose their scheduling problem into sequential stages:

  1. Schedule design: Which routes to fly, at what times (market-driven, months in advance).
  2. Fleet assignment: Which aircraft type flies each route (driven by demand and range).
  3. Crew pairing: Construct legal sequences of flights (pairings) that crews can operate.
  4. Crew rostering: Assign pairings to individual crew members over a monthly bid period.
  5. Disruption management: Re-optimize in real time when things break (weather, mechanical, crew illness).

Stages 3–5 are the OR problems most directly parallel to WFM.

Crew Pairing

A pairing is a sequence of flights starting and ending at a crew base, spanning 1–4 days, satisfying all duty-time regulations. The problem: select a set of pairings that covers every flight exactly once at minimum cost.

Set covering/partitioning formulation:

Let j index pairings and i index flights. Let aij=1 if pairing j covers flight i, and cj = cost of pairing j.

min⁡∑jcjxj

subject to:

∑jaijxj=1∀i(every flight covered exactly once)
xj∈{0,1}∀j

This is a set partitioning problem. The number of feasible pairings is enormous — millions or billions for a large carrier. Enumerating them all is impossible.

Column Generation for Crew Pairing

Column generation (Desrosiers et al., 1984) solves this by generating pairings on-the-fly rather than enumerating upfront:

  1. Restricted master problem (RMP): Start with a small set of feasible pairings. Solve the LP relaxation.
  2. Pricing subproblem: Use dual prices from the RMP to identify pairings with negative reduced cost — pairings that would improve the solution if added. This is a constrained shortest path problem through a time-space network, solvable by dynamic programming.
  3. Add columns: Add promising pairings to the RMP and re-solve.
  4. Iterate until no improving pairings exist.
  5. Integrality: Branch-and-price combines column generation with branch-and-bound to obtain integer solutions.

This is the same method used in advanced WFM Schedule Optimization via Column Generation in Scheduling. In WFM, "pairings" become "individual agent schedules" (sequences of shifts across a planning horizon), and "flights" become "intervals requiring coverage."

Crew Rostering

Crew rostering assigns the generated pairings to individual crew members over a monthly period. Each crew member has preferences, qualifications, seniority-based bidding rights, and accumulated duty time.

Formulation: Another set partitioning problem, but now rows are pairings (each must be assigned to exactly one crew member) and columns are monthly lines (complete month-long schedules for one crew member). Constraints include:

  • Maximum monthly flying hours (FAA limits, typically 80–100 hours)
  • Minimum days off per month
  • Vacation periods, training blocks, medical leave
  • Seniority-based preference satisfaction

The WFM parallel: rostering is to the airline what roster generation is to the contact center. Lines of work must be assembled from shifts, assigned to agents, and must satisfy contractual constraints, preference satisfaction, and fairness requirements.

Duty-Time Regulations

FAA (and EASA in Europe) regulations impose complex constraints:

  • Flight duty period: Maximum hours from report time to block-in (varies by start time and number of legs)
  • Rest requirements: Minimum 10 consecutive hours between duty periods, including an 8-hour sleep opportunity
  • Cumulative limits: 100 flight hours in 28 days, 1,000 in 365 days
  • Fatigue risk management: Some carriers use biomathematical fatigue models to supplement regulatory limits

These parallel WFM labor constraints:

Airline Constraint WFM Parallel
Maximum flight duty period Maximum shift length
Minimum rest between duties Minimum rest between shifts (11 hours in EU Working Time Directive)
Cumulative flight hours per 28 days Maximum weekly/monthly hours
Reduced duty limits for early starts Predictive scheduling law constraints on clopening shifts
Augmented crew for long flights Overtime/extended shift regulations

Disruption Management (IROPS)

When a flight is delayed or cancelled — due to weather, mechanical issues, or crew unavailability — the airline must re-optimize in real time. This is Irregular Operations (IROPS), and it is the airline equivalent of intraday management in WFM.

The IROPS problem: Given the current state (delayed flights, stranded crews, maintenance issues), find a new feasible assignment of crews to flights that minimizes total disruption cost (passenger delays, cancellations, crew repositioning, hotel costs).

Methods:

  • Re-optimization: Re-solve the crew pairing/rostering problem from the current state. Computationally expensive but produces the best solution.
  • Displacement chains: Fix most assignments and propagate changes through a chain of affected crew-flight pairs. Faster but potentially suboptimal.
  • Look-ahead policies: Anticipate future disruptions when making current recovery decisions. Uses stochastic programming or scenario-based optimization.

WFM Parallels

The structural parallels between airline crew scheduling and contact center WFM are exact:

Airline Concept WFM Equivalent Mathematical Structure
Crew pairing Shift pattern generation Set covering / partitioning
Crew rostering Schedule generation + assignment Set partitioning with preferences
Flight coverage Interval coverage Constraint satisfaction
Duty-time regulations Labor law and contractual rules Constraint set in optimization
Seniority bidding Schedule preference bidding Mechanism design (see Game Theory and Incentive Design in WFM)
Crew base Agent home site or virtual team Network node
Deadheading (repositioning) Cross-site virtual routing Network flow
IROPS Intraday management Real-time re-optimization
Fuel cost Labor cost Objective function coefficient
Aircraft swap Agent skill swap / queue reassignment Recourse decision

Crew Pairing ↔ Shift Generation

In airlines, a pairing is a legal sequence of flights. In WFM, a shift is a legal sequence of work intervals, breaks, and activities. Both must satisfy regulatory constraints (duty limits ↔ shift length limits), rest requirements, and coverage obligations.

Column generation generates pairings by solving a shortest-path subproblem through a time-space network. The same method generates WFM shifts: nodes are time points, arcs represent work intervals and breaks, and constraints are encoded as arc restrictions. The dynamic programming pricing in the airline subproblem is identical in structure to the DP pricing in the WFM subproblem — both seek the lowest-reduced-cost column (pairing/shift) in a resource-constrained network.

Seniority Bidding ↔ Schedule Bidding

Airlines use seniority-based preferential bidding — senior pilots get first pick of lines. This is mechanism design (see Game Theory and Incentive Design in WFM). The airline industry has extensive experience with:

  • Truthful bidding: Does the system incentivize honest preference reporting? PBS (Preferential Bidding System) designs vary in truthfulness.
  • Fairness vs. seniority: Pure seniority creates extreme inequality. Some carriers use hybrid systems with minimum quality guarantees for junior crew.
  • Computational bidding: Pilots submit ranked preferences; an optimization algorithm assigns lines to maximize aggregate preference satisfaction subject to coverage constraints.

These are exactly the problems WFM faces with shift bidding systems. The airline solution — decades of refinement in mechanism design — provides proven approaches.

IROPS ↔ Intraday Management

When plans break, the re-optimization challenge is identical:

Airline: A thunderstorm at O'Hare delays 40 flights. Crew connections are broken. Some crews will time out on duty limits. The airline must: cancel some flights, delay others, reposition crews, and communicate changes — all in real time.

WFM: A network outage spikes call volume 200% above forecast. 15 agents called out sick. The contact center must: activate overtime, recall agents from training, adjust routing priorities, extend shifts, and offer overtime — all in real time.

Both are real-time re-optimization under uncertainty: the current state is known, the future state is stochastic, and decisions must be made with incomplete information. The mathematical frameworks — rolling horizon optimization, displacement chains, scenario-based stochastic programming — transfer directly.

Worked Example: Crew Pairing as WFM Shift Generation

Setup (airline): A small carrier has a crew base at Airport A. Three flights need coverage:

  • Flight 101: A→B, departs 6:00, arrives 8:00
  • Flight 202: B→C, departs 9:00, arrives 11:00
  • Flight 303: C→A, departs 12:00, arrives 14:00

Duty rules: Maximum 12-hour duty period. Minimum 1-hour connection time. Crew must start and end at base A.

Feasible pairings:

  • Pairing 1: {101, 202, 303} — 3-leg day trip. Report 5:00, release 14:30. Duty = 9.5 hrs. Cost: $900.
  • Pairing 2: {101} + overnight at B + return deadhead next day. Cost: $700 + $200 hotel + $300 deadhead = $1,200.
  • Pairing 3: {202, 303} — need a deadhead A→B first. Cost: $600 + $300 deadhead = $900.
  • Pairing 4: {303} — need deadhead A→B→C. Cost: $300 + $600 deadhead = $900.

Optimal solution: Pairing 1 covers all three flights with one crew at $900. Any decomposition into smaller pairings costs more.

WFM translation: Replace flights with intervals, airports with skills/queues, and duty rules with shift constraints:

  • "Flight 101 (A→B, 6–8)" becomes "Work Queue A, 6:00–8:00"
  • "Flight 202 (B→C, 9–11)" becomes "Work Queue B, 9:00–11:00"
  • "Flight 303 (C→A, 12–14)" becomes "Work Queue A, 12:00–14:00"

The optimal "shift" is a single split-skill shift: 6:00–14:00 covering Queue A, then B, then A again. Just as the airline pairing chains flights through airports, the WFM shift chains intervals through queues.

Why WFM Practitioners Should Study Airline OR

  1. Proven at scale. Airlines solve crew scheduling for 3,000+ daily flights with thousands of crew members. WFM problems at 500 agents are smaller — the methods are more than sufficient.
  2. Column generation is the same algorithm. The pricing subproblem (constrained shortest path via DP) is identical in structure for crew pairing and shift generation.
  3. Disruption management is mature. Airlines have decades of experience with real-time re-optimization. WFM intraday management can adopt these methods directly.
  4. Bidding system design is solved. Airlines have experimented extensively with seniority bidding, preferential bidding, and hybrid systems. WFM shift bidding can learn from this experience.
  5. Regulatory constraint modeling is transferable. FAA duty-time rules are as complex as labor law. The constraint modeling techniques transfer directly.
  6. The literature is deep. Airline OR is one of the best-documented applied OR domains, with textbooks, survey papers, and case studies spanning 40 years.

Maturity Model Position

Awareness of airline OR parallels maps to the WFM Labs Maturity Model:

  • Level 2 (Established): Awareness that scheduling is an optimization problem with constraint structures similar to other industries.
  • Level 3 (Advanced): Use of column generation (the airline method) for shift pattern generation. Explicit modeling of labor constraints using techniques from airline duty-time constraint modeling.
  • Level 4 (Optimized): Real-time re-optimization using airline IROPS techniques for intraday management. Formal bid system design informed by airline PBS experience.
  • Level 5 (Autonomous): Integrated planning pipeline modeled on the airline scheduling pipeline (schedule design → fleet/skill assignment → shift generation → rostering → disruption management), with autonomous re-optimization at each stage.

See Also

References

  • Barnhart, C. et al. "Branch-and-Price: Column Generation for Solving Huge Integer Programs." Operations Research 46(3), 1998. — The foundational paper on branch-and-price for airline crew scheduling.
  • Desrosiers, J. et al. "Methods for Routing with Time Windows." Les Cahiers du GERAD, 1984. — Column generation for vehicle routing and crew scheduling.
  • Belobaba, P., Odoni, A., and Barnhart, C. (eds.) The Global Airline Industry, 2nd ed. Wiley, 2015. — Comprehensive coverage of airline OR.
  • Clausen, J. et al. "Disruption Management in the Airline Industry." Computers & Operations Research 37(5), 2010.
  • Hillier, F.S. and Lieberman, G.J. Introduction to Operations Research, 11th ed. McGraw-Hill, 2021.
  • Koole, G. Call Center Optimization. MG Books, 2013. — Column generation applied to contact center scheduling.
  • Gamache, M. et al. "A Column Generation Approach for Large-Scale Aircrew Rostering Problems." Operations Research 47(2), 1999.
Retrieved from "https://wiki.wfmlabs.org/w/index.php?title=OR_in_Aerospace_and_Crew_Scheduling&oldid=1986"