Publication: Problem Decomposition and Multi-shot AS...
Master data
Title: | Problem Decomposition and Multi-shot ASP Solving for Job-shop Scheduling |
Subtitle: | |
Abstract: | 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. |
Keywords: | Artificial Intelligence, Computational Theory and Mathematics, Hardware and Architecture, Theoretical Computer Science, Software |
Publication type: | Article in journal (Authorship) |
Publication date: | 04.07.2022 (Online) |
Published by: |
Theory and Practice of Logic Programming
Theory and Practice of Logic Programming
(
Cambridge University Press;
M. Truszczynski
)
to publication |
Title of the series: | - |
Volume number: | 22 |
Issue: | 4 |
First publication: | Yes |
Version: | - |
Page: | pp. 623 - 639 |
Versionen
Keine Version vorhanden |
Publication date: | 07.2022 |
ISBN: | - |
ISSN: | 1471-0684 |
Homepage: | - |
Publication date: | 04.07.2022 |
ISBN (e-book): | - |
eISSN: | 1475-3081 |
DOI: | http://dx.doi.org/10.1017/s1471068422000217 |
Homepage: | - |
Open access |
|
Authors
Mohammed Mahmoud Saadeldin El-Kholany (internal) |
Martin Gebser (internal) |
Konstantin Schekotihin (internal) |
Assignment
Organisation | Address | ||||
---|---|---|---|---|---|
Fakultät für Technische Wissenschaften
Institut für Artificial Intelligence und Cybersecurity
|
AT - A-9020 Klagenfurt |
Categorisation
Subject areas | |
Research Cluster | No research Research Cluster selected |
Citation index |
Information about the citation index: Master Journal List
|
Peer reviewed |
|
Publication focus |
Classification raster of the assigned organisational units:
|
working groups |
|
Cooperations
Research activities
Projects: | No related projects |
Publications: | No related publications |
Events: | No related events |
Lectures: |
|