NobleBlocks

Research indexJournal article

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

Côté, Gendron, Rousseau

DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)1 Jan 2009Open access

NobleIDark:/48914/w1/20260524/6C833364DOI10.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.

Discussion

Citations

Topics

More

Suggest a correction or report