{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,12]],"date-time":"2025-04-12T04:28:35Z","timestamp":1744432115667,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,9,13]],"date-time":"2021-09-13T00:00:00Z","timestamp":1631491200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,9,13]],"date-time":"2021-09-13T00:00:00Z","timestamp":1631491200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006012","name":"Christian Doppler Forschungsgesellschaft","doi-asserted-by":"publisher","award":["Christian Doppler Laboratory for Artificial Intelligence and Optimization for Planning and Scheduling"],"award-info":[{"award-number":["Christian Doppler Laboratory for Artificial Intelligence and Optimization for Planning and Scheduling"]}],"id":[{"id":"10.13039\/501100006012","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2023,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The Test Laboratory Scheduling Problem (TLSP) is a real-world scheduling problem that extends the well-known Resource-Constrained Project Scheduling Problem (RCPSP) by several new constraints. Most importantly, the jobs have to be assembled out of several smaller tasks by the solver, before they can be scheduled. In this paper, we introduce different metaheuristic solution approaches for this problem. We propose four new neighborhoods that modify the grouping of tasks. In combination with neighborhoods for scheduling, they are used by our metaheuristics to produce high-quality solutions for both randomly generated and real-world instances. In particular, Simulated Annealing managed to find solutions that are competitive with the best known results and improve upon the state-of-the-art for larger instances. The algorithm is currently used for the daily planning of a large real-world laboratory.<\/jats:p>","DOI":"10.1007\/s10951-021-00699-2","type":"journal-article","created":{"date-parts":[[2021,9,13]],"date-time":"2021-09-13T15:03:03Z","timestamp":1631545383000},"page":"457-477","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Local search approaches for the test laboratory scheduling problem with variable task grouping"],"prefix":"10.1007","volume":"26","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1166-3881","authenticated-orcid":false,"given":"Florian","family":"Mischek","sequence":"first","affiliation":[]},{"given":"Nysret","family":"Musliu","sequence":"additional","affiliation":[]},{"given":"Andrea","family":"Schaerf","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,9,13]]},"reference":[{"key":"699_CR1","doi-asserted-by":"crossref","unstructured":"Ahmeti, A., & Musliu, N. (2018). Min-conflicts heuristic for multi-mode resource-constrained projects scheduling. In: Proceedings of the Genetic and Evolutionary Computation Conference, ACM (pp. 237\u2013244).","DOI":"10.1145\/3205455.3205620"},{"key":"699_CR2","unstructured":"Ahmeti, A., & Musliu, N. (2021). Hybridizing constraint programming and meta-heuristics for multi-mode resource-constrained multiple projects scheduling problem. In Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling-PATAT (Vol. 1)."},{"key":"699_CR3","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1016\/j.ins.2016.09.010","volume":"373","author":"S Asta","year":"2016","unstructured":"Asta, S., Karapetyan, D., Kheiri, A., \u00d6zcan, E., & Parkes, A. J. (2016). Combining Monte\u2013Carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem. Information Sciences, 373, 476\u2013498. https:\/\/doi.org\/10.1016\/j.ins.2016.09.010","journal-title":"Information Sciences"},{"key":"699_CR4","doi-asserted-by":"crossref","unstructured":"Bai, R., Blazewicz, J., Burke, E. K., Kendall, G., & McCollum, B. (2012). A simulated annealing hyper-heuristic methodology for flexible decision support. 4OR, 10(1), 43\u201366.","DOI":"10.1007\/s10288-011-0182-8"},{"issue":"3","key":"699_CR5","doi-asserted-by":"publisher","first-page":"805","DOI":"10.1016\/j.ejor.2007.11.010","volume":"193","author":"JH Bartels","year":"2009","unstructured":"Bartels, J. H., & Zimmermann, J. (2009). Scheduling tests in automotive r&d projects. European Journal of Operational Research, 193(3), 805\u2013819. https:\/\/doi.org\/10.1016\/j.ejor.2007.11.010","journal-title":"European Journal of Operational Research"},{"key":"699_CR6","doi-asserted-by":"publisher","unstructured":"Bellenguez, O., & N\u00e9ron, E. (2005). Lower bounds for the multi-skill project scheduling problem with hierarchical levels of skills. In E. Burke & M. Trick (Eds.), Practice and theory of automated timetabling V (pp. 229\u2013243). Berlin: Springer. https:\/\/doi.org\/10.1007\/11593577_14.","DOI":"10.1007\/11593577_14"},{"key":"699_CR7","doi-asserted-by":"crossref","unstructured":"Brightwell, G., & Winkler, P. (1991). Counting linear extensions is #p-complete. In Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing (pp 175\u2013181).","DOI":"10.1145\/103418.103441"},{"issue":"1","key":"699_CR8","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0377-2217(98)00204-5","volume":"112","author":"P Brucker","year":"1999","unstructured":"Brucker, P., Drexl, A., M\u00f6hring, R., Neumann, K., & Pesch, E. (1999). Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research, 112(1), 3\u201341. https:\/\/doi.org\/10.1016\/S0377-2217(98)00204-5","journal-title":"European Journal of Operational Research"},{"key":"699_CR9","doi-asserted-by":"crossref","unstructured":"Danzinger, P., Geibinger, T., Mischek, F., & Musliu, N. (2020). Solving the test laboratory scheduling problem with variable task grouping. In: J.C. Beck, O. Buffet, J. Hoffmann, E. Karpas, & S. Sohrabi (Eds.) Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling, Nancy, France, October 26\u201330, 2020 (pp. 357\u2013365). AAAI Press. https:\/\/aaai.org\/ojs\/index.php\/ICAPS\/article\/view\/6681.","DOI":"10.1609\/icaps.v30i1.6681"},{"issue":"2","key":"699_CR10","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/S0377-2217(97)00341-X","volume":"107","author":"S Dauz\u00e8re-P\u00e9r\u00e8s","year":"1998","unstructured":"Dauz\u00e8re-P\u00e9r\u00e8s, S., Roux, W., & Lasserre, J. (1998). Multi-resource shop scheduling with resource flexibility. European Journal of Operational Research, 107(2), 289\u2013305. https:\/\/doi.org\/10.1016\/S0377-2217(97)00341-X","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"699_CR11","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0377-2217(99)00205-2","volume":"125","author":"A Drexl","year":"2000","unstructured":"Drexl, A., Nissen, R., Patterson, J. H., & Salewski, F. (2000). Progen\/$$\\pi $$x\u2014An instance generator for resource-constrained project scheduling problems with partially renewable resources and further extensions. European Journal of Operational Research, 125(1), 59\u201372. https:\/\/doi.org\/10.1016\/S0377-2217(99)00205-2","journal-title":"European Journal of Operational Research"},{"key":"699_CR12","unstructured":"Elmaghraby, S. E. (1977). Activity networks: Project planning and control by network models. Wiley."},{"key":"699_CR13","doi-asserted-by":"crossref","unstructured":"Geibinger, T., Mischek, F., Musliu, N. (2019). Investigating constraint programming for real world industrial test laboratory scheduling. In Proceedings of the Sixteenth International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR 2019).","DOI":"10.1007\/978-3-030-19212-9_20"},{"issue":"3","key":"699_CR14","doi-asserted-by":"publisher","first-page":"1171","DOI":"10.1016\/j.ejor.2006.06.074","volume":"189","author":"J Gon\u00e7alves","year":"2008","unstructured":"Gon\u00e7alves, J., Mendes, J., & Resende, M. (2008). A genetic algorithm for the resource constrained multi-project scheduling problem. European Journal of Operational Research, 189(3), 1171\u20131190. https:\/\/doi.org\/10.1016\/j.ejor.2006.06.074","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"699_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2009.11.005","volume":"207","author":"S Hartmann","year":"2010","unstructured":"Hartmann, S., & Briskorn, D. (2010). A survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research, 207(1), 1\u201314. https:\/\/doi.org\/10.1016\/j.ejor.2009.11.005","journal-title":"European Journal of Operational Research"},{"key":"699_CR16","doi-asserted-by":"crossref","unstructured":"Hutter, F., Hoos, H. H., & Leyton-Brown, K. (2011). Sequential model-based optimization for general algorithm configuration. In International Conference on Learning and Intelligent Optimization (pp. 507\u2013523). Springer.","DOI":"10.1007\/978-3-642-25566-3_40"},{"issue":"4598","key":"699_CR17","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671\u2013680. https:\/\/doi.org\/10.1126\/science.220.4598.671","journal-title":"Science"},{"key":"699_CR18","doi-asserted-by":"crossref","unstructured":"Louren\u00e7o, H. R., Martin, O. C., St\u00fctzle, T. (2003). Iterated local search. In Handbook of metaheuristics (pp. 320\u2013353). Springer.","DOI":"10.1007\/0-306-48056-5_11"},{"key":"699_CR19","doi-asserted-by":"crossref","unstructured":"Mika, M., Walig\u00f3ra, G., & W\u0229glarz, J. (2006). Modelling setup times in project scheduling. Perspectives in Modern Project Scheduling, pp. 131\u2013163.","DOI":"10.1007\/978-0-387-33768-5_6"},{"issue":"3","key":"699_CR20","doi-asserted-by":"publisher","first-page":"1238","DOI":"10.1016\/j.ejor.2006.06.069","volume":"187","author":"M Mika","year":"2008","unstructured":"Mika, M., Walig\u00f3ra, G., & W\u0229glarz, J. (2008). Tabu search for multi-mode resource-constrained project scheduling with schedule-dependent setup times. European Journal of Operational Research, 187(3), 1238\u20131250. https:\/\/doi.org\/10.1016\/j.ejor.2006.06.069","journal-title":"European Journal of Operational Research"},{"key":"699_CR21","doi-asserted-by":"publisher","unstructured":"Mika, M., Walig\u00f3ra, G., & W\u0229glarz, J. (2015). Overview and state of the art. In C. Schwindt & J. Zimmermann (Eds.), Handbook on project management and scheduling (Vol. 1, pp. 445\u2013490). Springer. https:\/\/doi.org\/10.1007\/978-3-319-05443-8_21.","DOI":"10.1007\/978-3-319-05443-8_21"},{"key":"699_CR22","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0004-3702(92)90007-K","volume":"58","author":"S Minton","year":"1992","unstructured":"Minton, S., Johnston, M. D., Philips, A. B., & Laird, P. (1992). Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems. Artificial Intelligence, 58, 161\u2013205.","journal-title":"Artificial Intelligence"},{"key":"699_CR23","unstructured":"Mischek, F., & Musliu, N. (2018). The test laboratory scheduling problem. Technical report, Christian Doppler Laboratory for Artificial Intelligence and Optimization for Planning and Scheduling, TU Wien, CD-TR 2018\/1."},{"key":"699_CR24","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/s10479-021-04007-1","volume":"302","author":"F Mischek","year":"2021","unstructured":"Mischek, F., & Musliu, N. (2021). A local search framework for industrial test laboratory scheduling. Annals of Operations Research, 302, 533\u2013562. https:\/\/doi.org\/10.1007\/s10479-021-04007-1","journal-title":"Annals of Operations Research"},{"key":"699_CR25","unstructured":"Musliu, N. (2005). Combination of local search strategies for rotating workforce scheduling problem. In L.P. Kaelbling, & A. Saffiotti (Eds.), IJCAI-05, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, UK, July 30\u2013August 5, 2005 (pp. 1529\u20131530). Professional Book Center. http:\/\/ijcai.org\/Proceedings\/05\/Papers\/post-0448.pdf."},{"issue":"2","key":"699_CR26","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/j.ejor.2019.01.063","volume":"280","author":"R Pellerin","year":"2020","unstructured":"Pellerin, R., Perrier, N., & Berthaut, F. (2020). A survey of hybrid metaheuristics for the resource-constrained project scheduling problem. European Journal of Operational Research, 280(2), 395\u2013416.","journal-title":"European Journal of Operational Research"},{"key":"699_CR27","unstructured":"Polo\u00a0Mejia, O., Anselmet, M.C., Artigues, C., & Lopez, P. (2017). A new RCPSP variant for scheduling research activities in a nuclear laboratory. In 47th International Conference on Computers and Industrial Engineering (CIE47), Lisbonne, Portugal. https:\/\/hal.laas.fr\/hal-01630977."},{"issue":"2","key":"699_CR28","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1016\/S0377-2217(99)00153-8","volume":"120","author":"CN Potts","year":"2000","unstructured":"Potts, C. N., & Kovalyov, M. Y. (2000). Scheduling with batching: A review. European Journal of Operational Research, 120(2), 228\u2013249. https:\/\/doi.org\/10.1016\/S0377-2217(99)00153-8","journal-title":"European Journal of Operational Research"},{"key":"699_CR29","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.cor.2017.09.011","volume":"93","author":"SM Pour","year":"2018","unstructured":"Pour, S. M., Drake, J. H., & Burke, E. K. (2018). A choice function hyper-heuristic framework for the allocation of maintenance tasks in Danish railways. Computers and Operations Research, 93, 15\u201326.","journal-title":"Computers and Operations Research"},{"issue":"1","key":"699_CR30","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/S0377-2217(96)00219-6","volume":"102","author":"F Salewski","year":"1997","unstructured":"Salewski, F., Schirmer, A., & Drexl, A. (1997). Project scheduling under resource and mode identity constraints: Model, complexity, methods, and application. European Journal of Operational Research, 102(1), 88\u2013110. https:\/\/doi.org\/10.1016\/S0377-2217(96)00219-6","journal-title":"European Journal of Operational Research"},{"issue":"4","key":"699_CR31","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/s002910000042","volume":"22","author":"C Schwindt","year":"2000","unstructured":"Schwindt, C., & Trautmann, N. (2000). Batch scheduling in process industries: An application of resource-constrained project scheduling. OR-Spektrum, 22(4), 501\u2013524.","journal-title":"OR-Spektrum"},{"key":"699_CR32","doi-asserted-by":"publisher","unstructured":"Szeredi, R., & Schutt, A. (2016). Modelling and solving multi-mode resource-constrained project scheduling. In Principles and Practice of Constraint Programming\u201422nd International Conference, CP 2016, Toulouse, France, September 5\u20139, 2016, proceedings (pp. 483\u2013492). https:\/\/doi.org\/10.1007\/978-3-319-44953-1_31.","DOI":"10.1007\/978-3-319-44953-1_31"},{"issue":"10","key":"699_CR33","doi-asserted-by":"publisher","first-page":"3465","DOI":"10.1007\/s00500-017-3003-y","volume":"23","author":"F Villaf\u00e1\u00f1ez","year":"2019","unstructured":"Villaf\u00e1\u00f1ez, F., Poza, D., L\u00f3pez-Paredes, A., Pajares, J., & del Olmo, R. (2019). A generic heuristic for multi-project scheduling problems with global and local resource constraints (rcmpsp). Soft Computing, 23(10), 3465\u20133479.","journal-title":"Soft Computing"},{"key":"699_CR34","doi-asserted-by":"crossref","unstructured":"Wallace, R.J., & Freuder, E.C. (1996). Heuristic methods for over-constrained constraint satisfaction problems. In Overconstrained systems. Springer 1106.","DOI":"10.1007\/3-540-61479-6_23"},{"issue":"3","key":"699_CR35","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s10951-014-0402-0","volume":"19","author":"T Wauters","year":"2016","unstructured":"Wauters, T., Kinable, J., Smet, P., Vancroonenburg, W., Vanden Berghe, G., & Verstichel, J. (2016). The multi-mode resource-constrained multi-project scheduling problem. Journal of Scheduling, 19(3), 271\u2013283. https:\/\/doi.org\/10.1007\/s10951-014-0402-0","journal-title":"Journal of Scheduling"},{"issue":"3","key":"699_CR36","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/j.ejor.2010.03.037","volume":"208","author":"J W\u0229glarz","year":"2011","unstructured":"W\u0229glarz, J., J\u00f3zefowska, J., Mika, M., & Walig\u00f3ra, G. (2011). Project scheduling with finite or infinite number of activity processing modes\u2014A survey. European Journal of Operational Research, 208(3), 177\u2013205. https:\/\/doi.org\/10.1016\/j.ejor.2010.03.037","journal-title":"European Journal of Operational Research"},{"key":"699_CR37","unstructured":"Wilson, M., Witteveen, C., & Huisman, B. (2012). Enhancing predictability of schedules by task grouping. In BNAIC 2012: 24th Benelux Conference on Artificial Intelligence, Maastricht, The Netherlands, 25\u201326 October."},{"key":"699_CR38","doi-asserted-by":"crossref","unstructured":"Young, K. D., Feydy, T., & Schutt, A. (2017). Constraint programming applied to the multi-skill project scheduling problem. In J. C. Beck (Ed.), Principles and practice of constraint programming (pp. 308\u2013317). Springer.","DOI":"10.1007\/978-3-319-66158-2_20"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-021-00699-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-021-00699-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-021-00699-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,16]],"date-time":"2023-09-16T09:06:41Z","timestamp":1694855201000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-021-00699-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,13]]},"references-count":38,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["699"],"URL":"https:\/\/doi.org\/10.1007\/s10951-021-00699-2","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"type":"print","value":"1094-6136"},{"type":"electronic","value":"1099-1425"}],"subject":[],"published":{"date-parts":[[2021,9,13]]},"assertion":[{"value":"16 July 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 September 2021","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 authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}