Detailansicht
Flexible job shop scheduling problem with iterative combinatorial auctions
Gabriel Reiter
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Mathematik
Betreuer*in
Arnold Neumaier
DOI
10.25365/thesis.45248
URN
urn:nbn:at:at-ubw:1-11892.94351.902658-4
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Diese Masterarbeit legt einen Algorithmus zum Lösen des flexiblen job shop scheduling Problems mit Transportzeiten vor. Dieser Algorithmus besteht aus einem Subgradientenverfahren und einer List Scheduling Heuristic, welche das Ergebnis des Subgradientenverfahrens in einen zulässigen Ablaufplan verändert. Es werden drei Methoden zur sogenannten Preis Diskriminierung vorgestellt und ihr Einfluss auf die Qualität der Ergebnisse untersucht. Außerdem wurde der Algorithmus in Java programmiert und an realitätsnahen Probleminstanzen getestet. Die Ergebnisse werden interpretiert und mit den Ergebnissen anderer Algorithmen verglichen.
Abstract
(Englisch)
This thesis puts forth an algorithm for solving the flexible job shop scheduling problem. The algorithm consist of a subgradient search and of a list scheduling heuristic, which is designed to generate feasible solutions deriving from the infeasible solutions we obtain from the subgradient search. Several methods for so-called price discrimination are introduced and their effects on the subgradient search are examined. The list scheduling heuristic uses a priority function to rank operations and creates a schedule that does not violate any constraints. Implementation in Java was written to test the method. The results of testing the algorithm on realistic industrial data are shown, compared to results from other programs and interpreted.
Schlagwörter
Schlagwörter
(Englisch)
Job Shop Scheduling Transport Times Iterative Combinatorial Auction Subgradient Search Lagrangian Relaxation
Schlagwörter
(Deutsch)
Job Shop Scheduling Transport Zeiten Iterative Kombinatorische Auktion Subgradientenverfahren Lagrange Relaxierung
Autor*innen
Gabriel Reiter
Haupttitel (Englisch)
Flexible job shop scheduling problem with iterative combinatorial auctions
Paralleltitel (Deutsch)
Flexible Job Shop Scheduling Probleme mit Iterativen Kombinatorischen Auktionen
Publikationsjahr
2016
Umfangsangabe
75 Seiten : Diagramme
Sprache
Englisch
Beurteiler*in
Arnold Neumaier
Klassifikationen
31 Mathematik > 31.76 Numerische Mathematik ,
31 Mathematik > 31.80 Angewandte Mathematik
AC Nummer
AC14467310
Utheses ID
40048
Studienkennzahl
UA | 066 | 821 | |