Grammar-based integer programming models for multiactivity shift scheduling / Marie-Claude Côté in Management science, Vol. 57 N° 1 (Janvier 2011)  

Public ISBD [article]  inManagement science > Vol. 57 N° 1 (Janvier 2011) . - pp. 151-163 Titre : Grammar-based integer programming models for multiactivity shift scheduling Type de document : texte imprimé Auteurs : Marie-Claude Côté, Auteur ; Bernard Gendron, Auteur ; Louis-Martin Rousseau, Auteur Année de publication : 2011 Article en page(s) : pp. 151-163 Note générale : Management Langues : Anglais (eng) Mots-clés : Shift scheduling Implicit models Mixed integer programming Context-free grammars Index. décimale : 658 Organisation des entreprises. Techniques du commerce Résumé : 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. DEWEY : 658 ISSN : 0025-1909 En ligne : http://mansci.journal.informs.org/cgi/content/abstract/57/1/151 [article] Grammar-based integer programming models for multiactivity shift scheduling [texte imprimé] / Marie-Claude Côté, Auteur ; Bernard Gendron, Auteur ; Louis-Martin Rousseau, Auteur . - 2011 . - pp. 151-163. Management Langues : Anglais (eng) in Management science > Vol. 57 N° 1 (Janvier 2011) . - pp. 151-163 Mots-clés : Shift scheduling Implicit models Mixed integer programming Context-free grammars Index. décimale : 658 Organisation des entreprises. Techniques du commerce Résumé : 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. DEWEY : 658 ISSN : 0025-1909 En ligne : http://mansci.journal.informs.org/cgi/content/abstract/57/1/151

Exemplaires

Code-barres	Cote	Support	Localisation	Section	Disponibilité
aucun exemplaire