{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T12:02:39Z","timestamp":1769601759700,"version":"3.49.0"},"reference-count":37,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2022,7,4]],"date-time":"2022-07-04T00:00:00Z","timestamp":1656892800000},"content-version":"unspecified","delay-in-days":3,"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":[[2022,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Scheduling methods are important for effective production and logistics management, where tasks need to be allocated and performed with limited resources. In particular, the Job-shop Scheduling Problem (JSP) is a well known and challenging combinatorial optimization problem in which tasks sharing a machine are to be arranged in a sequence such that encompassing jobs can be completed as early as possible. Given that already moderately sized JSP instances can be highly combinatorial, and neither optimal schedules nor the runtime to termination of complete optimization methods is known, efficient approaches to approximate good-quality schedules are of interest. In this paper, we propose problem decomposition into time windows whose operations can be successively scheduled and optimized by means of multi-shot Answer Set Programming (ASP) solving. From a computational perspective, decomposition aims to split highly complex scheduling tasks into better manageable subproblems with a balanced number of operations so that good-quality or even optimal partial solutions can be reliably found in a small fraction of runtime. Regarding the feasibility and quality of solutions, problem decomposition must respect the precedence of operations within their jobs and partial schedules optimized by time windows should yield better global solutions than obtainable in similar runtime on the entire instance. We devise and investigate a variety of decomposition strategies in terms of the number and size of time windows as well as heuristics for choosing their operations. Moreover, we incorporate time window overlapping and compression techniques into the iterative scheduling process to counteract window-wise optimization limitations restricted to partial schedules. Our experiments on JSP benchmark sets of several sizes show that successive optimization by multi-shot ASP solving leads to substantially better schedules within the runtime limit than global optimization on the full problem, where the gap increases with the number of operations to schedule. While the obtained solution quality still remains behind a state-of-the-art Constraint Programming system, our multi-shot solving approach comes closer the larger the instance size, demonstrating good scalability by problem decomposition.<\/jats:p>","DOI":"10.1017\/s1471068422000217","type":"journal-article","created":{"date-parts":[[2022,7,4]],"date-time":"2022-07-04T07:51:24Z","timestamp":1656921084000},"page":"623-639","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":17,"title":["Problem Decomposition and Multi-shot ASP Solving for Job-shop Scheduling"],"prefix":"10.1017","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1088-2081","authenticated-orcid":false,"given":"MOHAMMED M. S.","family":"EL-KHOLANY","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MARTIN","family":"GEBSER","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0286-0958","authenticated-orcid":false,"given":"KONSTANTIN","family":"SCHEKOTIHIN","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2022,7,4]]},"reference":[{"key":"S1471068422000217_ref29","doi-asserted-by":"publisher","DOI":"10.1017\/S147106841100007X"},{"key":"S1471068422000217_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068419000450"},{"key":"S1471068422000217_ref21","doi-asserted-by":"publisher","DOI":"10.1109\/TSM.2020.3001933"},{"key":"S1471068422000217_ref1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068420000046"},{"key":"S1471068422000217_ref20","unstructured":"Kaminski, R. and Schaub, T. 2021. On the foundations of grounding in answer set programming. CoRR, abs\/2108.04769."},{"key":"S1471068422000217_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-24658-7"},{"key":"S1471068422000217_ref2","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2016-1396"},{"key":"S1471068422000217_ref30","doi-asserted-by":"publisher","DOI":"10.1080\/00207543.2021.1963496"},{"key":"S1471068422000217_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-75775-5_21"},{"key":"S1471068422000217_ref5","doi-asserted-by":"crossref","unstructured":"Balduccini, M. 2011. Industrial-size scheduling with ASP+CP. In LPNMR 2011, volume 6645. LNCS. Springer, 284\u2013296.","DOI":"10.1007\/978-3-642-20895-9_33"},{"key":"S1471068422000217_ref34","unstructured":"Tassel, P. , Gebser, M. and Schekotihin, K. 2021. A reinforcement learning environment for job-shop scheduling. In PRL 2021. URL: https:\/\/prl-theworkshop.github.io\/prl2021\/"},{"key":"S1471068422000217_ref32","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0548(99)00098-2"},{"key":"S1471068422000217_ref3","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.34.3.391"},{"key":"S1471068422000217_ref16","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1.2.117"},{"key":"S1471068422000217_ref17","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068415000150"},{"key":"S1471068422000217_ref33","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(93)90182-M"},{"key":"S1471068422000217_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-018-2757-7"},{"key":"S1471068422000217_ref27","unstructured":"Perron, L. and Furnon, V. 2019. OR-tools. URL: https:\/\/developers.google.com\/optimization"},{"key":"S1471068422000217_ref18","unstructured":"Gebser, M. , Kaminski, R. , Kaufmann, B. , Ostrowski, M. , Schaub, T. and Wanko, P. 2016. Theory solving made easy with clingo 5. In ICLP (Technical Communications) 2016, volume 52 of OASIcs. Schloss Dagstuhl, 2:1\u20132:15."},{"key":"S1471068422000217_ref36","doi-asserted-by":"publisher","DOI":"10.3926\/jiem.1206"},{"key":"S1471068422000217_ref26","volume-title":"Decomposition Methods for Complex Factory Scheduling Problems","author":"Ovacik","year":"2012"},{"key":"S1471068422000217_ref12","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068421000363"},{"key":"S1471068422000217_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2007.02.014"},{"key":"S1471068422000217_ref25","doi-asserted-by":"publisher","DOI":"10.1016\/j.mcm.2007.03.032"},{"key":"S1471068422000217_ref7","doi-asserted-by":"publisher","DOI":"10.1080\/00207548208947745"},{"key":"S1471068422000217_ref4","volume-title":"Introduction to Sequencing and Scheduling","author":"Baker","year":"1974"},{"key":"S1471068422000217_ref37","doi-asserted-by":"publisher","DOI":"10.1007\/s10489-008-0134-y"},{"key":"S1471068422000217_ref13","unstructured":"El-Kholany, M. and Gebser, M. Job shop scheduling with multi-shot ASP. In TAASP 2020. URL: http:\/\/www.kr.tuwien.ac.at\/events\/taasp20\/accepted.html"},{"key":"S1471068422000217_ref14","doi-asserted-by":"crossref","unstructured":"El-Kholany, M. , Schekotihin, K. and Gebser, M. 2022. Decomposition-based job-shop scheduling with constrained clustering. In PADL 2022, volume 13165. LNCS. Springer, 165\u2013180.","DOI":"10.1007\/978-3-030-94479-7_11"},{"key":"S1471068422000217_ref35","doi-asserted-by":"publisher","DOI":"10.1080\/002075400188843"},{"key":"S1471068422000217_ref19","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068418000054"},{"key":"S1471068422000217_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70743-X"},{"key":"S1471068422000217_ref9","doi-asserted-by":"crossref","unstructured":"Cotton, S. and Maler, O. 2006. Fast and flexible difference constraint propagation for DPLL(T). In SAT 2006, volume 4121. LNCS. Springer, 170\u2013183.","DOI":"10.1007\/11814948_19"},{"key":"S1471068422000217_ref10","doi-asserted-by":"crossref","unstructured":"Da Col, G. and Teppan, E. 2019. Industrial size job shop scheduling tackled by present day CP solvers. In CP 2019, volume 11802. LNCS. Springer, 144\u2013160.","DOI":"10.1007\/978-3-030-30048-7_9"},{"key":"S1471068422000217_ref11","doi-asserted-by":"publisher","DOI":"10.1108\/K-08-2020-0521"},{"key":"S1471068422000217_ref22","unstructured":"Kov\u00c1cs, B. , Tassel, P. , Kohlenbrein, W. , Schrott-Kostwein, P. and Gebser, M. Utilizing constraint optimization for industrial machine workload balancing. In CP 2021, volume 210. LIPIcs. Schloss Dagstuhl, 36:1\u201336:17."},{"key":"S1471068422000217_ref31","unstructured":"Shylo, O. and Shams, H. 2018. Boosting binary optimization via binary classification: A case study of job shop scheduling. CoRR, abs\/1808.10813."}],"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\/S1471068422000217","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T23:40:27Z","timestamp":1680478827000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068422000217\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["S1471068422000217"],"URL":"https:\/\/doi.org\/10.1017\/s1471068422000217","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7]]},"assertion":[{"value":"\u00a9 The Author(s), 2022. 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"}]}}