{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T13:02:26Z","timestamp":1779195746672,"version":"3.51.4"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Evol. Learn. Optim."],"published-print":{"date-parts":[[2025,12,31]]},"abstract":"<jats:p>\n                    This study addresses large-scale personnel scheduling problems in the service industry by combining mathematical programming with data mining techniques to enhance efficiency. The studied problem aims at efficiently scheduling skilled employees over a one-week planning horizon, minimizing costs while meeting diverse job demands. In service industries, shift planning is intricately tied to customer presence, leading to a multitude of potential shifts and a difficult optimization problem that cannot be easily solved using a commercial mixed-integer programming solver. Nevertheless, these problems are categorized as recurrent problems, where distinct instances share common characteristics and solution structures that differ only in a few parameters over time. We propose to use a data mining technique, namely, the\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(k\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -nearest neighbors algorithm, to expedite the solution process while upholding solution quality. We suggest using schedules of past solutions to reduce the problem size. Thus, for an upcoming instance, we identify similar historical instances and streamline the enumeration of shifts to align with the comparable historical instances\u2019 schedules. This approach allows us to solve the problem using a commercial solver within a reasonable timeframe while preserving solution quality. Moreover, our methodology offers decision-makers the flexibility to determine the extent to which they wish to scale down the problem. Our experiments conducted on instances generated from real historical data with up to 12 jobs and 252 employees, yield an average removal of up to 85.5% of decision variables. This resulted in an average speedup factor of up to 15.5, with a marginal average cost increase of approximately 1.2%.\n                  <\/jats:p>","DOI":"10.1145\/3709013","type":"journal-article","created":{"date-parts":[[2024,12,20]],"date-time":"2024-12-20T10:13:58Z","timestamp":1734689638000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Data Mining-Driven Shift Enumeration for Accelerating the Solution of Large-Scale Personnel Scheduling Problems"],"prefix":"10.1145","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0367-410X","authenticated-orcid":false,"given":"Farin","family":"Rastgar-Amini","sequence":"first","affiliation":[{"name":"Department of Mathematics and Industrial Engineering, Polytechnique Montreal, Montreal, QC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9876-2921","authenticated-orcid":false,"given":"Daniel","family":"Aloise","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering and Software Engineering, Polytechnique Montreal, Montreal, QC, Canada and GERAD, Montreal, QC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7595-3904","authenticated-orcid":false,"given":"Claudio","family":"Contardo","sequence":"additional","affiliation":[{"name":"Department of Mechanical, Industrial and Aerospace Engineering, Concordia University, Montreal, QC, Canada and GERAD, Montreal, QC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4469-9813","authenticated-orcid":false,"given":"Guy","family":"Desaulniers","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Industrial Engineering, Polytechnique Montreal, Montreal, QC, Canada and GERAD, Montreal, QC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,12,6]]},"reference":[{"key":"e_1_3_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00170-013-5354-6"},{"key":"e_1_3_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2778285"},{"issue":"4","key":"e_1_3_1_4_1","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/s13675-019-00119-3","article-title":"A decomposition-based heuristic for large employee scheduling problems with inter-department transfers","volume":"7","author":"Attia Dalia","year":"2019","unstructured":"Dalia Attia, Reinhard B\u00fcrgy, Guy Desaulniers, and Fran\u00e7ois Soumis. 2019. A decomposition-based heuristic for large employee scheduling problems with inter-department transfers. EURO Journal on Computational Optimization 7, 4 (2019), 325\u2013357.","journal-title":"EURO Journal on Computational Optimization"},{"key":"e_1_3_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2020.07.063"},{"key":"e_1_3_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1198399"},{"key":"e_1_3_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1967.1053964"},{"issue":"3","key":"e_1_3_1_8_1","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1287\/opre.2.3.339","article-title":"Letter to the editor\u2014a comment on Edie\u2019s \u201ctraffic delays at toll booths\u201d","volume":"2","author":"Dantzig George B","year":"1954","unstructured":"George B Dantzig. 1954. Letter to the editor\u2014a comment on Edie\u2019s \u201ctraffic delays at toll booths\u201d. Journal of the Operations Research Society of America 2, 3 (1954), 339\u2013341.","journal-title":"Journal of the Operations Research Society of America"},{"key":"e_1_3_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tre.2011.08.001"},{"key":"e_1_3_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-78230-6_26"},{"key":"e_1_3_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2016.03.035"},{"key":"e_1_3_1_12_1","article-title":"Exact combinatorial optimization with graph convolutional neural networks","volume":"32","author":"Gasse Maxime","year":"2019","unstructured":"Maxime Gasse, Didier Ch\u00e9telat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. 2019. Exact combinatorial optimization with graph convolutional neural networks. Advances in Neural Information Processing Systems 32 (2019).","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_1_13_1","first-page":"65","article-title":"Efficiently using prefix-trees in mining frequent itemsets","volume":"90","author":"Grahne G\u00f6sta","year":"2003","unstructured":"G\u00f6sta Grahne and Jianfei Zhu. 2003. Efficiently using prefix-trees in mining frequent itemsets. In FIMI, Vol. 90. 65.","journal-title":"FIMI"},{"key":"e_1_3_1_14_1","doi-asserted-by":"crossref","first-page":"1116","DOI":"10.1109\/WSC57314.2022.10015405","volume-title":"2022 Winter Simulation Conference (WSC)","author":"Guastalla Alberto","year":"2022","unstructured":"Alberto Guastalla, Emilio Sulis, Roberto Aringhieri, Stefano Branchi, Chiara Di Francescomarino, and Chiara Ghidini. 2022. Workshift scheduling using optimization and process mining techniques: An application in healthcare. In 2022 Winter Simulation Conference (WSC). IEEE, 1116\u20131127."},{"key":"e_1_3_1_15_1","first-page":"1","article-title":"A parallel ruin and recreate heuristic for personnel scheduling in a flexible working environment","author":"Hassani Rachid","year":"2023","unstructured":"Rachid Hassani, Guy Desaulniers, and Issmail El Hallaoui. 2023. A parallel ruin and recreate heuristic for personnel scheduling in a flexible working environment. Forthcoming in: Journal of Scheduling (2023), 1\u201318.","journal-title":"Forthcoming in: Journal of Scheduling"},{"key":"e_1_3_1_16_1","doi-asserted-by":"crossref","first-page":"1099","DOI":"10.1109\/IADCC.2015.7154874","volume-title":"2015 IEEE International Advance Computing Conference (IACC)","author":"Jamsheela O.","year":"2015","unstructured":"O. Jamsheela and G. Raju. 2015. Frequent itemset mining algorithms: A literature survey. In 2015 IEEE International Advance Computing Conference (IACC). IEEE, 1099\u20131104."},{"key":"e_1_3_1_17_1","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/11890584_5","volume-title":"International Workshop on Hybrid Metaheuristics","author":"Jourdan Laetitia","year":"2006","unstructured":"Laetitia Jourdan, Clarisse Dhaenens, and El-Ghazali Talbi. 2006. Using datamining techniques to help metaheuristics: A short survey. In International Workshop on Hybrid Metaheuristics. Springer, 57\u201369."},{"key":"e_1_3_1_18_1","first-page":"2314","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","volume":"33","author":"Lauri Juho","year":"2019","unstructured":"Juho Lauri and Sourav Dutta. 2019. Fine-grained search space classification for Hard enumeration variants of subset problems. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33. 2314\u20132321."},{"key":"e_1_3_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10489-010-0270-z"},{"key":"e_1_3_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejtl.2020.100023"},{"key":"e_1_3_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11750-017-0451-6"},{"key":"e_1_3_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.22213"},{"key":"e_1_3_1_23_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2021.1045"},{"key":"e_1_3_1_24_1","unstructured":"Mouad Morabit Guy Desaulniers and Andrea Lodi. 2022. Learning to repeatedly solve routing problems. [arxiv]2212.08101 [math.OC] Retrieved from https:\/\/arxiv.org\/abs\/2212.08101"},{"issue":"6","key":"e_1_3_1_25_1","doi-asserted-by":"crossref","first-page":"1695","DOI":"10.1142\/S0219622020300050","article-title":"A systematic literature review for personnel scheduling problems","volume":"19","author":"\u00d6zder Emir H\u00fcseyin","year":"2020","unstructured":"Emir H\u00fcseyin \u00d6zder, Evrencan \u00d6zcan, Tamer Eren, et al. 2020. A systematic literature review for personnel scheduling problems. International Journal of Information Technology & Decision Making 19, 6 (2020), 1695\u20131735.","journal-title":"International Journal of Information Technology & Decision Making"},{"key":"e_1_3_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2017.09.051"},{"key":"e_1_3_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2078195"},{"key":"e_1_3_1_28_1","first-page":"2352","article-title":"Dataset for solving a hybrid flexibility strategy on personnel scheduling problem in the retail industry","volume":"32","author":"Porto Andr\u00e9s Felipe","year":"2020","unstructured":"Andr\u00e9s Felipe Porto, C\u00e9Sar augusto henao, h\u00e9ctor l\u00f3Pez-ospina, esneyder rafael gonz\u00e1Lez, and Virginia i. Gonz\u00e1lez. 2020. Dataset for solving a hybrid flexibility strategy on personnel scheduling problem in the retail industry. Data in Brief 32 (2020), 106066. 2352\u20133409","journal-title":"Data in Brief"},{"key":"e_1_3_1_29_1","first-page":"24","volume-title":"Learning to enumerate shifts for large-scale flexible personnel scheduling problems","author":"Rastgar Farin","year":"2022","unstructured":"Farin Rastgar, Claudio Contardo, Guy Desaulniers, and Maxime Gasse. 2022. Learning to enumerate shifts for large-scale flexible personnel scheduling problems. Les Cahiers du GERAD G-2022-29. HEC Montr\u00e9al, Canada. 24 pages."},{"issue":"1","key":"e_1_3_1_30_1","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1023\/B:ANOR.0000019101.29692.2c","article-title":"Using benders decomposition to implicitly model Tour scheduling","volume":"128","author":"Rekik Monia","year":"2004","unstructured":"Monia Rekik, Jean-Fran\u00e7ois cordeau, and Fran\u00e7ois soumis. 2004. Using benders decomposition to implicitly model Tour scheduling. Annals of Operations Research 128, 1\u20134 (2004), 111\u2013133.","journal-title":"Annals of Operations Research"},{"key":"e_1_3_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2018.01.014"},{"issue":"1","key":"e_1_3_1_32_1","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1109\/TEVC.2012.2185847","article-title":"Objective reduction in Many-objective optimization: Linear and nonlinear algorithms","volume":"17","author":"Saxena Dhish Kumar","year":"2012","unstructured":"Dhish Kumar Saxena, Joao A Duro, Ashutosh Tiwari, Kalyanmoy Deb, and Qingfu Zhang. 2012. Objective reduction in Many-objective optimization: Linear and nonlinear algorithms. IEEE Transactions on Evolutionary Computation 17, 1 (2012), 77\u201399.","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"e_1_3_1_33_1","article-title":"Machine learning for large-scale optimization in 6g wireless networks","author":"Shi Yandong","year":"2023","unstructured":"Yandong Shi, Lixiang Lian, Yuanming Shi, Zixin Wang, Yong Zhou, Liqun Fu, Lin Bai, Jun Zhang, and Wei Zhang. 2023. Machine learning for large-scale optimization in 6g wireless networks. IEEE Communications Surveys & Tutorials (2023).","journal-title":"IEEE Communications Surveys & Tutorials"},{"key":"e_1_3_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3459664"},{"key":"e_1_3_1_35_1","first-page":"9367","volume-title":"International Conference on Machine Learning","author":"Tang Yunhao","year":"2020","unstructured":"Yunhao Tang, Shipra Agrawal, and Yuri Faenza. 2020. Reinforcement learning for integer programming: Learning to cut. In International Conference on Machine Learning. PMLR, 9367\u20139376."},{"key":"e_1_3_1_36_1","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1137\/1.9781611977042.15","volume-title":"2022 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX)","author":"Tayebi Dena","year":"2022","unstructured":"Dena Tayebi, Saurabh Ray, and Deepak Ajwani. 2022. Learning to prune instances of k-median and related problems. In 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX). SIAM, 184\u2013194."},{"issue":"3","key":"e_1_3_1_37_1","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1016\/j.ejor.2012.11.029","article-title":"Personnel scheduling: A literature review","volume":"226","author":"Bergh Jorne Van den","year":"2013","unstructured":"Jorne Van den Bergh, Jeroen Beli\u00ebn, Philippe De Bruecker, Erik Demeulemeester, and Liesje De Boeck. 2013. Personnel scheduling: A literature review. European Journal of Operational Research 226, 3 (2013), 367\u2013385.","journal-title":"European Journal of Operational Research"},{"key":"e_1_3_1_38_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1120.1048"},{"key":"e_1_3_1_39_1","volume-title":"New Developments in Unsupervised Outlier Detection: Algorithms and Applications","author":"Wang Xiaochun","year":"2020","unstructured":"Xiaochun Wang, Xiali Wang, and Mitch Wilkes. 2020. New Developments in Unsupervised Outlier Detection: Algorithms and Applications. Springer."},{"issue":"3","key":"e_1_3_1_40_1","first-page":"376","article-title":"Learning to decompose: A paradigm for decomposition-based multiobjective optimization","volume":"23","author":"Wu Mengyuan","year":"2018","unstructured":"Mengyuan Wu, Ke Li, Sam Kwong, Qingfu Zhang, and Jun Zhang. 2018. Learning to decompose: A paradigm for decomposition-based multiobjective optimization. IEEE Transactions on Evolutionary Computation 23, 3 (2018), 376\u2013390.","journal-title":"IEEE Transactions on Evolutionary Computation"},{"issue":"2","key":"e_1_3_1_41_1","first-page":"739","article-title":"Learning to solve large-scale security-constrained unit commitment problems","volume":"33","author":"Xavier \u00c1linson S","year":"2020","unstructured":"\u00c1linson S Xavier, Feng Qiu, and Shabbir Ahmed. 2020. Learning to solve large-scale security-constrained unit commitment problems. INFORMS Journal on Computing 33, 2 (2020), 739\u2013756.","journal-title":"INFORMS Journal on Computing"},{"issue":"4","key":"e_1_3_1_42_1","first-page":"958","volume":"64","author":"Xu Huan","year":"2016","unstructured":"Huan Xu, Constantine Caramanis, and Shie Mannor. 2016. Statistical optimization in high dimensions. Operations Research 64, 4 (2016), 958\u2013979.","journal-title":"Statistical optimization in high dimensions"},{"issue":"3","key":"e_1_3_1_43_1","doi-asserted-by":"crossref","first-page":"1503","DOI":"10.1109\/TSMC.2020.3027860","article-title":"Frequent pattern-based search: A case study on the quadratic assignment problem","volume":"52","author":"Zhou Yangming","year":"2020","unstructured":"Yangming Zhou, Jin-Kao Hao, and B\u00e9atrice Duval. 2020. Frequent pattern-based search: A case study on the quadratic assignment problem. IEEE Transactions on Systems, Man, and Cybernetics: Systems 52, 3 (2020), 1503\u20131515.","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics:"},{"issue":"1","key":"e_1_3_1_44_1","first-page":"39","volume":"36","author":"Zhou Yangming","year":"2024","unstructured":"Yangming Zhou, Jiaqi Li, Jin-Kao Hao, and Fred Glover. 2024. Detecting critical nodes in sparse graphs via \u201creduce-solve-combine\u201d memetic search. INFORMS Journal on Computing 36, 1 (2024), 39\u201360.","journal-title":"Detecting critical nodes in sparse graphs via \u201creduce-solve-combine\u201d memetic search"}],"container-title":["ACM Transactions on Evolutionary Learning and Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3709013","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T12:26:51Z","timestamp":1765024011000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709013"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,6]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1145\/3709013"],"URL":"https:\/\/doi.org\/10.1145\/3709013","relation":{},"ISSN":["2688-299X","2688-3007"],"issn-type":[{"value":"2688-299X","type":"print"},{"value":"2688-3007","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,6]]},"assertion":[{"value":"2023-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-09","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}