A branch-and-bound algorithm for shift scheduling with stochastic nonstationary demand

Many shift scheduling algorithms presume that the staffing levels, required to ensure a target customer service, are known in advance. Determining these staffing requirements is often not straightforward, particularly in systems where the arrival rate fluctuates over the day. We present a branch-and-bound approach to estimate optimal shift schedules in systems with nonstationary stochastic demand and service level constraints. The algorithm is intended for personnel planning in service systems with limited opening hours (such as small call centers, banks, and retail stores). Our computational experiments show that the algorithm is efficient in avoiding regions of the solution space that cannot contain the optimum; moreover, it requires only a limited number of evaluations to encounter the estimated optimum. The quality of the starting solution is not a decisive factor for the algorithm's performance. Finally, by benchmarking our algorithm against two state-of-the-art algorithms, we show that our algorithm is very competitive, as it succeeds in finding a high-quality solution fast (i.e., with a limited number of simulations required in the search phase). (C) 2015 Elsevier Ltd. All rights reserved.