Title: Large neighbourhood search for large-scale shift assignment problems with multiple tasks
Authors: Smet, Pieter ×
Vanden Berghe, Greet #
Issue Date: Aug-2016
Host Document: Proceedings of the 11th international conference on the practice and theory of automated timetabling pages:339-352
Conference: Practice and Theory of Automated Timetabling (PATAT2016) location:Udine, Italy date:23-26 August 2016
Abstract: 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.
Publication status: published
KU Leuven publication type: IC
Appears in Collections:Computer Science Technology TC, Technology Campuses Ghent and Aalst
Technologiecluster Computerwetenschappen
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
techrepSDTSS.pdf Published 783KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.