A Simulated Annealing Approach to the Multi-Activity Multi-Day Shift Scheduling Problem

This paper addresses the multi-activity multi-day shift scheduling problem with a homogeneous workforce and 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, respecting numerous hard constraints and minimizing overstaffing. We propose a multi-neighborhood Simulated Annealing algorithm as a solution method, for which we introduce eight 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 show that our approach can handle even the most complex tasks and is able to find feasible solutions for 201 out of the 225 total problem instances, of which 99 were previously unsolved. Our method outperforms the solver that produced the previous best known solutions for the benchmark dataset and finds new best solutions for 190 of the instances. The algorithm can create good schedules in a matter of a few seconds, using limited computing resources. © 2024 PATAT. All Rights Reserved.