{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:54:38Z","timestamp":1762325678466,"version":"3.37.3"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,7,22]],"date-time":"2023-07-22T00:00:00Z","timestamp":1689984000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,22]],"date-time":"2023-07-22T00:00:00Z","timestamp":1689984000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["398911053"],"award-info":[{"award-number":["398911053"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100014690","name":"Ministerium f\u00fcr Kultur und Wissenschaft des Landes Nordrhein-Westfalen","doi-asserted-by":"publisher","award":["NRW Return Programme"],"award-info":[{"award-number":["NRW Return Programme"]}],"id":[{"id":"10.13039\/501100014690","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2024,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper presents new mixed-integer linear programming formulations for multi-activity shift scheduling problems (MASSP). In these formulations, the rules governing shift feasibility are encoded in block-based state-expanded networks in which nodes are associated with states and arcs represent assignments of blocks of work or break periods inducing state transitions. A key advantage of these formulations is that for the anonymous MASSP in which all employees are considered as equal only a single network with integer flow variables is needed as long as the network encodes all shift composition rules. A challenging aspect is that the networks can become very large, yielding huge models that are hard to solve for large problem instances. To address this challenge, this paper proposes two exact modeling techniques that substantially reduce the size of the model instances: First, it introduces a set of aggregate side constraints enforcing that an integer flow solution can be decomposed into paths representing feasible shifts. Second, it proposes to decouple the shift composition from the assignment of concrete activities to blocks of work periods, thereby removing a large amount of symmetry from the original model. In a computational study with two MASSP instance sets from the literature dealing with shift scheduling problems, we demonstrate the effectiveness of these techniques for reducing the both size of the model instances and the solution time: We are able to solve all instances, including more than 70 previously open instances, to optimality\u2013the vast majority of them in less than 30\u00a0min on a notebook computer.<\/jats:p>","DOI":"10.1007\/s10951-023-00789-3","type":"journal-article","created":{"date-parts":[[2023,7,22]],"date-time":"2023-07-22T15:01:18Z","timestamp":1690038078000},"page":"341-361","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Block-based state-expanded network models for multi-activity shift scheduling"],"prefix":"10.1007","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8369-7939","authenticated-orcid":false,"given":"Michael","family":"R\u00f6mer","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,7,22]]},"reference":[{"issue":"11","key":"789_CR1","doi-asserted-by":"publisher","first-page":"1339","DOI":"10.1287\/mnsc.36.11.1339","volume":"36","author":"SE Bechtold","year":"1990","unstructured":"Bechtold, S. E., & Jacobs, L. W. (1990). Implicit modeling of flexible break assignments in optimal shift scheduling. Management Science, 36(11), 1339\u20131351. https:\/\/doi.org\/10.1287\/mnsc.36.11.1339","journal-title":"Management Science"},{"issue":"1","key":"789_CR2","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/s10601-009-9083-2","volume":"16","author":"MC C\u00f4t\u00e9","year":"2011","unstructured":"C\u00f4t\u00e9, M. C., Gendron, B., Quimper, C. G., et al. (2011). Formal languages for integer programming modeling of shift scheduling problems. Constraints, 16(1), 54\u201376. https:\/\/doi.org\/10.1007\/s10601-009-9083-2","journal-title":"Constraints"},{"issue":"1","key":"789_CR3","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1287\/mnsc.1100.1264","volume":"57","author":"MC C\u00f4t\u00e9","year":"2011","unstructured":"C\u00f4t\u00e9, M. C., Gendron, B., & Rousseau, L. M. (2011). Grammar-based integer programming models for multiactivity shift scheduling. Management Science, 57(1), 151\u2013163. https:\/\/doi.org\/10.1287\/mnsc.1100.1264","journal-title":"Management Science"},{"issue":"3","key":"789_CR4","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1287\/ijoc.1120.0514","volume":"25","author":"MC C\u00f4t\u00e9","year":"2013","unstructured":"C\u00f4t\u00e9, M. C., Gendron, B., & Rousseau, L. M. (2013). Grammar-based column generation for personalized multi-activity shift scheduling. INFORMS Journal on Computing, 25(3), 461\u2013474. https:\/\/doi.org\/10.1287\/ijoc.1120.0514","journal-title":"INFORMS Journal on Computing"},{"issue":"3","key":"789_CR5","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/s10951-017-0544-y","volume":"21","author":"S Dahmen","year":"2018","unstructured":"Dahmen, S., Rekik, M., & Soumis, F. (2018). An implicit model for multi-activity shift scheduling problems. Journal of Scheduling, 21(3), 285\u2013304. https:\/\/doi.org\/10.1007\/s10951-017-0544-y","journal-title":"Journal of Scheduling"},{"issue":"3","key":"789_CR6","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1287\/opre.2.3.339","volume":"2","author":"GB Dantzig","year":"1954","unstructured":"Dantzig, G. B. (1954). Letter to the editor\u2013a comment on Edie\u2019s \u201ctraffic delays at toll booths\u2019\u2019. Journal of the Operations Research Society of America, 2(3), 339\u2013341. https:\/\/doi.org\/10.1287\/opre.2.3.339","journal-title":"Journal of the Operations Research Society of America"},{"key":"789_CR7","doi-asserted-by":"publisher","unstructured":"Demassey, S., Pesant, G., & Rousseau, L.M. (2005). Constraint programming based column generation for employee timetabling. In: Bart\u00e1k, R., & Milano, M. (eds) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Springer, Berlin, Heidelberg, Lecture Notes in Computer Science, pp 140\u2013154, https:\/\/doi.org\/10.1007\/11493853_12","DOI":"10.1007\/11493853_12"},{"issue":"4","key":"789_CR8","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/s10601-006-9003-7","volume":"11","author":"S Demassey","year":"2006","unstructured":"Demassey, S., Pesant, G., & Rousseau, L. M. (2006). A cost-regular based hybrid column generation approach. Constraints, 11(4), 315\u2013333. https:\/\/doi.org\/10.1007\/s10601-006-9003-7","journal-title":"Constraints"},{"issue":"3","key":"789_CR9","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1016\/j.ejor.2018.07.010","volume":"272","author":"NA Hern\u00e1ndez-Leandro","year":"2019","unstructured":"Hern\u00e1ndez-Leandro, N. A., Boyer, V., Salazar-Aguilar, M. A., et al. (2019). A matheuristic based on Lagrangian relaxation for the multi-activity shift scheduling problem. European Journal of Operational Research, 272(3), 859\u2013867. https:\/\/doi.org\/10.1016\/j.ejor.2018.07.010","journal-title":"European Journal of Operational Research"},{"key":"789_CR10","doi-asserted-by":"publisher","unstructured":"Mellouli, T. (2001). A network flow approach to crew scheduling based on an analogy to a train\/aircraft maintenance routing problem. In: Voss, S., & Daduna, J. (eds) Computer-Aided Scheduling of Public Transport, Lecture Notes in Economics and Mathematical Systems, vol 505. Springer, Berlin, pp 91\u2013120, https:\/\/doi.org\/10.1007\/978-3-642-56423-9_6","DOI":"10.1007\/978-3-642-56423-9_6"},{"key":"789_CR11","doi-asserted-by":"publisher","unstructured":"Porrmann, T., & R\u00f6mer, M. (2021). Learning to reduce state-expanded networks for multi-activity shift scheduling. In: Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Lecture Notes in Computer Science, vol 12735. Springer-Verlag, Berlin, Heidelberg, pp 383\u2013391, https:\/\/doi.org\/10.1007\/978-3-030-78230-6_24","DOI":"10.1007\/978-3-030-78230-6_24"},{"issue":"3","key":"789_CR12","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/s10732-009-9106-6","volume":"16","author":"CG Quimper","year":"2010","unstructured":"Quimper, C. G., & Rousseau, L. M. (2010). A large neighbourhood search approach to the multi-activity shift scheduling problem. Journal of Heuristics, 16(3), 373\u2013392. https:\/\/doi.org\/10.1007\/s10732-009-9106-6","journal-title":"Journal of Heuristics"},{"issue":"1","key":"789_CR13","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1016\/j.ijpe.2012.06.030","volume":"140","author":"MI Restrepo","year":"2012","unstructured":"Restrepo, M. I., Lozano, L., & Medaglia, A. L. (2012). Constrained network-based column generation for the multi-activity shift scheduling problem. International Journal of Production Economics, 140(1), 466\u2013472. https:\/\/doi.org\/10.1016\/j.ijpe.2012.06.030","journal-title":"International Journal of Production Economics"},{"key":"789_CR14","unstructured":"R\u00f6mer, M., & Mellouli, T. (2016). A direct MILP approach based on state-expanded network flows and anticipation for multi-stage nurse rostering under uncertainty. In: Burke, E.K., Di\u00a0Gaspero, L., \u00d6zcan, E., et\u00a0al (eds) PATAT 2016: Proceedings of the 11th International Conference of the Practice and Theory of Automated Timetabling, Udine, Italy, pp 549\u2013552"},{"key":"789_CR15","doi-asserted-by":"publisher","unstructured":"Van den Bergh, J., Beli\u00ebn, J., De Bruecker, P., et al. (2013). Personnel scheduling: A literature review. European Journal of Operational Research, 226(3), 367\u2013385. https:\/\/doi.org\/10.1016\/j.ejor.2012.11.029","DOI":"10.1016\/j.ejor.2012.11.029"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-023-00789-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-023-00789-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-023-00789-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,9]],"date-time":"2024-08-09T13:35:41Z","timestamp":1723210541000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-023-00789-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,22]]},"references-count":15,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["789"],"URL":"https:\/\/doi.org\/10.1007\/s10951-023-00789-3","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"type":"print","value":"1094-6136"},{"type":"electronic","value":"1099-1425"}],"subject":[],"published":{"date-parts":[[2023,7,22]]},"assertion":[{"value":"7 June 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 July 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author has no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}