A simulated-annealing heuristic for shift scheduling using non-continuously available employees

This paper presents a simulated-annealing heuristic (SAH) for developing shift schedules. The paper assumes 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. It evaluates 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. The present 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 the paper compares 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.