Grammar‐Based Integer Programming Models for Multiactivity Shift Scheduling

Grammar‐Based Integer Programming Models for Multiactivity Shift Scheduling

0.00 Avg rating0 Votes
Article ID: iaor20111766
Volume: 57
Issue: 1
Start Page Number: 151
End Page Number: 163
Publication Date: Jan 2011
Journal: Management Science
Authors: , ,
Keywords: programming: integer, scheduling
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.

Reviews

Required fields are marked *. Your email address will not be published.