M. Schlenkrich,
"Das Shifting-Bottleneck Verfahren für das Job-Shop Scheduling-Problem"
, Serie JKU Linz, 9-2018
Original Titel:
Das Shifting-Bottleneck Verfahren für das Job-Shop Scheduling-Problem
Sprache des Titels:
Englisch
Original Kurzfassung:
Schedulingprobleme treten in unserer Welt in den verschiedensten Bereichen auf. Egal ob in Krankenha?usern bei der Zuteilung von Patienten zu Behandlungs- ra?umen, in Tischlereien und anderen Manufakturen bei der Abfolge von Ar- beitsschritten auf Maschinen oder der Nutzung von Schienentrassen im Bahn- verkehr. Das Lo?sen dieser Ablaufplanungsprobleme ist oftmals essentiell, um einen reibungsfreien Arbeitsalltag garantieren zu ko?nnen oder um Produktions- prozesse zu optimieren. Eine besonders ha?ufig auftretende Variante dieser Schedulingprobleme ist das sogenannte Job-Shop Ablaufplanungsproblem, bei dem die Auftra?ge auf allen zur Verfu?gung stehenden Ressourcen in einer definierten Reihenfolge be- arbeitet werden mu?ssen. Fu?r große Problemdaten mit einer hohen Anzahl an Auftra?gen und Maschinen ist das Lo?sen dieser Probleme sehr aufwa?ndig und im mathematisch-wissenschaftlichen Bereich noch nicht zur Ga?nze erforscht. Eine Methode zur Lo?sung dieser Problemklasse ist die Shifting-Bottleneck Heuristik. Wie der Name schon verra?t, handelt es sich dabei nicht um ein exaktes Verfahren, sondern um eine Heuristik, die zwar eine zula?ssige Lo?sung liefert, dies jedoch nicht unbedingt das Optimum sein muss. In der Regel sind die Lo?sungen dieses Verfahrens jedoch sehr gute Na?herungen. Dieses Verfahren lo?st mehrere kleinere Hilfsprobleme und gelangt nach m Iterationen zu einem Ergebnis, wobei m die Anzahl der Ressourcen bzw. Ma- schinen ist. Das Lo?sen dieser Hilfsprobleme geschieht zwar exakt, was Zeit und Rechenaufwand kostet, diese sind jedoch um einiges einfacher zu lo?sen als das Gesamtproblem und somit bleibt der Aufwand in einem akzeptablen Rahmen. Die Basisversion der Shifting-Bottleneck Heuristik wurde im Rahmen dieser Arbeit in Python implementiert und mit Benchmarkproblemdaten aus der Li- teratur getestet.