SmallTime Airlines: A Set Partitioning Problem

Page 131

You are managing operations for SmallTime Airlines, a small regional airline in Western Canada. You operate 12 flights per day. You have identified 11 possible "duty plans" (possible daily work schedules) for your pilots, as follows:

Flights Covered
Duty Plan / Cost / 101 / 102 / 103 / 201 / 202 / 203 / 401 / 402 / 403 / 501 / 502 / 503
1 / $ 382 / 1 / -- / -- / -- / -- / 1 / -- / 1 / -- / -- / -- / --
2 / $ 378 / -- / -- / 1 / -- / 1 / -- / 1 / -- / 1 / -- / -- / --
3 / $ 405 / 1 / -- / -- / -- / 1 / 1 / -- / 1 / -- / 1 / 1 / --
4 / $ 410 / -- / 1 / -- / -- / 1 / -- / -- / -- / -- / 1 / -- / 1
5 / $ 425 / -- / -- / 1 / 1 / -- / -- / 1 / -- / -- / -- / -- / --
6 / $ 457 / 1 / -- / -- / 1 / -- / -- / 1 / -- / -- / -- / 1 / --
7 / $ 461 / -- / -- / -- / -- / 1 / -- / -- / 1 / -- / 1 / -- / --
8 / $ 475 / 1 / -- / -- / -- / 1 / -- / -- / -- / 1 / -- / 1 / --
9 / $ 479 / -- / -- / 1 / 1 / -- / -- / -- / 1 / -- / -- / -- / 1
10 / $ 495 / -- / -- / 1 / 1 / -- / -- / 1 / -- / 1 / -- / 1 / --
11 / $ 523 / -- / 1 / -- / -- / -- / 1 / -- / 1 / 1 / -- / -- / 1

For example, possible duty plan 1 assigns a single flight crew to flights 101, 203, 402. The cost of each duty plan is determined by your labor agreement with the pilots. Each flight must have exactly one flight crew.

Which duty plans should you use to minimize your costs?