Scheduling Interrelated Activities

Scheduling Interrelated Activities

We all schedule interrelated activities in our everyday lives, even if it is just scheduling when to begin our various homework assignments. So too, managers must schedule var- ious kinds of interrelated activities. When should we begin production for various new or- ders? When should we begin marketing various new products? When should we make various capital investments to expand our production capacity?

For any such activity, the decision about when to begin can be expressed in terms of a series of yes-or-no decisions, with one of these decisions for each of the possible time periods in which to begin, as shown below.

Should a certain activity begin in a certain time period?

Since a particular activity can begin in only one time period, the choice of the various time periods provides a group of mutually exclusive alternatives, so the decision variable for only one time period can have a value of 1.

Selected Reference A4 describes how Swedish municipalities use large BIP models of this type to plan staff scheduling and routing of 4,000 home care workers to attend to the needs of the elderly. Replacing manual planning by BIP has resulted in annual savings in the range of $30 million to $45 million while also improving the quality of the home care.

Airline Applications

The airline industry is an especially heavy user of OR throughout its operations. Many hundreds of OR professionals now work in this area. Major airline companies typically have a large in-house department that works on OR applications. In addition, there are some prominent consulting firms that focus solely on the problems of companies involved with transportation, including especially airlines. We will mention here just two of the applications which specifically use BIP.

One is the fleet assignment problem. Given several different types of airplanes avail- able, the problem is to assign a specific type to each flight leg in the schedule so as to maximize the total profit from meeting the schedule. The basic trade-off is that if the air- line uses an airplane that is too small on a particular flight leg, it will leave potential customers behind, while if it uses an airplane that is too large, it will suffer the greater expense of the larger airplane to fly empty seats.

An Application Vignette

Netherlands Railways (Nederlandse Spoorwegen Reizigers) is the main Dutch railway operator of passenger trains. In this densely populated country, about 5,500 passenger trains currently transport approximately 1.1 million passengers on an average workday. The company’s operating revenues are approximately 1.5 billion Euros (approximately $2 billion) per year.

The amount of passenger transport on the Dutch rail- way network has steadily increased over the years, so a national study in 2002 concluded that three major infra- structure extensions should be undertaken. As a result, a new national timetable for the Dutch railway system, specifying the planned departure and arrival times of every train at every station, would need to be developed. Therefore, the management of Netherlands Railways directed that an extensive operations research study should be conducted over the next few years to develop an optimal overall plan for both the new timetable and the usage of the available resources (rolling-stock units and train crews) for meeting this timetable. A task force con- sisting of several members of the company’s Department of Logistics and several prominent OR scholars from European universities or a software company was formed to conduct this study.

The new timetable was launched in December 2006, along with a new system for scheduling the allocation of rolling-stock units (various kinds of passenger cars and other train units) to the trains meeting this timetable. A new system also was implemented for scheduling the assign- ment of crews (with a driver and a number of conductors in each crew) to the trains. Binary integer programming and related techniques were used to do all of this. For example, the BIP model used for crew scheduling closely resembles (except for its vastly larger size) the one shown in this section for the Southwestern Airlines problem.

This application of operations research immediately resulted in an additional annual profit of approximately $60 million for the company and this additional profit is expected to increase to $105 million annually in the coming years. These dramatic results led to Netherlands Railways winning the prestigious First Prize in the 2008 international competition for the Franz Edelman Award for Achievement in Operations Research and the Management Sciences.

Source: L. Kroon, D. Huisman, E. Abbink, P.-J. Fioole, M. Fischetti, G. Maróti, A. Schrijver, A. Steenbeck, and R. Ybema, “The New Dutch Timetable: The OR Revolution,” Interfaces, 39(1): 6–17, Jan.–Feb. 2009. (A link to this article is provided on our website, www.mhhe.com/hillier.)

For each combination of an airplane type and a flight leg, we have the following yes-or-no decision.

Should a certain type of airplane be assigned to a certain flight leg?

Prior to its merger with Northwest Airlines, completed in 2010, Delta Air Lines flew over 2,500 domestic flight legs every day, using about 450 airplanes of 10 different types. As described in Selected Reference A11, they have used a huge integer programming model (about 40,000 functional constraints, 20,000 binary variables, and 40,000 general integer variables) to solve their fleet assignment problem each time a change is needed. This ap- plication has saved Delta approximately $100 million per year.

A fairly similar application is the crew scheduling problem. Here, rather than assigning airplane types to flight legs, we are instead assigning sequences of flight legs to crews of pilots and flight attendants. Thus, for each feasible sequence of flight legs that leaves from a crew base and returns to the same base, the following yes-or-no decision must be made.

Should a certain sequence of flight legs be assigned to a crew?

The objective is to minimize the total cost of providing crews that cover each flight leg in the schedule.

A full-fledged formulation example of this type will be presented at the end of Sec. 12.4.

A related problem for airline companies is that their crew schedules occasionally need to be revised quickly when flight delays or cancellations occur because of inclement weather, aircraft mechanical problems, or crew unavailability. As described in an application vignette in Sec. 2.2 (as well as in Selected Reference A12), Continental Air- lines (now merged with United Airlines) achieved savings of $40 million in the first year of using an elaborate decision support system based on BIP for optimizing the reassign- ment of crews to flights when such emergencies occur.

Many of the problems that face airline companies also arise in other segments of the transportation industry. Therefore, some of the airline applications of OR are being ex- tended to these other segments, including extensive use now by the railroad industry. For example, the second application vignette in this section describes how Netherlands Rail- ways won a prestigious award for its applications of operations research, including inte- ger programming and constraint programming (the subject of Sec. 12.9), throughout its operations.