Title: Instance space analysis for the job shop scheduling problem
Language: English
Authors: Strassl, Simon 
Qualification level: Diploma
Advisor: Musliu, Nysret  
Issue Date: 2020
Strassl, S. (2020). Instance space analysis for the job shop scheduling problem [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2020.80620
Number of Pages: 77
Qualification level: Diploma
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%.
Keywords: Instance Space Analysis; Job Shop Scheduling
URI: https://doi.org/10.34726/hss.2020.80620
DOI: 10.34726/hss.2020.80620
Library ID: AC16074160
Organisation: E192 - Institut für Logic and Computation 
Publication Type: Thesis
Appears in Collections:Thesis

Files in this item:

Page view(s)

checked on Jan 28, 2022


checked on Jan 28, 2022

Google ScholarTM


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.