A Simulated-Annealing Heuristic for Shift Scheduling Using Non-Continuously Available Employees

Abstract

This paper presents a simulated-annealing heuristic (SAH) for developing shift schedules. We assume that each employee is available only during an individually-specified portion of the day and has individually-specified limits on the duration of shifts to which he/she can be assigned. We evaluate the effectiveness of the SAH under several "neighborhood" search parameters using a primary set of 144 test problems. These parameters include numerous criteria for adding shifts during schedule construction and for dropping shifts during schedule improvement. Our results allow us to make observations regarding appropriate search "neighborhoods" in labor-scheduling and other applications of simulated-annealing. Using a secondary set of 20 test problems we compare the SAH to an efficient optimal integer-programming model. On average, SAH's schedules are 0.29% more costly than optimal schedules but are obtained in 8.4% of the time required to generate optimal schedules.