Logo PTI Logo FedCSIS

Position and Communication Papers of the 16th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 26

The Extended Shift Minimization Personnel Task Scheduling Problem

,

DOI: http://dx.doi.org/10.15439/2021F35

Citation: Position and Communication Papers of the 16th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 26, pages 6574 ()

Full text

Abstract. Shift generation is the process of determining the tasks to be carried out in particular shifts. 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 using minimum number of employees. In the extended problem, 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 heuristic for existing and new benchmark instances. Our best solutions are available online.

References

  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.