Scheduling Interrelated Activities

By -
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?

INTRODUCTION TO OPERATIONS RESEARCH-0100

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?

INTRODUCTION TO OPERATIONS RESEARCH-0101

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.

Comments

Post a Comment

Popular posts from this blog

DUALITY THEORY:THE ESSENCE OF DUALITY THEORY

By -
Image
THE ESSENCE OF DUALITY THEORY Given our standard form for the primal problem at the left (perhaps after conversion from another form), its dual problem has the form shown to the right. Thus, with the primal problem in maximizatio n form, the dual problem is in minimization form instead. Furthermore, the dual problem uses exactly the same pa r amete r s as the primal problem, but in different locations, as summarized below. 1. The coefficients in the objective function of the primal problem are the right-hand sides of the functional constraints in the dual problem. 2. The right-hand sides of the functional constraints in the primal problem are the coef- ficients in the objective function of the dual problem. 3. The coefficients of a variable in the functional constraints of the primal problem are the coefficients in a functional constraint of the dual problem. To highlight the comparison, now look at these same two problems in matrix notation (as introduced at the beginn...
Read more

NETWORK OPTIMIZATION MODELS:THE MINIMUM SPANNING TREE PROBLEM

By -
Image
THE MINIMUM SPANNING TREE PROBLEM The minimum spanning tree problem bears some similarities to the main version of the shortest-path problem presented in the preceding section. In both cases, an undi r ecte d and connected network is being considered, where the given information includes some mea- sure of the positive length (distance, cost, time, etc.) associated with each link. Both problems also involve choosing a set of links that have the shortest total length among all sets of links that satisfy a certain property. For the shortest-path problem, this property is that the chosen links must provide a path between the origin and the destination. For the minimum spanning tree problem, the required property is that the chosen links must provide a path between ea c h pair of nodes. The minimum spanning tree problem can be summarized as follows: 1. You are given the nodes of a network but not the links. Instead, you are given the po- tential links and the positive length for each ...
Read more

INTEGER PROGRAMMING:THE BRANCH-AND-CUT APPROACH TO SOLVING BIP PROBLEMS

By -
TH E BRANCH-AND-CUT APPROACH TO SOLVING BIP PROBLEMS Integer programming has been an especially exciting area of OR since the mid-1980s be- cause of the dramatic progress being made in its solution methodology. Background To place this progress into perspective, consider the historical background. One big break- through had come in the 1960s and early 1970s with the development and refinement of the branch-and-bound approach. But then the state of the art seemed to hit a plateau. Rel- atively small problems (well under 100 variables) could be solved very efficiently, but even a modest increase in problem size might cause an explosion in computation time be- yond feasible limits. Little progress was being made in overcoming this exponential growth in computation time as the problem size was increased. Many important problems arising in practice could not be solved. Then came the next breakthrough in the mid-1980s, with the introduction of the b r an c h- and-cu t approach to sol...
Read more