License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-21775
URL: http://drops.dagstuhl.de/opus/volltexte/2009/2177/

Cote, Marie-Claude ; Gendron, Bernard ; Rousseau, Louis-Martin

Grammar-Based Integer Programing Models for Multi-Activity Shift Scheduling

pdf-format:
Dokument 1.pdf (95 KB)


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.

BibTeX - Entry

@InProceedings{cote_et_al:DSP:2009:2177,
  author =	{Marie-Claude Cote and Bernard Gendron and Louis-Martin Rousseau},
  title =	{Grammar-Based Integer Programing Models for Multi-Activity Shift Scheduling},
  booktitle =	{Models and Algorithms for Optimization in Logistics},
  year =	{2009},
  editor =	{Cynthia Barnhart and Uwe Clausen and Ulrich Lauther and Rolf H. M{\"o}hring},
  number =	{09261},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/2177},
  annote =	{Keywords: Shift Scheduling, Implicit models, Integer Programming,  Context-free grammars}
}

Keywords: Shift Scheduling, Implicit models, Integer Programming, Context-free grammars
Seminar: 09261 - Models and Algorithms for Optimization in Logistics
Issue date: 2009
Date of publication: 02.10.2009


DROPS-Home | Fulltext Search | Imprint Published by LZI