Grammar-Based Integer Programming Models for Multi-Activity Shift Scheduling
This paper presents a new implicit formulation for shift scheduling problems, using context-free grammars to model regulation in the composition of shifts. From the grammar, we generate an integer programming (IP) model having a linear programming (LP) relaxation equivalent to that of Dantzig 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, multi-activity 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 and we experimentally demonstrate the interest of our modeling approach on problems dealing with up to ten work-activities.