Document RAIRO-Oper. Res. 42 (2008) 229-258
DOI: 10.1051/ro:2008006
Solution approaches to large shift scheduling problems
Monia Rekik1, Jean-François Cordeau2 and François Soumis11 École Polytechnique de Montréal and GERAD, C.P. 6079, succ. Centre-Ville Montréal, H3C 3A7, Canada
2 HEC Montréal and GERAD, 3000, chemin de la Côte-Sainte-Catherine, Montréal H3T 2A7, Canada; jean-francois.cordeau@hec.ca
(Received May 31, 2007. Accepted November 28, 2007. Published online 17 May 2008.)
Abstract
This paper considers large shift scheduling problems with different shift
start times and lengths, fractionable breaks and work stretch duration
restrictions. Two solution approaches are proposed to solve the problems
over a multiple-day planning horizon. The first approach is based on a
local branching strategy and the second one is based on a temporal
decomposition of the problem. Local branching is very
efficient in finding good feasible solutions when compared to a classical
branch-and-bound procedure. However, the decomposition approach has the
advantage of yielding feasible solutions in short computing times, even for difficult instances.
Mathematics Subject Classification. 90C10, 90C11, 90C29.
Key words: Shift scheduling, flexibility, fractionable breaks, work stretch restrictions, forward and backward constraints, local branching, heuristic.
© EDP Sciences, ROADEF, SMAI 2008