{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:35:03Z","timestamp":1759667703979,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,3,8]],"date-time":"2021-03-08T00:00:00Z","timestamp":1615161600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,8]],"date-time":"2021-03-08T00:00:00Z","timestamp":1615161600000},"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":["CD-Labor f\u00fcr K\u00fcnstliche Intelligenz und Optimierung in Planung und Scheduling"],"award-info":[{"award-number":["CD-Labor f\u00fcr K\u00fcnstliche Intelligenz und Optimierung in Planung und Scheduling"]}],"id":[{"id":"10.13039\/501100006012","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper we introduce a complex scheduling problem that arises in a real-world industrial test laboratory, where a large number of activities has to be performed using qualified personnel and specialized equipment, subject to time windows and several other constraints. The problem is an extension of the well-known Resource-Constrained Project Scheduling Problem and features multiple heterogeneous resources with very general availability restrictions, as well as a grouping phase, where the jobs have to be assembled from smaller units. We describe an instance generator for this problem and publicly available instance sets, both randomly generated and real-world data. Finally, we present and evaluate different metaheuristic approaches to solve the scheduling subproblem, where the assembled jobs are already provided. Our results show that Simulated Annealing can be used to achieve very good results, in particular for large instances, where it is able to consistently find better solutions than a state-of-the-art constraint programming solver within reasonable time.<\/jats:p>","DOI":"10.1007\/s10479-021-04007-1","type":"journal-article","created":{"date-parts":[[2021,3,8]],"date-time":"2021-03-08T13:02:46Z","timestamp":1615208566000},"page":"533-562","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["A local search framework for industrial test laboratory scheduling"],"prefix":"10.1007","volume":"302","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1166-3881","authenticated-orcid":false,"given":"Florian","family":"Mischek","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3992-8637","authenticated-orcid":false,"given":"Nysret","family":"Musliu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,3,8]]},"reference":[{"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","key":"4007_CR1","DOI":"10.1145\/3205455.3205620"},{"key":"4007_CR2","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-carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem. Information Sciences, 373, 476\u2013498.","journal-title":"Information Sciences"},{"issue":"3","key":"4007_CR3","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":"4007_CR4","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/11593577_14","volume-title":"Practice and Theory of Automated Timetabling V","author":"O Bellenguez","year":"2005","unstructured":"Bellenguez, O., & N\u00e9ron, E. (2005). Lower bounds for the multi-skill project scheduling problem with hierarchical levels of skills. In M. Trick & E. Burke (Eds.), Practice and Theory of Automated Timetabling V (pp. 229\u2013243). Berlin: Springer Berlin Heidelberg."},{"issue":"1","key":"4007_CR5","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(83)90012-4","volume":"5","author":"J Blazewicz","year":"1983","unstructured":"Blazewicz, J., Lenstra, J. K., & Kan, A. R. (1983). Scheduling subject to resource constraints: Classification and complexity. Discrete Applied Mathematics, 5(1), 11\u201324.","journal-title":"Discrete Applied Mathematics"},{"doi-asserted-by":"publisher","unstructured":"Bouleimen K, Lecocq H (2003) A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. European Journal of Operational Research 149(2):268 \u2013 281, https:\/\/doi.org\/10.1016\/S0377-2217(02)00761-0, http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0377221702007610, sequencing and Scheduling","key":"4007_CR6","DOI":"10.1016\/S0377-2217(02)00761-0"},{"issue":"1","key":"4007_CR7","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.","journal-title":"European Journal of Operational Research"},{"unstructured":"Chu G (2011) Improving combinatorial optimization. PhD thesis, University of Melbourne, Australia, http:\/\/hdl.handle.net\/11343\/36679","key":"4007_CR8"},{"issue":"2","key":"4007_CR9","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.","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"4007_CR10","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 -an instance generator for resource-constrained project scheduling problems with partially renewable resources and further extensions. European Journal of Operational Research, 125(1), 59\u201372.","journal-title":"European Journal of Operational Research"},{"key":"4007_CR11","volume-title":"Activity networks: Project planning and control by network models","author":"SE Elmaghraby","year":"1977","unstructured":"Elmaghraby, S. E. (1977). Activity networks: Project planning and control by network models. New Jersey: Wiley."},{"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)","key":"4007_CR12","DOI":"10.1007\/978-3-030-19212-9_20"},{"issue":"3","key":"4007_CR13","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.","journal-title":"European Journal of Operational Research"},{"issue":"7","key":"4007_CR14","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1002\/(SICI)1520-6750(199810)45:7<733::AID-NAV5>3.0.CO;2-C","volume":"45","author":"S Hartmann","year":"1998","unstructured":"Hartmann, S. (1998). A competitive genetic algorithm for resource-constrained project scheduling. Naval Research Logistics (NRL), 45(7), 733\u2013750.","journal-title":"Naval Research Logistics (NRL)"},{"issue":"1","key":"4007_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.","journal-title":"European Journal of Operational Research"},{"doi-asserted-by":"crossref","unstructured":"Hutter F, Hoos HH, Leyton-Brown K (2011) Sequential model-based optimization for general algorithm configuration. In: International Conference on Learning and Intelligent Optimization, Springer, pp 507\u2013523","key":"4007_CR16","DOI":"10.1007\/978-3-642-25566-3_40"},{"issue":"4598","key":"4007_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.","journal-title":"Science"},{"key":"4007_CR18","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1016\/j.cie.2017.07.028","volume":"112","author":"A Laurent","year":"2017","unstructured":"Laurent, A., Deroussi, L., Grangeon, N., & Norre, S. (2017). A new extension of the rcpsp in a multi-site context: Mathematical model and metaheuristics. Computers and Industrial Engineering, 112, 634\u2013644.","journal-title":"Computers and Industrial Engineering"},{"key":"4007_CR19","first-page":"131","volume-title":"Modelling setup times in project scheduling. Perspectives in modern project scheduling","author":"M Mika","year":"2006","unstructured":"Mika, M., Walig\u00f3ra, G., & W\u0229glarz, J. (2006). Modelling setup times in project scheduling. Perspectives in modern project scheduling (pp. 131\u2013163). Boston: Springer."},{"key":"4007_CR20","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/978-3-319-05443-8_21","volume-title":"Handbook on Project Management and Scheduling","author":"M Mika","year":"2015","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). Cham: Springer International Publishing. https:\/\/doi.org\/10.1007\/978-3-319-05443-8_21."},{"key":"4007_CR21","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"},{"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":"4007_CR22"},{"doi-asserted-by":"publisher","unstructured":"Nethercote N, Stuckey PJ, Becket R, Brand S, Duck GJ, Tack G (2007) Minizinc: Towards a standard CP modelling language. In: Principles and Practice of Constraint Programming - CP 2007, 13th International Conference, CP 2007, Providence, RI, USA, September 23-27, 2007, Proceedings, pp 529\u2013543, https:\/\/doi.org\/10.1007\/978-3-540-74970-7_38","key":"4007_CR23","DOI":"10.1007\/978-3-540-74970-7_38"},{"issue":"2","key":"4007_CR24","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"},{"unstructured":"Polo\u00a0Mejia O, Anselmet MC, Artigues C, Lopez P (2017) A new RCPSP variant for scheduling research activities in a nuclear laboratory. In: 47th International Conference on Computers & Industrial Engineering (CIE47), Lisbonne, Portugal, p 8p., https:\/\/hal.laas.fr\/hal-01630977","key":"4007_CR25"},{"issue":"2","key":"4007_CR26","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.","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"4007_CR27","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.","journal-title":"European Journal of Operational Research"},{"issue":"4","key":"4007_CR28","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"},{"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 - 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings, pp 483\u2013492, https:\/\/doi.org\/10.1007\/978-3-319-44953-1_31","key":"4007_CR29","DOI":"10.1007\/978-3-319-44953-1_31"},{"key":"4007_CR30","first-page":"1309","volume-title":"A minlp\/rcpsp decomposition approach for the short-term planning of batch production. In: computer aided chemical engineering","author":"N Trautmann","year":"2005","unstructured":"Trautmann, N., & Schwindt, C. (2005). A minlp\/rcpsp decomposition approach for the short-term planning of batch production. In: computer aided chemical engineering (Vol. 20, pp. 1309\u20131314). Amsterdam: Elsevier."},{"issue":"10","key":"4007_CR31","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"},{"issue":"3","key":"4007_CR32","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.","journal-title":"Journal of Scheduling"},{"issue":"3","key":"4007_CR33","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 - a 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"},{"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-26 October 2012, Citeseer","key":"4007_CR34"},{"key":"4007_CR35","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1007\/978-3-319-66158-2_20","volume-title":"Principles and Practice of Constraint Programming","author":"KD Young","year":"2017","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). Cham: Springer International Publishing."}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-021-04007-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-021-04007-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-021-04007-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T16:16:54Z","timestamp":1623946614000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-021-04007-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,8]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["4007"],"URL":"https:\/\/doi.org\/10.1007\/s10479-021-04007-1","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"type":"print","value":"0254-5330"},{"type":"electronic","value":"1572-9338"}],"subject":[],"published":{"date-parts":[[2021,3,8]]},"assertion":[{"value":"23 February 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 March 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}