Instance space analysis and algorithm selection for the job shop scheduling problem

Simon Strassl

doi:10.1016/j.cor.2021.105661

2022-05-01

PRE

Simon Strassl *

Nysret Musliu

DOI：10.1016/j.cor.2021.105661

原文链接

原文求助

摘要

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%.

Keyword:

Instance space analysis

ISA

Job shop scheduling

Automated algorithm selection

Algorithm selection

Job scheduling

JSSP