{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T23:39:18Z","timestamp":1743118758734,"version":"3.40.3"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031810091"},{"type":"electronic","value":"9783031810107"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-81010-7_11","type":"book-chapter","created":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T04:52:19Z","timestamp":1740459139000},"page":"153-170","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Study on the Hardness of the Shift Minimization Personnel Task Scheduling Problem"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8278-9874","authenticated-orcid":false,"given":"Kimmo","family":"Nurmi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Reshma","family":"Chandrasekharan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jari","family":"Kyng\u00e4s","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nico","family":"Kyng\u00e4s","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,2,26]]},"reference":[{"issue":"1","key":"11_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0377-2217(03)00095-X","volume":"153","author":"AT Ernst","year":"2004","unstructured":"Ernst, A.T., Jiang, H., Krishnamoorthy, M., Sier, D.: Staff scheduling and rostering: a review of applications, methods and models. Eur. J. Oper. Res. 153(1), 3\u201327 (2004)","journal-title":"Eur. J. Oper. Res."},{"issue":"4","key":"11_CR2","first-page":"393","volume":"49","author":"K Nurmi","year":"2019","unstructured":"Nurmi, K., Kyng\u00e4s, N., Kyng\u00e4s, J.: Workforce optimization: the general task-based shift generation problem. IAENG Int. J. Appl. Math. 49(4), 393\u2013400 (2019)","journal-title":"IAENG Int. J. Appl. Math."},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"Nurmi, K., Kyng\u00e4s, J., Kyng\u00e4s, N.: The effects of shift generation on staff rostering. In: Proceedings of the 6th International Conference on Dynamics of Information Systems (DIS), 2023","DOI":"10.1007\/978-3-031-50320-7_15"},{"issue":"1","key":"11_CR4","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s10479-007-0221-1","volume":"155","author":"L Di Gaspero","year":"2007","unstructured":"Di Gaspero, L., G\u00e4rtner, J., Kortsarz, G., Musliu, N., Schaerf, A., Slany, W.: The minimum shift design problem. Ann. Oper. Res. 155(1), 79\u2013105 (2007)","journal-title":"Ann. Oper. Res."},{"key":"11_CR5","unstructured":"Michael, R.G., David, S.J.: Computers and Intractability: A Guide to the Theory of NP-completeness. A Series of Books in the Mathematical Sciences. W. H. Freeman, San Francisco  (1979)"},{"issue":"1","key":"11_CR6","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/0377-2217(93)E0335-U","volume":"82","author":"LG Kroon","year":"1995","unstructured":"Kroon, L.G., Salomon, M., Van Wassenhove, L.N.: Exact and approximation algorithms for the operational fixed interval scheduling problem. Eur. J. Oper. Res. 82(1), 190\u2013205 (1995)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"11_CR7","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0377-2217(03)00098-5","volume":"153","author":"N Musliu","year":"2004","unstructured":"Musliu, N., Schaerf, A., Slany, W.: Local search for shift design. Eur. J. Oper. Res. 153(1), 51\u201364 (2004)","journal-title":"Eur. J. Oper. Res."},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Kyng\u00e4s, N., Nurmi, K., Kyng\u00e4s, J.: Solving the person-based multitask shift generation problem with breaks . In: Proceedings of the 5th International Conference On Modeling, Simulation And Applied Optimization (ICMSAO), pp. 1\u20138, Hammamet, Tunis, 2013","DOI":"10.1109\/ICMSAO.2013.6552670"},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"Kyng\u00e4s, N., Goossens, D., Nurmi, K., Kyng\u00e4s, J.: Optimizing the Unlimited Shift Generation Problem, Applications of Evolutionary Computation, Lecture Notes in Computer Science, vol. 7248, pp 508\u2013518, 2012","DOI":"10.1007\/978-3-642-29178-4_51"},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"Liu, S., Zhang, T., Feng, P., Zheng, Y., Chen, W.: Hierarchical staffing problem by shift design in nursing homes: a two-stage method. In: Proceedings of the 16th International Conference on Automation Science and Engineering (CASE), pp. 1013\u20131018 (2020)","DOI":"10.1109\/CASE48305.2020.9216768"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Smet, P., Lejon, A.,  Vanden Berghe, G.: Demand smoothing in shift design. Flex. Serv. Manuf. J. (2020)","DOI":"10.1007\/s10696-020-09380-w"},{"issue":"3","key":"11_CR12","doi-asserted-by":"publisher","first-page":"1051","DOI":"10.1016\/j.ejor.2019.07.068","volume":"280","author":"S Dahmen","year":"2020","unstructured":"Dahmen, S., Rekik, M., Soumis, F., Desaulniers, G.: A two-stage solution approach for personalized multi-department multi-day shift scheduling. Eur. J. Oper. Res. 280(3), 1051\u20131063 (2020)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"11_CR13","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.ejor.2011.11.034","volume":"219","author":"M Krishnamoorthy","year":"2012","unstructured":"Krishnamoorthy, M., Ernst, A.T., Baatar, D.: Algorithms for large scale shift minimisation personnel task scheduling problems. Eur. J. Oper. Res. 219(1), 34\u201348 (2012)","journal-title":"Eur. J. Oper. Res."},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0377-2217(94)90150-3","volume":"73","author":"K Jansen","year":"1994","unstructured":"Jansen, K.: An approximation algorithm for the license and shift class design problem. Eur. J. Oper. Res. 73, 127\u2013131 (1994)","journal-title":"Eur. J. Oper. Res."},{"key":"11_CR15","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/0377-2217(95)00355-X","volume":"90","author":"V Valls","year":"1996","unstructured":"Valls, V., Perez, A., Quintanilla, S.: A graph colouring model for assigning a heterogeneous workforce to a given schedule. Eur. J. Oper. Res. 90, 285\u2013302 (1996)","journal-title":"Eur. J. Oper. Res."},{"issue":"5","key":"11_CR16","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1002\/nav.20231","volume":"54","author":"AWJ Kolen","year":"2007","unstructured":"Kolen, A.W.J., Lenstra, J.K., Papadimitriou, C.H., Spieksma, F.C.R.: Interval scheduling: a survey. Nav. Res. Logist. 54(5), 530\u2013543 (2007)","journal-title":"Nav. Res. Logist."},{"issue":"24","key":"11_CR17","doi-asserted-by":"publisher","first-page":"7286","DOI":"10.1080\/00207543.2015.1037023","volume":"53","author":"D Prot","year":"2015","unstructured":"Prot, D., Lapegue, T., Bellenguez-Morineau, O.: A two-phase method for the shift design and personnel task scheduling problem with equity objective. Int. J. Prod. Res. 53(24), 7286\u20137298 (2015)","journal-title":"Int. J. Prod. Res."},{"key":"11_CR18","doi-asserted-by":"crossref","unstructured":"Kyng\u00e4s, N., Nurmi, K.: The extended shift minimization personnel task scheduling problem, Position and Communication Papers of the 16th Conference on Computer Science and Intelligence Systems, vol. 26, pp. 65\u201374, 2021","DOI":"10.15439\/2021F35"},{"key":"11_CR19","doi-asserted-by":"crossref","unstructured":"Kyng\u00e4s, N., Nurmi, K.: Finding optimum solutions to the shift minimization personnel task scheduling problem with a new pack-based approach. In: Proceedings of the 8th International Conference on Mathematics and Computers in Sciences and Industry (MCSI), 2023","DOI":"10.1109\/MCSI60294.2023.00018"},{"key":"11_CR20","doi-asserted-by":"publisher","unstructured":"Chirayil Chandrasekharan, R., Smet, P., Wauters, T.: An automatic constructive matheuristic for the shift minimization personnel task scheduling problem. J. Heurist. (2020). https:\/\/doi.org\/10.1007\/s10732-020-09439-9","DOI":"10.1007\/s10732-020-09439-9"},{"key":"11_CR21","doi-asserted-by":"crossref","unstructured":"Nurmi, K., Kyng\u00e4s, N.: A successful three-phase metaheuristic for the shift minimization personal task scheduling problem. Adv. Oper. Res. 2021, Article ID 8876990 (2021)","DOI":"10.1155\/2021\/8876990"},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"Solyali, O.: The shift minimization personnel task scheduling problem: an effective lower bounding procedure. Hacettepe \u00dcniversitesi \u0130ktisadi ve \u0130dari Bilimler Fak\u00fcltesi Dergisi 34(2) (2016)","DOI":"10.17065\/huniibf.259136"},{"key":"11_CR23","doi-asserted-by":"crossref","unstructured":"Smet, P., Wauters, T., Mihaylov, M., Vanden Berghe, G.: The shift minimisation personnel task scheduling problem: a new hybrid approach and computational insights. Omega 46, 64\u201373 (2014)","DOI":"10.1016\/j.omega.2014.02.003"},{"key":"11_CR24","first-page":"63","volume":"8124","author":"J-G Fages","year":"2013","unstructured":"Fages, J.-G., Lap\u00e8gue, T.: Filtering AtMostNValue with difference constraints: application to the shift minimisation personnel task scheduling problem. Princ. Pract. Constr. Program. 8124, 63\u201379 (2013)","journal-title":"Princ. Pract. Constr. Program."},{"key":"11_CR25","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.cor.2018.07.010","volume":"100","author":"M Hojati","year":"2018","unstructured":"Hojati, M.: A greedy heuristic for shift minimization personnel task scheduling problem. Comput. Oper. Res. 100, 66\u201376 (2018)","journal-title":"Comput. Oper. Res."},{"key":"11_CR26","unstructured":"Lapegue, T.: Personnel task scheduling problem library, https:\/\/sites.google.com\/site\/ptsplib\/smptsp\/instances. Accessed 21 Apr 2013"},{"key":"11_CR27","unstructured":"Nurmi, K.: The General Task-based Shift Generation Problem - Benchmark Instances. http:\/\/web.samk.fi\/public\/tkiy\/GTSGP\/. Accessed 4 Apr 2024"},{"key":"11_CR28","unstructured":"Kyng\u00e4s, N., Nurmi, K., Goossens, D.: The general task-based shift generation problem: formulation and benchmarks. In: Proceedings of the 9th Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA), pp. 301\u2013319, 2019"},{"key":"11_CR29","unstructured":"K. Smith-Miles, Matilda. https:\/\/matilda.unimelb.edu.au\/matilda\/showMobileHomePage. Accessed 9 Oct 2024"},{"issue":"3","key":"11_CR30","doi-asserted-by":"publisher","first-page":"841","DOI":"10.1016\/j.ejor.2021.12.009","volume":"301","author":"J Jooken","year":"2022","unstructured":"Jooken, J., Leyman, P., De Causmaecker, P.: A new class of hard problem instances for the 0\u20131 knapsack problem. Eur. J. Oper. Res. 301(3), 841\u2013854 (2022)","journal-title":"Eur. J. Oper. Res."},{"key":"11_CR31","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1287\/mnsc.45.3.414","volume":"45","author":"S Martello","year":"1999","unstructured":"Martello, S., Pisinger, D., Toth, P.: Dynamic programming and strong bounds for the 0\u20131 knapsack problem. Manag. Sci. 45, 414\u2013424 (1999)","journal-title":"Manag. Sci."},{"key":"11_CR32","unstructured":"\u201cWorkforce scheduling with Gurobi\u201d. https:\/\/www.gurobi.com\/jupyter_models\/workforce-scheduling\/. Accessed 9 Oct 2024"},{"key":"11_CR33","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1109\/4235.585893","volume":"1","author":"DH Wolpert","year":"1997","unstructured":"Wolpert, D.H., Macready, W.G.: No free lunch theorems for optimization. IEEE Trans. Evol. Comput. 1, 67\u201382 (1997)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"11_CR34","doi-asserted-by":"crossref","unstructured":"Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning Data Mining, Inference, and Prediction, Second Edition, Springer, 2009","DOI":"10.1007\/978-0-387-84858-7"},{"key":"11_CR35","doi-asserted-by":"crossref","unstructured":"Cristianini, N., Shawe-Taylor, J.: An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. Cambridge University Press, Cambridge (2000)","DOI":"10.1017\/CBO9780511801389"},{"key":"11_CR36","doi-asserted-by":"crossref","unstructured":"Hosmer, D.W., Lemeshow, S., Sturdivant, R.X.: Applied Logistic Regression, John Wiley Sons Inc., Hoboken (2013)","DOI":"10.1002\/9781118548387"}],"container-title":["Lecture Notes in Computer Science","Dynamics of Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-81010-7_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T04:54:32Z","timestamp":1740459272000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-81010-7_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031810091","9783031810107"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-81010-7_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"26 February 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"DIS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on the Dynamics of Information Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Kalamata","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 June 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 June 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"dis22024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/dis2024.ujep.cz\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}