Reconsider the Southwestern Airways crew scheduling problem presented in Section 7.4. Because of a blizzard in the Chicago area, all the flights into and out of Chicago (including flights 4, 6, 7, and 9 in Table 7.5 ) have been canceled for the time being, so a new crew scheduling plan needs to be developed to cover the seven remaining flights in Table 7.5 .
TABLE 7.5: Data for the Southwestern Airways Problem

The 12 feasible sequences of flights still are the ones shown in Table 7.5 after deleting the canceled flights. When flights into and out of Chicago had originally been part of a sequence, a crew now would fly as passengers on a Southwestern Airways flight to the next city in the sequence to cover the remaining flights in the sequence. For example, flight sequence 4 now would be San Francisco to Los Angeles to Denver to San Francisco, where a crew would fly as passengers on a flight from Los Angeles to Denver (not shown in the table) to enable serving as the crew from Denver to San Francisco. (Since the original sequence 5 included a roundtrip from Denver to Chicago and back, a crew assigned to this sequence now would simply layover in Denver to await the flight from Denver to San Francisco.) The cost of assigning a crew to any sequence still would be the same as shown in the bottom row of Table 7.5.
The objective still is to minimize the total cost of the crew assignments that cover all the flights. The fact that only 7 flights

Now need to be covered instead of 11 increases the chance that fewer than three crews will need to be assigned to a flight sequence this time. (The flights where these crews fly as passengers do not need to be covered since they already are assigned to crews that are not based in San Francisco.)
a. Formulate a BIP model in algebraic form for this problem.
b. Formulate and solve this problem on a spreadsheet?

Feasible Sequence of Flights 5 6 Flight 3 4 10 11 12 1. San Francisco to Los Angeles (SFO-LAX) 2. San Francisco to Denver (SFO-DEN) San Francisco to Seattle (SFO-SEA) Los Angeles to Chicago (LAX-ORD) Los Angeles to San Francisco (LAX-SFO) 3. 1 4. 5. 6. Chicago to Denver (ORD-DEN) 7. Chicago to Seattle (ORD-SEA) 8. Denver to San Francisco (DEN-SFO) 9. Denver to Chicago (DEN-ORD) 10. Seattle to San Francisco (SEA-SFO) 11. Seattle to Los Angeles (SEA-LAX) 3. 3. 4 4 Cost, $1,000s 2. 4. 2. Fire Station in Tract Average Frequency of Medical Emergencies per Day 2 3 4 5 times (min.) to a medical emergency Response 20 15 4 25 15 25 10 25 15 12 2. 12 30 20 15 20 15 10 3 15 in tract 12 25 10