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

• We present a branch-and-bound approach for shift scheduling with non-stationary demand and (stochastic) service level constraints.
• The algorithm efficiently explores the solution space and quickly finds an estimated optimum.
• The algorithm is intended for personnel planning in small-scale service systems with limited opening hours.
• The algorithm is also highly competitive for larger-scale settings, when compared to benchmark algorithms from the literature.

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).