Verleihung der Diplom- und Masterarbeitspreise 2004

von PETER BRUCKER, OSNABRÜCK

Für den Diplomarbeitspreis der GOR wurden im Jahr 2004 sechs Arbeiten eingereicht. Die Jury, bestehend aus Peter Brucker, Fachbereich Mathematik/Informatik der Universität Osnabrück, Kai-Oliver Schocke von der Degussa in Darmstadt und Armin Scholl, Wirtschaftswissenschaftliche Fakultät der Friedrich-Schiller Universität Jena, hat unter dem Vorsitz von Peter Brucker nach sorgfältiger Auswahl die drei folgenden Arbeiten prämiert. Hierbei wurde wie im letzten Jahr keine Reihung vorgenommen.

Die erste Arbeit mit dem Titel »Ein Entscheidungsunterstützungssystem zur Verschnittoptimierung von Rollenstahl« wurde unter der Anleitung von Lena Suhl angefertigt. Herr Ingmar Steinzen beschäftigt sich in der sehr gelungenen Diplomarbeit mit der Analyse und der Lösung eines komplexen Entscheidungsproblems aus der betrieblichen Praxis. In enger Kooperation mit einem Unternehmen aus der Stahlindustrie wurde ein Entscheidungsunterstützungssystem zur Lösung eines 1-dimensionalen Verschnittproblems entwickelt und prototypisch implementiert. Das Problem ist dadurch charakterisiert, dass vorliegende Federbandstahlrollen in die durch konkrete Kundenaufträge definierten Abmessungen zugeschnitten werden müssen. Dabei sind verschieden zusätzliche Restriktionen zu berücksichtigen.

Herr Steinzen hat die Problemstellungen durch ein lineares ganzzahliges Optimierungsmodell abgebildet und mittels einer Branch-and-Cut Strategie unter Einsatz der MIP-Solver MOPS und CPLEX gelöst. Dabei wurde mit Hilfe von Preprocessing-Strategien im Rahmen von MOPS eine deutliche Verbesserung der Lösungsqualität und Verkürzung der Rechenzeit erreicht. Im Rahmen von Testrechnungen anhand realer Datensätze weist Herr Steinzen nach, dass das von ihm entwickelte Entscheidungsunterstützungssystem ein erhebliches Verbesserungspotential gegenüber den bisher im Unternehmen üblichen manuellen Planungen aufweist. Dies betrifft sowohl die Lösungsgüte als auch den Lösungsaufwand. Die Arbeit zeichnet sich durch eine stringente Gliederung, eine präzise Analyse der praktischen Problemstellung sowie eine sehr gelungene Darstellung des Modells, der Lösungsverfahren und der Testrechungen aus. Es ist besonders bemerkenswert, dass Herr Steinzen es in hervorragender Weise verstand, sowohl die praktischen Anforderungen des Unternehmens vollständig umzusetzen als auch ein hohes wissenschaftliches Niveau zu erreichen.

Herr Ingmar Steinzen mit Prof. Dr. Gerhard Wäscher

Die Diplomarbeit »AGV-Steuerung im Hamburger Hafen: Online-Analyse und Algorithmen für fahrerlose Transportsysteme« von Herrn Björn Stenzel wurde von Rolf Möhring betreut. Sie entstand in einem Projekt mit der Hamburger Hafen- und Lagerhaus AG, das die Untersuchung effizienter Algorithmen zum Routing von Automated Guided Vehicles (AGVs) am Container Terminal Altenwerder zum Ziel hatte. Gegeben ist dabei eine Menge von Anfragen für bestimmte AGVs zusammen mit ihrer gegenwärtigen Position, ihrer Zielposition und einer Startzeit des Transports. Die Aufgabe besteht darin, für jeden Auftrag eine möglichst günstige kollisionsfreie Route des AGV zu finden. Hierbei sind die zum Teil sehr komplexen physikalischen Fahreigenschaften der AGVs zu berücksichtigen. Die Zielsetzung ist, den Containerumschlag am Kai zu maximieren. Es handelt sich hierbei um ein Online-Problem, das in Realzeit zu lösen ist.

Herr Stenzel entwickelt in seiner Diplomarbeit einen neuen Ansatz, der auf eine implizierte Zeitexpansion basiert. Um Kollisionen zu vermeiden, wird mit den Kanten eines entsprechenden Netzwerkes gespeichert, zu welchen Zeitpunkten sie bereits für bestimmte Routen benutzt werden und damit für andere AGVs gesperrt sind. Diese zeitliche Dynamik führt auf Kürzeste-Wege-Probleme mit Zeitfenstern, die vor allem für Rundreise-Probleme NP-vollständig sind, jedoch, wie Herr Stenzel zeigen kann, für die spezielle Hafenanwendung sich polynomial lösen lassen. Durch Simulation kann Herr Stenzel zeigen, dass das von ihm entwickelte neue Routingverfahren die Gesamtdauer aller abzuwickelnden Aufträge gegenüber dem zur Zeit angewandten Verfahren im Durchschnitt um 28,7 % verbessert. In der Spitze beläuft sich dieser Vorteil sogar auf 65%. Herr Stenzel belässt es in seiner Diplomarbeit jedoch nicht bei diesem praktischen, auf die Anwendungen bezogenen Teil, sondern befaßt sich auch mit der theoretischen Analyse solcher Online-Routingprobleme. Es gelingt ihm, durch Modifikation existierender Modelle Aussagen über die Kompetitivität von Online-Routingverfahren zu erreichen. Von Bedeutung sind Resultate, die auf eine Betrachtung des Problems als erweitertes Online-Dial-a-Ride Problem mit Konflikten basieren. In geeigneten vereinfachten Modellen, die den Kern der Praxis noch beinhalten, gelingt es ihm, eine Kompetivität von 2 zu erzielen und zu zeigen, dass dies bereits auch eine untere Schranke ist. Herr Stenzel hat mit seiner Arbeit eine weit über das übliche Maß hinausgehende Leistung erbracht, indem er zum einen ein praxisrelevantes Verfahren entwickelt hat, das deutlich besser als das bisher eingesetzte ist. Andererseits hat er die theoretischen Grundlagen für diese Verfahren erarbeitet und ist zu wichtigen Ergebnissen der Kompetitivitätsanalyse gelangt.

Prof. Dr. Peter Brucker mit Herrn Björn Stenzel

Die dritte ausgezeichnete Diplomarbeit »Dynamical Configuration of Optical Telecommunication Networks« von Herrn Andreas Tuchscherer wurde von Martin Grötschel betreut. Sie befasst sich mit dem dynamischen Routing- und Wellenlängenzuordnungs-Problem in transparenten optischen Telekommunikationsnetzen. Diese erlauben das Schalten von Verbindungen entlang von Lichtwegen, die ohne opto-elektronische Konversion über mehrere Bögen eines Netzes verlaufen. Wird eine Verbindung angefordert, so muss online entschieden werden, ob dieser Verbindungswunsch angenommen wird. Wird dies zugesagt, folgt die Entscheidung, entlang welchen Weges die Verbindung geschaltet wird (Routing) und in welcher Wellenlänge die Verbindung geschaltet wird (Wavelenght-Assignment). Thema der Arbeit waren der Entwurf sowie die experimentelle und möglicherweise theoretische Analyse von Online-Algorithmen für o.g. Problem. Herr Tuchscherer präsentiert sowohl einen neuen, lückenlosen Beweis für die Korrektheit eines von ihm benutzten MPS-Algorithmus für das k-kürzeste-Wege-Problem als auch experimentelle Resultate in Form einer selbst programmierten, außerordentlich überdurchschnittlichen Software.

Er stellt hervorragend die mathematischen Begriffsbildungen und Zusammenhänge seiner Arbeit dar. Die Ergebnisse der Arbeit werden aktiv in der Arbeitsgruppe von Herrn Grötschel, insbesondere in Zusammenarbeit mit T-Nova, verwendet. Die Diplomarbeit ist ein ausgezeichnetes Beispiel für Darstellung, Analyse, Modellierung und Simulation einer angewandten Optimierungsaufgabe. Durch die Einbindung neuer Resultate zum k-kürzeste-Wege-Problem hat Herr Tuchscherer in seiner von Modellierung und Simulation dominierten Arbeit zusätzlich einen theoretischen Akzent gesetzt.

Prof. Dr. Peter Brucker mit Herrn Andreas Tuchscherer