<div class="csl-bib-body">
<div class="csl-entry">Strassl, S. (2020). <i>Instance space analysis for the job shop scheduling problem</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2020.80620</div>
</div>
-
dc.identifier.uri
https://doi.org/10.34726/hss.2020.80620
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/16214
-
dc.description.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%.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Instance Space Analysis
en
dc.subject
Job Shop Scheduling
en
dc.title
Instance space analysis for the job shop scheduling problem
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.identifier.doi
10.34726/hss.2020.80620
-
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Simon Strassl
-
dc.publisher.place
Wien
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
tuw.publication.orgunit
E192 - Institut für Logic and Computation
-
dc.type.qualificationlevel
Diploma
-
dc.identifier.libraryid
AC16074160
-
dc.description.numberOfPages
77
-
dc.thesistype
Diplomarbeit
de
dc.thesistype
Diploma Thesis
en
dc.rights.identifier
In Copyright
en
dc.rights.identifier
Urheberrechtsschutz
de
tuw.advisor.staffStatus
staff
-
tuw.advisor.orcid
0000-0002-3992-8637
-
item.languageiso639-1
en
-
item.mimetype
application/pdf
-
item.openairecristype
http://purl.org/coar/resource_type/c_bdcc
-
item.fulltext
with Fulltext
-
item.openairetype
master thesis
-
item.grantfulltext
open
-
item.openaccessfulltext
Open Access
-
item.cerifentitytype
Publications
-
crisitem.author.dept
E192-02 - Forschungsbereich Databases and Artificial Intelligence