Karlsruhe, den 03.03.2013

Zusammenfassung der Dissertation

Scheduling Maximal Time Lags on GERT Networks

von

Max Muster

In der Dissertation wird ein Open–Shop–Scheduling–Modell mit stochastischen Anordnungsbeziehungen und Maximalabständen vorgestellt, und es werden Verfahren zur Lösung von zugehörigen Scheduling–Problemen entwickelt und verglichen.

Das deterministische Open–Shop–Problem O||Cmax gehört zur Klasse der NP–schweren Probleme. Erst in letzter Zeit wurden leistungsstarke Branch–and–Bound–Verfahren zur exakten Lösung von J||Cmax –Problemen vorgestellt, wie z.B. von Carlier & Pinson (1989), die erstmals das bekannte 10x10–Benchmarkproblem von Muth & Thompson aus dem Jahre 1963 exakt lösten.

In der vorliegenden Arbeit werden zusätzlich stochastische Vorrangsbeziehungen und zugleich Maximalabstände betrachtet. Hierfür wird das Konzept der GERT–Netzpläne verwendet. Diese Modelle können bei der Planung der Fertigung von Varianten bei Kundenauftragsfertigung eingesetzt werden. Dabei entsprechen die zu fertigenden Varianten gerade den Projektrealisationen des der Produktion zugrundeliegenden GERT–Netzplans. Es werden ein Open–Shop–Modell und eine deterministische Schedulingpolitik vorgestellt. Für Flow–Shop–Probleme können zwei unterschiedliche deterministische Schedulingpolitiken betrachtet werden. Die zu minimierende Zielgröße ist der erwartete Projektendtermin E(Cmax). Anschließend wird eine Möglichkeit zur Berechnung einer scharfen unteren Schranke aufgezeigt.
Danach werden zwei heuristische Lösungsverfahren vorgestellt. Zum einen wird ein "aggregierter" Disjunktivgraph entwickelt, der stochastische Vorrangsbeziehungen integriert und für den ein permutierendes Engpaßverfahren angewandt wird. Zum anderen wird ein prioritätsregelgesteuertes Verfahren entwickelt.
Beide Verfahren werden bzgl. Lösungsgüte und Laufzeit in einer umfangreichen experimentellen Studie miteinander verglichen.
Abschließend werden Ergänzungen bzgl. Zielfunktion und Vorrangsbeziehungen sowie Verbesserungsverfahren aufgezeigt.

Die Arbeit wurde von Herrn Prof. Dr. B. Treuer am Institut ABC betreut. Sie ist in englischer Sprache verfasst. Dr. rer. pol./Dr.-Ing ist der angestrebte Doktorgrad.