×

zbMATH — the first resource for mathematics

Modeling and solving a real-life multi-skill shift design problem. (English) Zbl 1368.90062
Summary: In this work, we consider the shift design problem and we define a novel, complex formulation arising from practical cases. In addition, we propose a new search method based on a fast Simulated Annealing, that, differently from previous approaches, solves the overall problem as a single-stage procedure. The core of the method is a composite neighborhood that includes at the same time changes in the staffing of shifts, the shape of shifts, and the position of breaks. Finally, we present a statistically-principled experimental analysis on a set of instances obtained from real cases. Both instances and results are available on the web for future comparisons.

MSC:
90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aarts, E. H. L., & Korst, J. (1989). Simulated annealing and Boltzmann machines. New York: Wiley. · Zbl 0674.90059
[2] Alfares, HK, Survey, categorization, and comparison of recent tour scheduling literature, Annals of Operations Research, 127, 145-175, (2004) · Zbl 1087.90023
[3] Aykin, T, Optimal shift scheduling with multiple break windows, Management Science, 42, 591-603, (1996) · Zbl 0880.90065
[4] Aykin, T, A comparative evaluation of modelling approaches to the labour shift scheduling problem, European Journal of Operational Research, 125, 381-397, (2000) · Zbl 0971.90025
[5] Bechtold, SE; Jacobs, LW, Implicit modelling of flexible break assignments in optimal shift scheduling, Management Science, 36, 1339-1351, (1990)
[6] Beer, A., Gärtner, J., Musliu, N., Schafhauser, W., & Slany, W. (2008). Scheduling breaks in shift plans for call centers. In Proceedings of The 7th international conference on the practice and theory of automated timetabling. Montreal, Canada. · Zbl 1053.90043
[7] Beer, A; Gärtner, J; Musliu, N; Schafhauser, W; Slany, W, An AI-based break-scheduling system for supervisory personnel, IEEE Intelligent Systems, 25, 60-73, (2010)
[8] Bhulai, S; Koole, G; Pot, A, Simple methods for shift scheduling in multiskill call centers, Manufacturing & Service Operations Management, 10, 411-420, (2008)
[9] Birattari, M. (2004). The problem of tuning metaheuristics as seen from a machine learning perspective, PhD thesis. Belgium: Université Libre de Bruxelles. · Zbl 1101.68748
[10] Černý, V, Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm, Journal of Optimization Theory and Applications, 45, 41-51, (1985) · Zbl 0534.90091
[11] Côté, M-C; Gendron, B; Quimper, C-G; Rousseau, L-M, Formal languages for integer programming modeling of shift scheduling problems, Constraints, 16, 55-76, (2011) · Zbl 1215.90026
[12] Côté, M-C; Gendron, B; Rousseau, L-M, Grammar-based integer programming models for multiactivity shift scheduling, Management Science, 57, 151-163, (2011) · Zbl 1214.90077
[13] Dantzig, GB, A comment on eddie’s traffic delays at toll booths, Operations Research, 2, 339-341, (1954)
[14] Gaspero, L; Gärtner, J; Kortsarz, G; Musliu, N; Schaerf, A; Slany, W, The minimum shift design problem, Annals of Operations Research, 155, 79-105, (2007) · Zbl 1145.90019
[15] Di Gaspero, L; Gärtner, J; Musliu, N; Schaerf, A; Schafhauser, W; Slany, W; Blesa, MJ (ed.); Blum, C (ed.); Raidl, G (ed.); Roli, A (ed.); Sampels, M (ed.), A hybrid LS-CP solver for the shifts and breaks design problem, 46-61, (2010), Berlin
[16] Di Gaspero, L; Gärtner, J; Musliu, N; Schaerf, A; Schafhauser, W; Slany, W; Uyar, SA (ed.); Ozcan, E (ed.); Urquhart, N (ed.), Automated shift design and break scheduling, 109-127, (2013), Berlin
[17] Gaspero, L; Schaerf, A, Easylocal++: an object-oriented framework for flexible design of local search algorithms, Software-Practice and Experience, 33, 733-765, (2003)
[18] Gärtner, J., Musliu, N., & Slany, W. (2004). A heuristic based system for generation of shifts with breaks. In Proceedings of the 24th SGAI international conference on innovative techniques and applications of artificial intelligence, Cambridge. · Zbl 1187.90141
[19] Hammersley., JM; Handscomb, DC; Weiss, G, Monte Carlo methods, Physics Today, 18, 55, (1965)
[20] Johnson, DS; Aragon, CR; McGeoch, LA; Schevon, C, Optimization by simulated annealing: an experimental evaluation; part I, graph partitioning, Operations Research, 37, 865-892, (1989) · Zbl 0698.90065
[21] Kirkpatrick, S; Gelatt, D; Vecchi, M, Optimization by simulated annealing, Science, 220, 671-680, (1983) · Zbl 1225.90162
[22] Musliu, N; Schaerf, A; Slany, W, Local search for shift design, European Journal of Operational Research, 153, 51-64, (2004) · Zbl 1053.90043
[23] Quimper, C-G; Rousseau, L-M, A large neighbourhood search approach to the multi-activity shift scheduling problem, Journal of Heuristics, 16, 373-391, (2010) · Zbl 1187.90141
[24] Rekik, M; Cordeau, J-F; Soumis, F, Implicit shift scheduling with multiple breaks and work stretch duration restrictions, Journal of Scheduling, 13, 49-75, (2010) · Zbl 1185.90091
[25] Rekik, M; Cordeau, J-F; Soumis, F, Using benders decomposition to implicitly model tour scheduling, Annals of Operations Research, 128, 111-133, (2004) · Zbl 1056.90073
[26] Tellier, P., & White, G. (2006). Generating personnel schedules in an industrial setting using a tabu search algorithm. In E. K. Burke & H. Rudova (Eds.), In The 5th international conference on the practice and theory of automated timetabling (pp. 293-302).
[27] Thompson, G, Improved implicit modeling of the labor shift scheduling problem, Management Science, 41, 595-607, (1995) · Zbl 0836.90108
[28] Urli, T. (2013). json2run: A tool for experiment design & analysis. arXiv:1305.1112.
[29] van Laarhoven, P. J. M., & Aarts, E. H. L. (1987). Simulated annealing: Theory and applications. New York: Kluwer. · Zbl 0643.65028
[30] Widl, M; Musliu, N, The break scheduling problem: complexity results and practical algorithms, Memetic Computing, 6, 97-112, (2014)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.