We developed a two-phase algorithm for solving Delta Air Lines' bidline-gen
eration problem: assigning trips (tasks) to monthly schedules for crew memb
ers (called bidlines.) The system must produce bidlines that conform to all
rules, and it should maximize average total value and the quality of the b
idlines as measured by their purity. The first phase of the algorithm (the
purity phase) constructs as many high-quality lines as possible, and the se
cond (the GA phase) completes the assignments by constructing high-total-va
lue valid lines from the remaining open trips. Delta obtains significant sa
vings in staffing by using this algorithm. The bidlines produced are of com
parable quality to those built with the semiautomatic process that Delta Ai
r Lines used before.