Publication: Decomposition-Based Job-Shop Scheduling...
Master data
Title: | Decomposition-Based Job-Shop Scheduling with Constrained Clustering |
Subtitle: | |
Abstract: | Scheduling is a crucial problem appearing in various domains, such as manufacturing, transportation, or healthcare. In most problem definitions, the goal is to schedule a given set of operations on available resources to complete the operations as early as possible. Unfortunately, most scheduling problems cannot be solved efficiently. Therefore, the research of suitable approximation methods is of primary importance. This work suggests a novel approximation approach based on problem decomposition with data mining methodologies. This study proposes a constrained clustering algorithm to group the operations into clusters corresponding to time windows in which these operations must be scheduled. The decomposition process depends on two main phases. The first phase is to extract features to predict the sequence of the operations on each resource. These features are extracted either from the problem itself or from solutions obtained by other heuristics. The second phase is to develop a constrained clustering algorithm to assign each operation into a time window. We solved the problem using the Answer Set Programming. Evaluation results show that our proposed outperformed other heuristic schedulers in most cases, where features, like Remaining Processing Time, Machine Load, and Earliest Starting Time, contributed significantly to the solution quality. |
Keywords: |
Publication type: | Article in Proceedings (Authorship) |
Publication date: | 12.01.2022 (Print) |
Published by: | Practical Aspects of Declarative Languages ( Springer Nature Switzerland AG; J. Cheney, S. Perri ) |
Title of the series: | Lecture Notes in Computer Science |
Volume number: | 13165 |
First publication: | Yes |
Version: | - |
Page: | pp. 165 - 180 |
Versionen
Keine Version vorhanden |
Publication date: | 12.01.2022 |
ISBN: |
|
ISSN: | - |
Homepage: | - |
Publication date: | 12.01.2022 |
ISBN (e-book): |
|
eISSN: | - |
DOI: | http://dx.doi.org/10.1007/978-3-030-94479-7 |
Homepage: | https://link.springer.com/book/10.1007/978-3-030-94479-7 |
Open access |
|
Authors
Mohammed Mahmoud Saadeldin El-Kholany (internal) |
Konstantin Schekotihin (internal) |
Martin Gebser (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 |
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: |
|