4.7 Article

Grammar-Based Integer Programming Models for Multiactivity Shift Scheduling

期刊

MANAGEMENT SCIENCE
卷 57, 期 1, 页码 151-163

出版社

INFORMS
DOI: 10.1287/mnsc.1100.1264

关键词

shift scheduling; implicit models; mixed integer programming; context-free grammars

资金

  1. Fonds Quebecois de Recherche sur la Nature et les Technologies

向作者/读者索取更多资源

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.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.7
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据