Multi-neighborhood simulated annealing for the multi-activity multi-day shift scheduling problem

Abstract This paper addresses the multi-activity multi-day shift scheduling problem with a homogeneous workforce and a quadratic cost function for overstaffing. The objective of this problem is to assign shifts to employees and activities within these shifts, based on short time intervals, while adhering to numerous hard constraints and minimizing overstaffing. We propose a multi-neighborhood simulated annealing algorithm as a solution method, for which we introduce nine neighborhood relations. The search space and neighborhood relations are designed so that the search algorithm can be executed efficiently even on large problem instances. The method is evaluated on a benchmark dataset consisting of problem instances with varying complexity. The results demonstrate that our approach can handle even the most complex tasks and consistently produce feasible solutions for all 225 problem instances, 118 of which were previously unsolved. Furthermore, our method outperforms the solver that produced the previous best-known solutions for the dataset and achieves new best solutions for all instances. Our algorithm is capable of generating high-quality schedules within just a few seconds.