Grammar-Based Integer Programming Models for Multiactivity Shift Scheduling

Marie-Claude Côté (), Bernard Gendron () and Louis-Martin Rousseau ()
Additional contact information
Marie-Claude Côté: CIRRELT and Département de Mathématiques et de Génie Industriel, École Polytechnique de Montréal, Montréal, Québec H3C 3A7, Canada
Bernard Gendron: CIRRELT and Département d'Informatique et de Recherche Opérationnelle, Université de Montréal, Montréal, Québec H3C 3J7, Canada
Louis-Martin Rousseau: CIRRELT and Département de Mathématiques et de Génie Industriel, École Polytechnique de Montréal, Montréal, Québec H3C 3A7, Canada

Management Science, 2011, vol. 57, issue 1, 151-163

Abstract: 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. This paper was accepted by Dimitris Bertsimas, optimization.

Keywords: shift scheduling; implicit models; mixed integer programming; context-free grammars (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (17)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.1100.1264 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:57:y:2011:i:1:p:151-163

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().