Article ID: | iaor20111766 |
Volume: | 57 |
Issue: | 1 |
Start Page Number: | 151 |
End Page Number: | 163 |
Publication Date: | Jan 2011 |
Journal: | Management Science |
Authors: | Gendron Bernard, Rousseau Louis-Martin, Ct Marie-Claude |
Keywords: | programming: integer, scheduling |
This paper presents a new implicit formulation for shift scheduling problems, using context‐free grammars to model the rules for the composition of shifts. From the grammar, we generate an integer programming (IP) model having a linear programming relaxation equivalent to that of the classical set covering model. When solved by a state‐of‐the‐art IP solver on problem instances with a small number of shifts, our model, the set covering formulation, and a typical implicit model from the literature yield comparable solution times. On instances with a large number of shifts, our formulation shows superior performance and can model a wider variety of constraints. In particular, multiactivity cases, which cannot be modeled by existing implicit formulations, can easily be handled with grammars. We present comparative experimental results on a large set of instances involving one work activity, as well as on problems dealing with up to 10 work activities.