nach oben

Journal of Scheduling

Erschienen in:

01.04.2014

A branch-and-price algorithm for the multi-activity multi-task shift scheduling problem

verfasst von: Vincent Boyer, Bernard Gendron, Louis-Martin Rousseau

Erschienen in: Journal of Scheduling | Ausgabe 2/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The multi-activity multi-task shift scheduling problem requires the assignment of interruptible activities and uninterruptible tasks to a set of employees in order to satisfy a demand function. In this paper, we consider the personalized variant of the problem where the employees have different qualifications, preferences, and availabilities. We present a branch-and-price algorithm to solve this problem. The pricing subproblems in column generation are formulated with context-free grammars that are able to model complex rules in the construction of feasible shifts for an employee. We present results for a large set of instances inspired by real cases and show that this approach is sufficiently flexible to handle different classes of problems.

Vorheriger Artikel Online scheduling with preemption or non-completion penalties

Nächster Artikel The optimal number of used machines in a two-stage flexible flowshop scheduling problem

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Barnhart, C., Hane, C. A., & Vance, P. H. (2000). Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems. Operations Research, 48(2), 318–326.CrossRef

Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998). Branch-and-price: Column generation for solving huge integer programs. Operations Research, 46(3), 316–329.CrossRef

Contreras, I., Díaz, J., & Fernández, E. (2011). Branch and price for large-scale capacitated hub location problems with single assignment. INFORMS Journal of Computing, 23, 41–55.CrossRef

Côté, M. C., Gendron, B., Quimper, C. G., & Rousseau, L. M. (2011a). Formal languages for integer programming modeling of shift scheduling problems. Constraints, 16(1), 54–76.

Côté, M. C., Gendron, B., & Rousseau, L. M. (2011b). Grammar-based integer programming models for multiactivity shift scheduling. Management Science, 57(1), 151–163.

Côté, M. C., Gendron, B., & Rousseau, L. M. (2012). Grammar-based column generation for personalized multi-activity shift scheduling. INFORMS Journal of Computing. doi:10.1287/ijoc.1120.0514.

Crainic, T. G., Frangioni, A., Gendron, B., & Guertin, F. (2009). OOBB: An object-oriented library for parallel branch-and-bound. In: CORS/INFORMS international conference, Toronto, Canada.

Dantzig, G. B. (1954). A comment on Edie’s “Traffic delays at toll booths”. Journal of the Operations Research Society of America, 2(3), 339–341.CrossRef

Demassey, S., Pesant, G., & Rousseau, L. M. (2006). A cost-regular based hybrid column generation approach. Constraints, 11(4), 315–333.CrossRef

Desaulniers, G., Desrosiers, J., & Solomon, M. M. (2005). Column generation. New York: Springer.CrossRef

Ernst, A. T., Jiang, H., Krishnamoorthy, M., Owens, B., & Sier, D. (2004a). An annotated bibliography of personnel scheduling and rostering. Annals of Operations Research, 127(1), 21–144.CrossRef

Ernst, A. T., Jiang, H., Krishnamoorthy, M., & Sier, D. (2004b). Staff scheduling and rostering: A review of applications, methods and models. European Journal of Operational Research, 153(1), 3–27.CrossRef

Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2001). Introduction to automata theory, languages and computability. Boston: Addison-Welsey.

Lequy, Q., Bouchard, M., Desaulniers, G., Soumis, F., & Tachefine, B. (2010a). Assigning multiple activities to work shifts. Journal of Scheduling, 15(2), 239–251.CrossRef

Lequy, Q., Desaulniers, G., Solomon, M. M. (2010b) Assigning team tasks and multiple activities to fixed work shifts. Cahiers du GERAD (G-2010-71). Montreal: HEC Montreal.

Lequy, Q., Desaulniers, G., Solomon, M. M. (2010c) A two-stage heuristic for multi-activity and task assignment to work shifts. Cahiers du GERAD (G-2010-28). Montreal: HEC Montreal.

Quimper, C. G., & Rousseau, L. M. (2009). A large neighbourhood search approach to the multi-activity shift scheduling problem. Journal of Heuristics, 16(3), 373–392.CrossRef

Quimper, C. G., & Walsh, T. (2007). Decomposing global grammar constraints. In: Principles and practice of constraint programming-CP 2007. Lecture notes in computer science (Vol. 4741, pp. 590–604). New York: Springer.

Tang, L., Wang, G., & Liu, J. (2007). A branch-and-price algorithm to solve the molten iron allocation problem in iron and steel industry. Computers & Operations Research, 34(10), 3001–3015.CrossRef

Tang, L., Wang, G., Liu, J., & Liu, J. (2011). A combination of lagrangian relaxation and column generation for order batching in steelmaking and continuous-casting production. Naval Research Logistics, 58(4), 370–388.CrossRef

van den Akker, J. M., Hoogeveen, J. A., & van de Velde, S. L. (1999). Parallel machine scheduling by column generation. Operations Research, 47(6), 862–872.CrossRef

Titel: A branch-and-price algorithm for the multi-activity multi-task shift scheduling problem
verfasst von: Vincent Boyer
Bernard Gendron
Louis-Martin Rousseau
Publikationsdatum: 01.04.2014
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 2/2014
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-013-0338-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 2/2014

The optimal number of used machines in a two-stage flexible flowshop scheduling problem

Online scheduling with preemption or non-completion penalties

A sequential GRASP for the therapist routing and scheduling problem

Approximation schemes for single machine scheduling with non-renewable resource constraints

Minimizing total weighted completion time with an unexpected machine unavailable interval

The total adjustment cost problem: Applications, models, and solution algorithms

Premium Partner