Personnel scheduling aims to determine least-cost personnel schedules to meet the demand for employees in each period of a planning horizon. In this article, we propose a heuristic, called Parallel Stimulation of Disruptions Heuristic (PSDH), for solving a personnel scheduling problem. PSDH is a new, integrated approach for this type of problem, which generates and affects shifts simultaneously. It is based on the iterative stimulation/correction of a set of disruptions on certain employee schedules. Each disruption is targeted according to predetermined probabilistic improvement scores, and repaired using an algorithm inspired by the heuristic of Hassani et al. (2021), which re-optimizes a schedule following a minor disruption. The approach is also based on a partition of the current solution, which is updated at each iteration to stimulate/repair the maximum number of disruptions in parallel. The proposed algorithm has been tested on real-life instances involving up to 94 employees and 10 jobs. PSDH found solutions of very good quality (2.01% from optimality on average) in fast computational times (less than three minutes on average).
Published January 2021 , 23 pages