THE LARGEST FLEET in the industry: 270 Boeing 737s. Almost 3000 pilots, 4500 flight attendants, and 2400 daily departures. Changing market demand and competition. Not to mention FAA and union regulations: maximum trip length 4 days, maximum flying time 8 hours, minimum time between connecting flights 40 minutes. And, at most, one aircraft change.

And this does not even begin to take into account another important variable: What routes do the pilots and flight attendants prefer, and for how long -- and where are they dead set against flying?

Now take all this and construct a schedule, pairing a sequence of flights to appropriate crews, starting and ending at the crew's home base. And since the second largest operating cost of an airline is the cost of a flight crew, make sure it's the most economical solution possible, and one which will still keep everyone happy -- the FAA, the unions, the crew members, and the shareholders. Oh, and did we tell you we need that done ASAP?

FOR SOUTHWEST AIRLINES, having a team of six to eight people sequestered for three to four weeks to produce a monthly "crew pairing" was no longer good enough. Especially since rapidly shifting market dynamics and new aircraft deliveries were demanding new schedules almost faster than they could be produced. Enter a team of experts from IBM Research, Global Services, Travel and Transportation Industry Solutions, RS/6000, and business partners from Sabre Decision Technologies. Drawing on their experience making Crew Pairing Optimization Systems (CPOS) work for other airlines, the IBM team was able to deliver a solution that now can generate daily, weekend, and transition pairing solutions in a fraction of the time they used to take. Additionally, aircraft downtime has been reduced, as have flight costs and crew work hours. But the most important benefit, according to Al Davis, vice president of special projects for Southwest, has been "improving the quality of life for airline crews and schedulers."

So how'd the IBM team perform the magic? First, using the domain knowledge built up over years of working with airline customers, the team was able to identify key elements of the problem and identify where efficiency increases were most needed. Then, IBM researchers with expertise in mathematical algorithms looked for novel ways of optimizing solutions to the problem -- no easy task, given the quadrillion possible permutations involved. As published in a 1998 paper entitled "Column Generation and the Airline Crew Pairing Problem," the researchers used something known as the so-called "Volume Algorithm" as well as other innovations to reach very good solutions to these large problems.

By running the solutions on the super-fast RS/6000 397 and 595 servers, Southwest has not only reduced the time to solve these problems from three to four weeks to a few days, but the airline also can now "fine-tune" solutions, instead of accepting the first solution found because of time constraints.

For IBM researchers, there is ongoing work in handling another nuisance to airlines, the so-called "schedule repair problem" -- or what to do when the schedule you've just completed is blown apart by an unexpected hurricane, for instance.