.png){kind=icon}
.png){kind=icon}
Return
Instance space analysis and algorithm selection for the job shop scheduling problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2021.105661.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper is concerned with the job shop scheduling problem, a well-known, NP-hard problem that has been extensively studied in the literature, but for which, despite its age and popularity, there has been relatively little work done towards understanding the landscape of instances. We provide a systematic analysis of the instance space for this problem. For this purpose, the benchmark instances commonly used in the literature were analyzed and extended by a set of newly generated instances of various sizes with processing times drawn from different probability distributions. A number of different state-of-the-art algorithms were evaluated on the extended instance set to analyze their performance patterns and highlight the differences to the current set of benchmark instances. It was found that the existing instances cover a significantly smaller area than the generated ones and did in fact result in different conclusions regarding the algorithms' performances. Furthermore, different algorithms have been shown to excel on distinct subsets of the extended instance set. This has been utilized to train machine learning models to predict the best algorithm for a given instance, the best of which was able to obtain the best solution for 90% of the instances, whereas the best individual algorithm only obtained the best solution for 64%.
Keywords:
Instance space analysis
ISA
Job shop scheduling
Automated algorithm selection
Algorithm selection
Job scheduling
JSSP
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W