Crew Scheduling |
|
|
|
|
|
| A
small airline company maintains 2 daily flights between Salt Lake City,
Chicago and Dallas. |
| How should the
company schedule the crews to minimize cost? |
|
|
|
|
|
|
|
|
|
| Flight Schedule |
|
|
|
|
|
| From |
To |
Departure |
Arrival |
Departure |
Arrival |
|
| Salt Lake City |
Dallas |
9:00 AM |
12:00 PM |
2:00 PM |
5:00 PM |
|
| Salt Lake City |
Chicago |
10:00 AM |
2:00 PM |
3:00 PM |
7:00 PM |
|
| Dallas |
Salt Lake City |
8:00 AM |
11:00 AM |
2:00 PM |
5:00 PM |
|
| Dallas |
Chicago |
9:00 AM |
11:00 AM |
3:00 PM |
5:00 PM |
|
| Chicago |
Salt Lake City |
8:00 AM |
12:00 PM |
2:00 PM |
6:00 PM |
|
| Chicago |
Dallas |
10:00 AM |
12:00 PM |
4:00 PM |
6:00 PM |
|
|
|
|
|
|
|
|
| A
crew must leave and arrive in the same city. It is possible to fly the crew
back aboard another |
| airline.
This would always be on a 8:00 PM flight. There are 6 airplanes in use. |
|
| When
a crew is actually flying a plane, the entire crew is paid $200 per hour. The
other time spent |
| (waiting
between flights or flying aboard another airplane) costs the company $75 per
hour. |
|
|
|
|
|
|
|
| Possible Crew Rotations |
|
|
|
|
|
| (S=Salt
Lake City, D=Dallas, C=Chicago, ( )=Back with other company) |
|
| |
Flying Hours |
Other Hours |
Cost |
Decision |
|
|
| SD+DS |
6 |
2 |
$1,350 |
0 |
|
|
| SD+(DS) |
3 |
11 |
$1,425 |
0 |
|
|
| SD+DC+(CS) |
5 |
10 |
$1,750 |
0 |
|
|
| SC+(CS) |
4 |
10 |
$1,550 |
0 |
|
|
| SC+CD+(DS) |
6 |
5 |
$1,575 |
0 |
|
|
| DS+SD |
6 |
3 |
$1,425 |
0 |
|
|
| DS+(SD) |
3 |
12 |
$1,500 |
0 |
|
|
| DS+SC+(CD) |
7 |
7 |
$1,925 |
0 |
|
|
| DC+CS+(SD) |
6 |
5 |
$1,575 |
0 |
|
|
| DC+CD |
4 |
5 |
$1,175 |
0 |
|
|
| CS+SD+(DC) |
7 |
7 |
$1,925 |
0 |
|
|
| CS+SC |
8 |
3 |
$1,825 |
0 |
|
|
| CD+DC |
4 |
3 |
$1,025 |
0 |
|
|
| CD+DS+(SC) |
7 |
9 |
$2,075 |
0 |
|
|
| |
|
Total Cost |
$0 |
|
|
|
|
|
|
|
|
|
|
| Twelve Flight
Constraints |
|
|
|
|
|
| Flight |
Number of
crews |
|
|
|
|
| SD 1 |
0 |
|
|
|
|
|
| SD 2 |
0 |
|
|
|
|
|
| SC 1 |
0 |
|
|
|
|
|
| SC 2 |
0 |
|
|
|
|
|
| DS 1 |
0 |
|
|
|
|
|
| DS 2 |
0 |
|
|
|
|
|
| DC 1 |
0 |
|
|
|
|
|
| DC 2 |
0 |
|
|
|
|
|
| CS 1 |
0 |
|
|
|
|
|
| CS 2 |
0 |
|
|
|
|
|
| CD 1 |
0 |
|
|
|
|
|
| CD 2 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Problem |
|
|
|
|
|
|
| An
airline company maintains a schedule of two daily flights between Salt Lake
City, Dallas and |
| Chicago.
A crew that leaves a city in the morning has to return there at night. The
crew can be |
| brought
back on another airline. There are 6 airplanes in use. When a crew is flying,
the cost is $200 |
| per
hour. When a crew is waiting or being flown back, the cost is $75. How should
the company |
| schedule its
crews to minimize cost? |
|
|
|
|
| |
|
|
|
|
|
|
| Solution |
|
|
|
|
|
|
| 1)
The airline has already determined what all the possible crew rotations can
be. The variables are |
| the
binary integer decisions to accept rotations. In worksheet Crew these are
defined as |
|
| Rotation_decisions. |
|
|
|
|
|
| 2) The
constraints are simple. We want only one crew per flight. This gives |
|
|
| |
Crews_on_flight = 1 |
|
|
|
|
| and the
logical constraint gives |
|
|
|
|
|
| |
Rotation_decisions = binary |
|
|
|
|
| 3) The objective is to minimize total cost. On worksheet Crew this cell is given the
name Total_cost. |
| |
|
|
|
|
|
|
| Remarks |
|
|
|
|
|
|
| Please
confirm for yourself that the crew rotations chosen meet the required
schedule. More |
| sphisticated
versions of this model are widely used in the airline industry, but the same
approach |
| can be used in
scheduling truck drivers, boat crews, etc. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|