Grammar-Based Integer Programming Models for Multiactivity Shift Scheduling
AbstractThis 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. This paper was accepted by Dimitris Bertsimas, optimization.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoArticle provided by INFORMS in its journal Management Science.
Volume (Year): 57 (2011)
Issue (Month): 1 (January)
shift scheduling; implicit models; mixed integer programming; context-free grammars;
You can help add them by filling out this form.
CitEc Project, subscribe to its RSS feed for this item.
- Restrepo, María I. & Lozano, Leonardo & Medaglia, Andrés L., 2012. "Constrained network-based column generation for the multi-activity shift scheduling problem," International Journal of Production Economics, Elsevier, vol. 140(1), pages 466-472.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc).
If references are entirely missing, you can add them using this form.