Abstract in Englisch

Dieser Arbeit liegt ein Industrieprojekt zugrunde. Ziel ist der Aufbau und die Implementation eines Produktionsplanungssytems (PPS-System) für die Brau- und Getränkeindustrie. Ausgehend von dieser Aufgabenstellung liegt der Fokus der Untersuchungen auf dem Teilbereich der effizienten Algorithmen innerhalb einer PPS-Lösung. Diese Arbeit gliedert sich in zwei Teile. Der erste Teil bildet eine grundlegende theoretische Analyse effizienter Algorithmen zur Produktionsplanung. Wir erhalten bestmögliche Approximationsaussagen f¨r zwei von uns betrachtete Schedulingprobleme und geben zusätzliche Performanceanalysen von einfachen (online) Schedulingalgorithmen. Der zweite Teil der Arbeit behandelt die praktische Umsetzung der Planungsalgorithmen in die entwickelte PPS-Lösung und betrachtet entstehenden Probleme bei der Systemintegration. Die im Theorieteil der Arbeit vorgestellten Planungsprobleme sind aus der konkreten Anwendung der Brau- und Getränkeindustrie abgeleitet. Es handelt sich dabei um Varianten klassischer Schedulingprobleme, die aber im Gegensatz zu ihren traditionellen Verwandten aus der Schedulingtheorie näher an der industriellen Praxis angeordnet sind. Konkret modellieren wir Fragestellungen, bei denen Maschinen und Anlagen - wie im industriellen Alltag üblich - zu gewissen Zeitpunkten nicht zur Verfügung stehen. Auf diese Weise können wir Fragestellungen, wie Systemausfälle, Wartungsmäßnahmen und Störungen betrachten. Zweitens spiegelt sich in einem solchen Ansatz eine Planung "in der Produktion" wider, bei der Maschinen und Anlagen bereits belegt sind und kontinuierlich mit neuen Aufträgen versorgt werden. Für die von uns betrachteten Probleme gelingt es uns unter Anwendung neuer Algorithmen, im Wesentlichen die gleichen Güteaussagen, wie für die klassischen Scheduling-Probleme zu treffen. Der zweite Teil der theoretischen Untersuchungen liegt im Bereich der Performance von Algorithmen. Es stellt sich die Frage, wann ein Algorithmus als ``gut'' bewertet werden kann. Hier verlassen wir die klassische Worst-Case-Analyse, die bestimmt, wie sich ein Algorithmus im schlimmsten Fall verhalten kann. Statt dessen versuchen wir durch eine Average-Case-Analyse das typische Verhalten eines Algorithmus zu erfassen. Zugrundegelegt wird ein stochastisches Modell, in dem die Prozesszeiten der Algorithmen durch Zufallsvariablen modelliert sind. Im zweiten Teil der Arbeit wird eine Brücke vom theorischen Modell zur Praxisanwendung gespannt. Für die konkrete Anwendung der Brau- und Getränkeindustrie stellen wir ein Betriebsmodell auf, das typische Informations- und Datenströme und ihre Wechselwirkung mit den zu automatisierenden Planungsabläufen in abstrakter Weise darstellt. Dieses Modell ist im gewissen Sinn stellvertretend f"ur die gesamte Prozessindustrie, da sich die typischen Elemente der Prozessindustrie wie Batchproduktion, Bestandsorientierung und mehrstufige Produktion in der Brauereianwendung wiederfinden. Anhand unseres Modells zeigen wir die Grenzen der im ersten Teil dieser Arbeit gewonnenen theoretischen Erkenntnisse. Als Konsequenz werden zum Teil völlig neue Ansätze notwendig. Es wird deutlich, dass die Planungsprobleme zwar theoretisch bestmöglich gelöst sind, aber dass die zugehörigen Algorithmen in der gegebenen Anwendung zum Teil nicht praktikabel sind. Das entwickelte Systemkonzept ist speziell auf die Anforderungen der Brau- und Getränkeindustrie ausgerichtet. Die Systemarchitektur ist hierarchisch aufgebaut: In der Vertikalen verbindet sie die Ebene der Unternehmensführung (Leitebene) mit der Produktion (Feldebene), horizontal folgt sie im Wesentlichen der Einteilung eines Brauereibetriebes in mehrere Produktionsstufen. In entsprechender Weise sind die Schedulingalgorithmen aufgebaut, so dass sie mehrstufig planen können und nur auf den Informationen aufsetzten, die ihnen aufgrund ihrer hierarchischen Einordnung zur Verfügung stehen. Wir beschreiben die Systemintegration des Algorithmenkerns in das hierarchische Planungssytem. Die Herausforderung liegt dabei vor allem in der Verknüpfung verschiedener Systemkomponenten und in der Integration der Planungsalgorithmik in die informatorischen Abläufe des Unternehmens.