Title: Instance Space Analysis for the Job Shop Scheduling Problem
Language: English
Authors: Strassl, Simon 
Keywords: Instance Space Analysis; Job Shop Scheduling
Advisor: Musliu, Nysret  
Issue Date: 2020
Number of Pages: 77
Qualification level: Diploma
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%.
URI: https://doi.org/10.34726/hss.2020.80620
http://hdl.handle.net/20.500.12708/16214
DOI: 10.34726/hss.2020.80620
Library ID: AC16074160
Organisation: E192 - Institut für Logic and Computation 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:

File Description SizeFormat
Instance Space Analysis for the Job Shop Scheduling Problem.pdf11.26 MBAdobe PDFThumbnail
 View/Open
Show full item record

Google ScholarTM

Check


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