Tools › Operations Research › Scheduling › Shift Scheduling › Example

Union Airways agent scheduling: five shifts covering ten periods at least daily cost (Hillier and Lieberman Section 3.4)

ToolShift Scheduling
SourceHillier, F. S., and Lieberman, G. J. (2015). Introduction to Operations Research, 10th ed. McGraw-Hill, New York. Section 3.4, personnel scheduling at Union Airways (Table 3.19).
LevelUndergraduate

Problem

Union Airways needs customer service agents at its hub in ten periods of the day: at least 48 (6-8 am), 79 (8-10), 65 (10-12), 87 (12-2 pm), 64 (2-4), 73 (4-6), 82 (6-8), 43 (8-10), 52 (10-12 pm) and 15 (midnight-6 am). Five eight-hour shifts are authorized: 6 am-2 pm at $170 per agent per day, 8 am-4 pm at $160, noon-8 pm at $175, 4 pm-midnight at $180 and 10 pm-6 am at $195. How many agents should be assigned to each shift to meet every requirement at least total cost?

Inputs to Enter

  • Demand: ten labelled periods with the minimum agents 48, 79, 65, 87, 64, 73, 82, 43, 52, 15 (the last period is six hours long)
  • Shifts typed as periods covered and cost: Shift 1 periods 1-4 at 170, Shift 2 2-5 at 160, Shift 3 4-7 at 175, Shift 4 6-9 at 180, Shift 5 9-10 at 195
  • Objective: minimize total cost; Show LP Details on
Open the Shift Scheduling tool (loaded with this example)

Answers

  • Optimal staffing x = 48, 31, 39, 43, 15 agents on shifts 1 to 5 (book: the same), 176 agents in total
  • Minimum cost Z = 170(48) + 160(31) + 175(39) + 180(43) + 195(15) = $30,610 per day (book: $30,610)
  • The LP relaxation is already integral (Z_LP = 30,610, gap 0 %), so no branching is needed
  • Coverage 48, 79, 79, 118, 70, 82, 82, 43, 58, 15: the periods 6-8 am, 8-10 am, 6-8 pm, 8-10 pm and 12-6 am are met exactly; shadow prices 10, 160, 0, 0, 0, 0, 175, 5, 0, 195 per extra agent required
  • Closed-form headcount bounds: peak 87, work-period bound ⌈608 / 4⌉ = 152; utilization 608 / 674 = 90.2 %

Notes

The tool's default inputs are this case; press Submit. The optimum, the LP value and the shadow prices are reproduced by scipy's milp and linprog (HiGHS) in References/Shift-Scheduling/shift_check.py; the same page solves Winston's post-office days-off problem (LP 67/3, 23 employees) and the 26-bus problem of Taha from the Problem select (test_shift_scheduling.php, 208 checks).