{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T22:16:41Z","timestamp":1766269001593,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,10,14]],"date-time":"2024-10-14T00:00:00Z","timestamp":1728864000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,10,14]],"date-time":"2024-10-14T00:00:00Z","timestamp":1728864000000},"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":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper we deal with a complex real world scheduling problem closely related to the well-known Resource-Constrained Project Scheduling Problem (RCPSP). The problem concerns industrial test laboratories in which a large number of tests are performed by qualified personnel using specialised equipment, while respecting deadlines and other constraints. We present different constraint programming models and search strategies for this problem. Furthermore, we propose a Very Large Neighborhood Search approach based on our CP methods. Our models are evaluated using CP solvers and a MIP solver both on real-world test laboratory data and on a set of generated instances of different sizes based on the real-world data. Further, we compare the exact approaches with VLNS and a Simulated Annealing heuristic. We could find feasible solutions for all instances and several optimal solutions and we show that using VLNS we can improve upon the results of the other approaches.\n<\/jats:p>","DOI":"10.1007\/s10951-024-00821-0","type":"journal-article","created":{"date-parts":[[2024,10,14]],"date-time":"2024-10-14T13:01:54Z","timestamp":1728910914000},"page":"607-622","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Investigating constraint programming and hybrid methods for real world industrial test laboratory scheduling"],"prefix":"10.1007","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0856-7162","authenticated-orcid":false,"given":"Tobias","family":"Geibinger","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1166-3881","authenticated-orcid":false,"given":"Florian","family":"Mischek","sequence":"additional","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":[[2024,10,14]]},"reference":[{"issue":"3","key":"821_CR1","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":"821_CR2","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 Proceedings of the 5th international conference on the practice and theory of automated timetabling (PATAT 2005), Springer, LNCS,3616, 229\u2013243. https:\/\/doi.org\/10.1007\/11593577_14","DOI":"10.1007\/11593577_14"},{"issue":"1","key":"821_CR3","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":"821_CR4","unstructured":"Chu, G. (2011). Improving combinatorial optimization. PhD thesis, University of Melbourne, Australia, http:\/\/hdl.handle.net\/11343\/36679"},{"issue":"2","key":"821_CR5","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"},{"key":"821_CR6","doi-asserted-by":"publisher","unstructured":"Demirovic, E., Chu, G., & Stuckey, PJ. (2018). Solution-based phase saving for CP: A value-selection heuristic to simulate local search behavior in complete solvers. In Proceedings of the 24th international conference on principles and practice of constraint programming (CP 2018), Springer, LNCS, 11008, 99\u2013108. https:\/\/doi.org\/10.1007\/978-3-319-98334-9_7","DOI":"10.1007\/978-3-319-98334-9_7"},{"issue":"1","key":"821_CR7","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/j.ijpe.2006.08.021","volume":"112","author":"LE Drezet","year":"2008","unstructured":"Drezet, L. E., & Billaut, J. C. (2008). A project scheduling problem with labour constraints and time-dependent activities requirements. International Journal of Production Economics, 112(1), 217\u2013225. https:\/\/doi.org\/10.1016\/j.ijpe.2006.08.021","journal-title":"International Journal of Production Economics"},{"key":"821_CR8","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. Wiley."},{"key":"821_CR9","unstructured":"Feydy, T., Goldwaser, A., Schutt, A., Stuckey, PJ., & Young, KD. (2017). Priority search with minizinc. In Proceedings of ModRef 2017: The 16th international workshop on constraint modelling and reformulation at CP 2017, https:\/\/ozgurakgun.github.io\/ModRef2017\/files\/ModRef2017_PrioritySearchWithMiniZinc.pdf"},{"key":"821_CR10","doi-asserted-by":"publisher","unstructured":"Geibinger, T., Mischek, F., & Musliu, N. (2019). Investigating constraint programming for real world industrial test laboratory scheduling. In Proceedings of the 16th international conference on the integration of constraint programming, artificial intelligence, and operations research (CPAIOR 2019), Springer, LNCS, 11494, 304\u2013319. https:\/\/doi.org\/10.1007\/978-3-030-19212-9_20","DOI":"10.1007\/978-3-030-19212-9_20"},{"issue":"1","key":"821_CR11","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":"821_CR12","unstructured":"IBM, CPLEX (2017a) 12.8.0 IBM ILOG CPLEX Optimization Studio CP Optimizer user\u2019s manual. https:\/\/www.ibm.com\/analytics\/cplex-cp-optimizer"},{"key":"821_CR13","unstructured":"IBM, CPLEX (2017b) 12.8.0 IBM ILOG CPLEX Optimization Studio CPLEX user\u2019s manual. https:\/\/www.ibm.com\/analytics\/cplex-optimizer"},{"issue":"4598","key":"821_CR14","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"},{"issue":"2","key":"821_CR15","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/s10601-018-9281-x","volume":"23","author":"P Laborie","year":"2018","unstructured":"Laborie, P., Rogerie, J., Shaw, P., & Vil\u00edm, P. (2018). IBM ILOG CP optimizer for scheduling. Constraints, 23(2), 210\u2013250. https:\/\/doi.org\/10.1007\/s10601-018-9281-x","journal-title":"Constraints"},{"key":"821_CR16","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). Springer."},{"key":"821_CR17","unstructured":"Mischek, F., & Musliu, N. (2018a). A local search framework for industrial test laboratory scheduling. In Proceedings of the 12th international conference on the practice and theory of automated timetabling (PATAT 2018), 465\u2013467, https:\/\/patatconference.org\/patat2018\/files\/proceedings\/paper33.pdf"},{"key":"821_CR18","unstructured":"Mischek, F., & Musliu, N. (2018b). 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, https:\/\/www.dbai.tuwien.ac.at\/staff\/fmischek\/TLSP\/TLSP.pdf"},{"key":"821_CR19","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":"821_CR20","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 Proceedings of the 13th international conference on principles and practice of constraint programming (CP 2007), Springer, LNCS, 4741, 529\u2013543. https:\/\/doi.org\/10.1007\/978-3-540-74970-7_38","DOI":"10.1007\/978-3-540-74970-7_38"},{"issue":"1","key":"821_CR21","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/S0360-8352(96)00212-4","volume":"32","author":"N Nudtasomboon","year":"1997","unstructured":"Nudtasomboon, N., & Randhawa, S. U. (1997). Resource-constrained project scheduling with renewable and non-renewable resources and time-resource tradeoffs. Computers & Industrial Engineering, 32(1), 227\u2013242. https:\/\/doi.org\/10.1016\/S0360-8352(96)00212-4","journal-title":"Computers & Industrial Engineering"},{"issue":"1","key":"821_CR22","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1023\/B:ANOR.0000039521.26237.62","volume":"131","author":"M Palpant","year":"2004","unstructured":"Palpant, M., Artigues, C., & Michelon, P. (2004). Lssper: Solving the resource-constrained project scheduling problem with large neighbourhood search. Annals of Operations Research, 131(1), 237\u2013257. https:\/\/doi.org\/10.1023\/B:ANOR.0000039521.26237.62","journal-title":"Annals of Operations Research"},{"issue":"1","key":"821_CR23","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1287\/mnsc.16.1.93","volume":"16","author":"AAB Pritsker","year":"1969","unstructured":"Pritsker, A. A. B., Waiters, L. J., & Wolfe, P. M. (1969). Multiproject scheduling with limited resources: A zero-one programming approach. Management Science, 16(1), 93\u2013108. https:\/\/doi.org\/10.1287\/mnsc.16.1.93","journal-title":"Management Science"},{"issue":"1","key":"821_CR24","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"},{"key":"821_CR25","unstructured":"Schulte, C., Lagerkvist, M., & Tack, G. (2018). Gecode 6.10 reference documentation. https:\/\/www.gecode.org"},{"issue":"4","key":"821_CR26","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. https:\/\/doi.org\/10.1007\/s002910000042","journal-title":"OR-Spektrum"},{"key":"821_CR27","doi-asserted-by":"publisher","unstructured":"Szeredi, R., & Schutt, A. (2016). Modelling and solving multi-mode resource-constrained project scheduling. In Proceedings of the 22nd international conference on principles and practice of constraint programming (CP 2016), Springer, LNCS, vol 9892, pp 483\u2013492, https:\/\/doi.org\/10.1007\/978-3-319-44953-1_31","DOI":"10.1007\/978-3-319-44953-1_31"},{"issue":"3","key":"821_CR28","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":"821_CR29","doi-asserted-by":"publisher","unstructured":"Young, KD., Feydy, T., & Schutt, A. (2017). Constraint programming applied to the multi-skill project scheduling problem. In Proceedings of the 23rd international conference on principles and practice of constraint programming (CP 2017), LNCS, 10416, 308\u2013317. https:\/\/doi.org\/10.1007\/978-3-319-66158-2_20","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-024-00821-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-024-00821-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-024-00821-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,16]],"date-time":"2024-11-16T13:03:46Z","timestamp":1731762226000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-024-00821-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,14]]},"references-count":29,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["821"],"URL":"https:\/\/doi.org\/10.1007\/s10951-024-00821-0","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"type":"print","value":"1094-6136"},{"type":"electronic","value":"1099-1425"}],"subject":[],"published":{"date-parts":[[2024,10,14]]},"assertion":[{"value":"3 August 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 October 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}