{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T03:14:33Z","timestamp":1767150873207,"version":"build-2238731810"},"reference-count":34,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2023,1,26]],"date-time":"2023-01-26T00:00:00Z","timestamp":1674691200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2023,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We deal with a challenging scheduling problem on parallel machines with sequence-dependent setup times and release dates from a real-world application of semiconductor work-shop production. There, jobs can only be processed by dedicated machines, thus few machines can determine the makespan almost regardless of how jobs are scheduled on the remaining ones. This causes problems when machines fail and jobs need to be rescheduled. Instead of optimising only the makespan, we put the individual machine spans in non-ascending order and lexicographically minimise the resulting tuples. This achieves that all machines complete as early as possible and increases the robustness of the schedule. We study the application of answer-set programming (ASP) to solve this problem. While ASP eases modelling, the combination of timing constraints and the considered objective function challenges current solving technology. The former issue is addressed by using an extension of ASP by difference logic. For the latter, we devise different algorithms that use multi-shot solving. To tackle industrial-sized instances, we study different approximations and heuristics. Our experimental results show that ASP is indeed a promising knowledge representation and reasoning (KRR) paradigm for this problem and is competitive with state-of-the-art constraint programming (CP) and Mixed-Integer Programming (MIP) solvers.<\/jats:p>","DOI":"10.1017\/s1471068423000017","type":"journal-article","created":{"date-parts":[[2023,1,26]],"date-time":"2023-01-26T02:34:31Z","timestamp":1674700471000},"page":"1281-1306","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":2,"title":["Answer-Set Programming for Lexicographical Makespan Optimisation in Parallel Machine Scheduling"],"prefix":"10.1017","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6003-6345","authenticated-orcid":false,"given":"THOMAS","family":"EITER","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0856-7162","authenticated-orcid":false,"given":"TOBIAS","family":"GEIBINGER","sequence":"additional","affiliation":[]},{"given":"NYSRET","family":"MUSLIU","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9902-7662","authenticated-orcid":false,"given":"JOHANNES","family":"OETSCH","sequence":"additional","affiliation":[]},{"given":"PETER","family":"SKO\u010cOVSK\u00dd","sequence":"additional","affiliation":[]},{"given":"DARIA","family":"STEPANOVA","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2023,1,26]]},"reference":[{"key":"S1471068423000017_ref26","doi-asserted-by":"crossref","unstructured":"Ouazene, Y. , Yalaoui, F. , Chehade, H. and Yalaoui, A. 2014. Workload balancing in identical parallel machine scheduling using a mathematical programming method. International Journal of Computational Intelligence Systems 7, Suppl. 1, 58\u201367.","DOI":"10.1080\/18756891.2013.853932"},{"key":"S1471068423000017_ref34","first-page":"42","article-title":"Parallel machine scheduling with load balancing and sequence dependent setups","volume":"1","author":"Yildirim","year":"2007","journal-title":"International Journal of Operations Research 4"},{"key":"S1471068423000017_ref5","doi-asserted-by":"crossref","unstructured":"Avalos-Rosales, O. , Alvarez, A. M. and \u00c1ngel-Bello, F. 2013. A reformulation for the problem of scheduling unrelated parallel machines with sequence and machine dependent setup times. In Proceedings 23rd International Conference on Automated Planning and Scheduling (ICAPS 2013), 278\u2013282.","DOI":"10.1609\/icaps.v23i1.13596"},{"key":"S1471068423000017_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/s10100-015-0429-0"},{"key":"S1471068423000017_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/s00170-003-1603-4"},{"key":"S1471068423000017_ref24","doi-asserted-by":"crossref","unstructured":"Nethercote, N. , Stuckey, P. J. , Becket, R. , Brand, S. , Duck, G. J. and Tack, G. 2007. MiniZinc: Towards a standard CP modelling language. In International Conference on Principles and Practice of Constraint Programming, vol. 4741. Lecture Notes in Computer Science. Springer, 529\u2013543.","DOI":"10.1007\/978-3-540-74970-7_38"},{"key":"S1471068423000017_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2020.08.032"},{"key":"S1471068423000017_ref33","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-5273(00)00066-9"},{"key":"S1471068423000017_ref10","doi-asserted-by":"crossref","unstructured":"Eiter, T. , Geibinger, T. , Musliu, N. , Oetsch, J. , Sko\u010dovsk\u00fd, P. and Stepanova, D. 2021. Answer-set programming for lexicographical makespan optimisation in parallel machine scheduling. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, vol. 18, 280\u2013290.","DOI":"10.24963\/kr.2021\/27"},{"key":"S1471068423000017_ref13","doi-asserted-by":"crossref","unstructured":"Gebser, M. , Ostrowski, M. and Schaub, T. 2009. Constraint answer set solving. In Proceedings of the 25th International Conference on Logic Programming (ICLP 2009), vol. 5649. Lecture Notes in Computer Science. Springer, 235\u2013249.","DOI":"10.1007\/978-3-642-02846-5_22"},{"key":"S1471068423000017_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2006.06.060"},{"key":"S1471068423000017_ref25","doi-asserted-by":"crossref","unstructured":"Ogryczak, W. and \u015aliwi\u0144ski, T. 2006. On direct methods for lexicographic min-max optimization. In Proceedings of the 6th International Conference on Computational Science and Its Applications (ICCSA 2006), vol. 3982. Lecture Notes in Computer Science. Springer, 802\u2013811.","DOI":"10.1007\/11751595_85"},{"key":"S1471068423000017_ref17","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068418000054"},{"key":"S1471068423000017_ref1","doi-asserted-by":"crossref","unstructured":"Abels, D. , Jordi, J. , Ostrowski, M. , Schaub, T. , Toletti, A. and Wanko, P. 2019. Train scheduling with hybrid ASP. In Proceedings of the 15th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2019), vol. 11481. Lecture Notes in Computer Science. Springer, 3\u201317.","DOI":"10.1007\/978-3-030-20528-7_1"},{"key":"S1471068423000017_ref11","unstructured":"El-Kholany, M. and Gebser, M. 2020. Job shop scheduling with multi-shot ASP. In Proceedings of the 4th Workshop on Trends and Applications of Answer Set Programming (TAASP 2020)."},{"key":"S1471068423000017_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2019.03.034"},{"key":"S1471068423000017_ref21","first-page":"1","article-title":"Relating constraint answer set programming languages and algorithms","author":"Lierler","year":"2014","journal-title":"Artificial Intelligence 207"},{"key":"S1471068423000017_ref29","unstructured":"Sabuncu, O. and Simsek, M. C. 2020. Solving assembly line workload smoothing problem via answer set programming. In Proceedings of the 13th Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP 2020), vol. 2678. CEUR Workshop Proceedings. CEUR-WS.org."},{"key":"S1471068423000017_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2018.05.014"},{"key":"S1471068423000017_ref7","doi-asserted-by":"publisher","DOI":"10.1145\/2043174.2043195"},{"key":"S1471068423000017_ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2011.01.011"},{"key":"S1471068423000017_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2016.05.020"},{"key":"S1471068423000017_ref23","unstructured":"McCarthy, J. 1998. Elaboration tolerance. In Common Sense, vol. 98."},{"key":"S1471068423000017_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068419000450"},{"key":"S1471068423000017_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(91)90018-K"},{"key":"S1471068423000017_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2018.10.010"},{"key":"S1471068423000017_ref15","doi-asserted-by":"crossref","unstructured":"Gebser, M. , Kaufmann, B. , Romero, J. , Otero, R. , Schaub, T. and Wanko, P. 2013. Domain-specific heuristics in answer set programming. In Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI 2013). AAAI Press, 350\u2013356.","DOI":"10.1609\/aaai.v27i1.8585"},{"key":"S1471068423000017_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-01561-8"},{"key":"S1471068423000017_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-24658-7"},{"key":"S1471068423000017_ref19","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068417000242"},{"key":"S1471068423000017_ref16","unstructured":"Gebser, M. , Kaminski, R. , Kaufmann, B. , Ostrowski, M. , Schaub, T. and Wanko, P. 2016. Theory solving made easy with Clingo 5. In Tech. Comm. 32nd International Conference on Logic Programming (ICLP 2016), vol. 52. OASIcs. Schloss Dagstuhl-Leibniz-Zentrum f. Informatik, 2:1\u20132:15."},{"key":"S1471068423000017_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2018.07.007"},{"key":"S1471068423000017_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2015.04.004"},{"key":"S1471068423000017_ref31","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2011.01.011"}],"updated-by":[{"DOI":"10.1017\/s1471068424000061","type":"addendum","label":"Addendum","source":"publisher","updated":{"date-parts":[[2023,1,26]],"date-time":"2023-01-26T00:00:00Z","timestamp":1674691200000}}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068423000017","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,24]],"date-time":"2024-01-24T07:06:50Z","timestamp":1706080010000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068423000017\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,26]]},"references-count":34,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["S1471068423000017"],"URL":"https:\/\/doi.org\/10.1017\/s1471068423000017","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,26]]},"assertion":[{"value":"\u00a9 The Author(s), 2023. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}