The Extended Shift Minimization Personnel Task Scheduling Problem

Kyngäs, Nico; Nurmi, Kimmo

doi:10.15439/2021F35

Artykuł - szczegóły

Tytuł artykułu

The Extended Shift Minimization Personnel Task Scheduling Problem

Autorzy

Kyngäs Nico , Nurmi Kimmo

Wybrane pełne teksty z tego czasopisma

http://annals-csis.org

Identyfikatory

DOI

10.15439/2021F35

Warianty tytułu

Konferencja

Federated Conference on Computer Science and Information Systems (16 ; 02-05.09.2021 ; online)

Języki publikacji

Abstrakty

In workforce scheduling, shift generation is the process of determining the shift structure, along with the tasks to be carried out in particular shifts. Application areas of shift generation include hospitals, retail stores, contact centers, cleaning, home care, guarding, manufacturing and delivery of goods. We present an extension to the Shift Minimization Personnel Task Scheduling Problem that is a problem in which a set of tasks with fixed start and finish times have to be allocated to a heterogeneous workforce. The objective in the SMPTSP is to minimize the number of employees required to carry out the given set of tasks. In the ESMPTSP, another objective is to maximize the number of feasible (shift, employee) pairs. We provide a mathematical formulation of the extended problem. We present an efficient ruin and recreate heuristic along with computational results for existing SMPTSP data sets and to a new data set. The presented heuristic is suitable for application in large real-world scenarios. The new instances, along with our best solutions, have been made available online.

Słowa kluczowe

workforce scheduling employee SMPTSP ruin heuristic recreate heuristic

planowanie siły roboczej pracownik SMPTSP heurystyka niszczenia heurystyka odtwarzania

Wydawca

Polskie Towarzystwo Informatyczne

Czasopismo

Annals of Computer Science and Information Systems

Rocznik

2021

Tom

Vol. 26

Strony

65--74

Opis fizyczny

Bibliogr. 25 poz., wz., tab.

Twórcy

autor

Kyngäs Nico

nico.kyngas@samk.fi

Satakunta University of Applied Sciences, Satakunnankatu 23, 28130 Pori, Finland

autor

Nurmi Kimmo

nico.kyngas@samk.fi

Satakunta University of Applied Sciences, Satakunnankatu 23, 28130 Pori, Finland

Bibliografia

1. A. T. Ernst, H. Jiang, M. Krishnamoorthy, and D. Sier, “Staff scheduling and rostering: A review of applications, methods and models”, European Journal of Operational Research vol. 153, no. 1, pp. 3-27, 2004.
2. J. Van den Bergh, J. Belin, P. De Bruecker, E. Demeulemeester and L. De Boeck, “Personnel scheduling: A literature review”, European Journal of Operational Research vol. 226, no. 3, pp 367-385, 2013.
3. L. Kletzander and N. Musliu, “Solving the General Employee Scheduling Problem”, Computers and Operations Research, vol. 13: 104794, 2020.
4. N. Musliu, A. Schaerf and W. Slany, “Local search for shift design”, European Journal of Operational Research, vol. 153, no. 1, pp. 51-64, 2004.
5. L. Di Gaspero, J. Gärtner, G. Kortsarz, N. Musliu, A. Schaerf and W. Slany, “The minimum shift design problem", Annals of Operations Research, vol. 155, no. pp. 79-105, 2007.
6. N. Kyngäs, D. Goossens, K. Nurmi and J. Kyngäs, “Optimizing the unlimited shift generation problem”, In: Di Chio C. et al. (eds) Applications of Evolutionary Computation. EvoApplications, Lecture Notes in Computer Science, vol. 7248, pp. 508-518, 2012.
7. N. Kyngäs, K. Nurmi and J. Kyngäs, “Solving the person-based multitask shift generation problem with breaks”, Proceedings of the 5th International Conference On Modeling, Simulation And Applied Optimization, pp. 1-8, 2013.
8. D. Dowling, M. Krishnamoorthy, H. Mackenzie and H. Sier, “Staff rostering at a large international airport”, Annals of Operations Research vol. 72, pp. 125-147, 1997.
9. V. Valls, A. Perez and S. Quintanilla, “A graph colouring model for assigning a heterogenous workforce to a given schedule”, European Journal of Operations Research vol. 90, pp. 285-302, 1996.
10. M. Krishnamoorthy and A.T. Ernst, “The personnel task scheduling problem”, Optimization Methods and Applications, pp. 343–367, 2001.
11. M. Krishnamoorthy, A.T. Ernst and D. Baatar, “Algorithms for large scale Shift Minimisation Personnel Task Scheduling Problems”, European Journal of Operational Research, vol. 219, no. 1, pp. 34-48, 2012.
12. K. Jansen, “An approximation algorithm for the license and shift class design problem”, European Journal of Operational Research vol. 73, pp. 127-131, 1994.
13. L.G. Kroon, M. Salomon and L.N. Van Wassenhove, “Exact and approximation algorithms for the tactical fixed interval scheduling problem”, Operations Research vol. 45, no. 4, pp. 624-638, 1997.
14. A.W.J. Kolen, J.K. Lenstra, C.H. Papadimitriou and F.C.R. Spieksma, “Interval Scheduling: A Survey”, Naval Research Logistics vol. 54, no. 5, pp. 530-543, 2007.
15. K. Nurmi, N. Kyngäs and J. Kyngäs, "Workforce Optimization: the General Task-based Shift Generation Problem", IAENG International Journal of Applied Mathematics, vol. 49, no. 4, pp. 393-400, 2019.
16. N. Kyngäs, K. Nurmi and D. Goossens, “The General Task-based Shift Generation Problem: Formulation and Benchmarks”, Proceedings of the 9th Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA), pp. 301-319, 2019.
17. P. Smet, T. Wauters, M. Mihaylov and G. Vanden Berghe, “The shift minimization personnel task scheduling problem: A new hybrid approach and computational insights”, Omega vol. 46, pp. 64-73, 2014.
18. J.G. Fages and T. Lapegue, “Filtering Atmostnvalue with Difference Constraints: Application to the Shift Minimisation Personnel Task Scheduling Problem”, Lecture Notes in Computer Science, vol. 8124, pp. 63-79, 2013.
19. S.-W. Lin and K.-C. Ying, “Minimizing Shifts for Personnel task Scheduling Problems: A three-Phase Algorithm”, European Journal of Operational Research vol. 237, pp. 323-334, 2014.
20. M. Hojati, “A greedy heuristic for shift minimization personnel task scheduling problem”, Computers and Operations Research vol. 100, pp. 66-76, 2018.
21. R. Chirayil Chandrasekharan, P. Smet, and T. Wauters, “An automatic constructive matheuristic for the shift minimization personnel task scheduling problem”, J Heuristics, Feb. 2020, http://dx.doi.org/10.1007/s10732-020-09439-9.
22. O. Solyali, “The Shift Minimization Personnel Task Scheduling Problem: An Effective Lower Bounding Procedure”, Hacettepe Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, vol. 34, no. 2, Jun. 2016, http://dx.doi.org/10.17065/huniibf.259136.
23. T. Lapègue: “Personnel Task Scheduling Problem Library", [Online]. Available: https://sites.google.com/site/ptsplib/smptsp/instances, (Last access 15-January-2021).
24. K. Nurmi: “The General Task-based Shift Generation Problem - Benchmark Instances", [Online]. Available: http://web.samk.fi/public/tkiy/GTSGP/, (Last update 26-July-2021).
25. K. Sörensen, M. Sevaux and F. Glover, “A History of Metaheuristics”, In: R. Martí, P. Pardalos and M. Resende (eds) Handbook of Heuristics, pp. 791-808, 2018.

Uwagi

1. Preface

2. Session: 14th International Workshop on Computational Optimization

3. Communication Papers

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-a54a1218-b9ca-4b16-91f7-27679664d869