DagSemProc.09261.9.pdf
- Filesize: 94 kB
- 2 pages
Document
Grammar-Based Integer Programing Models for Multi-Activity Shift Scheduling
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 9261
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2009-10-02
Cite As Get BibTex
Marie-Claude Cote, Bernard Gendron, and Louis-Martin Rousseau. Grammar-Based Integer Programing Models for Multi-Activity Shift Scheduling. In Models and Algorithms for Optimization in Logistics. Dagstuhl Seminar Proceedings, Volume 9261, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/DagSemProc.09261.9
Abstract
We present 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 allowing the same set of shifts as Dantzig’s set covering model. When solved by a state-of-the- art IP solver on problems allowing a small number of shifts, our model, the set covering formulation and a typical implicit model from the literature yield comparable solving times. Moreover, on instances where many shifts are allowed, our model is superior and can encode a wider variety of constraints. Among others, multi-activity cases, which cannot be modeled by existing implicit formulations, can easily be captured with grammars.
Subject Classification
Keywords
- Shift Scheduling
- Implicit models
- Integer Programming
- Context-free grammars
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads