Stalking the perfect schedule

As head of IBM's

Optimization Center, Brenda Dietrich spends her days solving some

of the hardest problems known to mathematics. Optimization problems-questions

of how best to allocate resources to tasks-come in many guises,

from managing workflow in a factory to setting rates for overnight

delivery services. The difficulty of the problem depends on how

the tasks consume resources.

Optimization

problems get especially hairy when the answer must be expressed

as an integer-that is, when a fractional answer, such as 'half a

worker' or 'two-thirds of a widget', doesn't make sense. Solving

such 'integer programming' problems often requires listing all possible

arrangements. Outwardly similar arrangements can have radically

different outcomes-which may be so numerous that they exceed the

number of particles in the universe. Much of the Deep Computing

that goes on in the Optimization Center is devoted to obviating

the need to list most of the possible solutions.

A classic integer

programming problem that Dietrich's group works on is matching airline

crews with flights. 'Crew pairing', as the exercise is known, can

entail a complex tour of cities, taking into account union rules,

FAA regulations on how long pilots must sleep and the need to give

crew members time to get from one flight to another. Most important,

these schedules must cost the airlines as little overtime as possible,

since pilots' salaries are the biggest expenditure an airline can

control.

Dietrich's group

recently solved the largest pairing problem in history. Southwest

Airlines is not the biggest carrier in the world, but because its

fleet consists entirely of 737s, an unusally large pool of crew

members are qualified for duty on a single type of plane. The human-generated

solutions were good enough, but the scheduler was working at the

limits of human ability. As the airline grew, however, the monthly

schedule took more than a month to compile.

Using standard

linear programming techniques on the Southwest problem would have

taken hundreds of hours, far too long to make practical decisions.

So Ranga Anbil, Manager, Network Logistics and Francisco Barahona,

a researcher in Dietrich's group, came up with an approximate solution

they call the volume algorithm. "It doesn't get the exact answer,"

Anbil explains, "but it gets close enough that you can use

it to jump-start the more standard linear programming algorithms.

And that speedup was enough to allow us to solve the Southwest problem

in reasonable time." When the airline hired IBM it was not

looking to save money, only to generate timely schedules.

Using the new

system it did both, saving millions in crew costs.



Unfortunately, the Southwest solution is not directly transferable
to other airlines. "The reason for that lies at the heart of

Deep Computing," says Avi Harpaz, a researcher at IBM's Haifa

Research Laboratory who has developed a crew-pairing program for

Israel's El Al airlines. "Because these kinds of problems are

so difficult, you must hand-tune each one to get an optimum solution."

By using Haifa's

trip-planning and crew-scheduling algorithms, El Al has been able

to save 4 to 5% of its variable costs, such as overtime, crew transport

and hotel expenses. And the benefits flow through the entire organization,

Harpaz points out. As the airlines gain a better understanding of

the problem, they can experiment with 'what if' scenarios. At the

same time, the human experts can devote time to fine-tuning the

schedules produced by the program and to handling issues that are

not reflected in the set of rules used by the algorithms.

Another group

at Haifa has been working on personnel scheduling for call centers.

The goal is to maintain a uniform level of service, but the peaks

in call volume are not always predictable. Moreover, the workers

have to be scheduled by shift rather than by peak call volumes.

The solution,

which started with the requirements that 90% of the calls be answered

within 30 seconds, has several components, says team leader David

Bernstein. First, the frequency of calls is calculated from historical

data. Based on the length of an average call and factors such as

the length of breaks, the number of people needed for each period

is computed. Then, taking into account the number of hours a person

could work, the solution finds an optimal number of shifts. Finally,

people are assigned to shifts, a step that reflects individual constraints

such as child care and outside classes. Thanks to the scheduling

system, staff utilization is up 5% and the weekly planning process-which

formerly took two or three days of an expert's time-now takes two

or three hours and can be done by a nonspecialist.

So what makes

optimization a Deep Computing problem? For Dietrich, a problem must

pass two tests-"Is it hard? And is it important? I want to

be working on important hard problems. Problems that have the potential

to change the way business is done."