Grammar-Based Integer Programming Models for Multiactivity Shift 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. This paper was accepted by Dimitris Bertsimas, optimization.
Volume (Year): 57 (2011)
Issue (Month): 1 (January)
|Contact details of provider:|| Postal: 7240 Parkway Drive, Suite 300, Hanover, MD 21076 USA|
Web page: http://www.informs.org/
More information through EDIRC
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Turgut Aykin, 1996. "Optimal Shift Scheduling with Multiple Break Windows," Management Science, INFORMS, vol. 42(4), pages 591-602, April.
- Willie B. Henderson & William L. Berry, 1976. "Heuristic Methods for Telephone Operator Shift Scheduling: An Experimental Analysis," Management Science, INFORMS, vol. 22(12), pages 1372-1380, August.
- Larry P. Ritzman & LeRoy J. Krajewski & Michael J. Showalter, 1976. "The Disaggregation of Aggregate Manpower Plans," Management Science, INFORMS, vol. 22(11), pages 1204-1214, July.
- Gary M. Thompson, 1995. "Improved Implicit Optimal Modeling of the Labor Shift Scheduling Problem," Management Science, INFORMS, vol. 41(4), pages 595-607, April.
When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:57:y:2011:i:1:p:151-163. See general information about how to correct material in RePEc.
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.