Proceedings of the 11th international conference on the practice and theory of automated timetabling pages:339-352
Practice and Theory of Automated Timetabling (PATAT2016) location:Udine, Italy date:23-26 August 2016
Shift scheduling with multiple tasks presents a challenging combinatorial optimisation problem in which two decisions must be taken simultaneously. Both tasks and shifts are fixed in time and must be assigned to qualified employees while minimizing costs originating from employee preferences. The present paper presents a natural integer programming formulation for this problem and introduces two lower bounds on the optimal solution quality. Two exponentially-sized neighbourhoods are used in a large neighbourhood search algorithm for improving initial solutions constructed by a greedy heuristic. Extensive computational experiments are analysed to gain insights into the performance and behaviour of the proposed solution approaches. All experiments are conducted on a randomly generated benchmark dataset inspired by real cases. The results demonstrate that the presented large neighbourhood search finds optimal solutions for all instances in relatively short computation time.