TY - GEN
T1 - Decomposition-Based Job-Shop Scheduling with Constrained Clustering
AU - El-Kholany, Mohammed M.S.
AU - Schekotihin, Konstantin
AU - Gebser, Martin
N1 - Funding Information:
This work was partially funded by KWF project 28472, cms electronics GmbH, Fun-derMax GmbH, Hirsch Armbänder GmbH, incubed IT GmbH, Infineon Technologies Austria AG, Isovolta AG, Kostwein Holding GmbH, and Privatstiftung Kärntner Sparkasse.
Publisher Copyright:
© 2022, Springer Nature Switzerland AG.
PY - 2022
Y1 - 2022
N2 - Scheduling is a crucial problem appearing in various domains, such as manufacturing, transportation, or healthcare, where the goal is to schedule given operations on available resources such that the operations are completed as soon as possible. Unfortunately, most scheduling problems cannot be solved efficiently, so that research on suitable approximation methods is of primary importance. This work introduces a novel approximation approach based on problem decomposition with data mining methodologies. We propose a constrained clustering algorithm to group operations into clusters, corresponding to time windows in which the operations must be scheduled. The decomposition process consists of two main phases. First, features are extracted, either from the problem itself or from solutions obtained by heuristic methods, to predict the execution sequence of operations on each resource. The second phase deploys our constrained clustering algorithm to assign each operation into a time window. We then schedule the operations by time windows using Answer Set Programming. Evaluation results show that our proposed approach outperforms other heuristic schedulers in most cases, where incorporating features like Remaining Processing Time, Machine Load, and Earliest Starting Time significantly improves the solution quality.
AB - Scheduling is a crucial problem appearing in various domains, such as manufacturing, transportation, or healthcare, where the goal is to schedule given operations on available resources such that the operations are completed as soon as possible. Unfortunately, most scheduling problems cannot be solved efficiently, so that research on suitable approximation methods is of primary importance. This work introduces a novel approximation approach based on problem decomposition with data mining methodologies. We propose a constrained clustering algorithm to group operations into clusters, corresponding to time windows in which the operations must be scheduled. The decomposition process consists of two main phases. First, features are extracted, either from the problem itself or from solutions obtained by heuristic methods, to predict the execution sequence of operations on each resource. The second phase deploys our constrained clustering algorithm to assign each operation into a time window. We then schedule the operations by time windows using Answer Set Programming. Evaluation results show that our proposed approach outperforms other heuristic schedulers in most cases, where incorporating features like Remaining Processing Time, Machine Load, and Earliest Starting Time significantly improves the solution quality.
KW - Answer Set Programming
KW - Constrained clustering
KW - Job-shop Scheduling Problem
KW - Time windows
UR - http://www.scopus.com/inward/record.url?scp=85123275318&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-94479-7_11
DO - 10.1007/978-3-030-94479-7_11
M3 - Conference paper
AN - SCOPUS:85123275318
SN - 9783030944780
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 165
EP - 180
BT - Practical Aspects of Declarative Languages - 24th International Symposium, PADL 2022, Proceedings
A2 - Cheney, James
A2 - Perri, Simona
PB - Springer
CY - Cham
T2 - 24th International Conference on Practical Aspects of Declarative Languages
Y2 - 17 January 2022 through 18 January 2022
ER -