Instance space analysis for the job shop scheduling problem

Abstract

The continuous increase in size and complexity of production systems makes the use of automated scheduling systems almost a necessity. The choice of algorithm is of course a major factor in the quality of the schedule, which in turn can have a very real impact on the efficiency of the system. It is therefore imperative that this choice is an informed one that can, ideally, be made by an automated system instead of relying on human expertise. This thesis provides a systematic analysis of the instance space of the job shop scheduling problem with the goal of furthering our understanding of the problem and creating an improved foundation for further work. 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 algorithms were evaluated 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. An analysis of the algorithms' performance characteristics revealed significant differences between the best metaheuristics and the best exact methods. The metaheuristics showed significantly worse performance on instances with processing times drawn from a constant or negative binomial distribution, while the exact methods displayed inferior performance on instances with uniformly or binomially distributed processing times. The difference in algorithm performance was utilized to train machine learning models to predict the best algorithm for a given instance. The solver based on the best model was able to obtain the best solution for 90% of the instances, whereas the best individual algorithm only obtained the best solution for 64%.