Effizienzsteigerung durch mathematische Optimierung

Arbeitsgruppe der TU Berlin entwickelt Algorithmen für die Praxis/Präsentation auf der CeBIT

Immer mehr Industrie- und Dienstleistungsunternehmen erkennen, daß mathematische Optimierung der Schlüssel zu ungeahnten Effizienzsteigerungen ist. Die Arbeitsgruppe "Kombinatorische Optimierung und Graphenalgorithmen" am Fachbereich Mathematik der TU Berlin entwickelt mathematische Verfahren, die Firmen bei der Planung von Arbeitsabläufen, Produktionsprozessen oder dem kostengünstigen Angebot von Dienstleistungen unterstützen. Zu den Einsatzgebieten dieser Verfahren gehören unter anderem der Entwurf von Telekommunikations- und Informationsnetzen, die Unterstützung von Produktions- und Ablaufplanung in der chemischen Industrie oder in der Baubranche, die Netzverfeinerung von Computer-Aided design (CAD) oder die Optimierung von Navigationssystemen im Straßenverkehr.

Deutlich wird der Vorteil des Einsatzes mathematischer Optimierung an einer Kooperation der Arbeitsgruppe mit der Deutschen Telekom AG. Die Telekom bietet Mobilfunkbetreibern und anderen Kunden an, in ihrem Kommunikationsnetz permanente Verbindungen zwischen zwei Orten (z.B. Hamburg und München) zu mieten, wobei diese Verbindungen möglichst kostengünstig und störungsfrei sein sollten. Bisher wurden die gewünschten Verbindungen unabhängig voneinander auf dem Leitungsnetz realisiert. Dabei kam es häufig vor, daß sich verschiedene Verbindungen, wie etwa Hamburg und München oder Hamburg und Berlin, streckenweise ein Kabelstück teilen mußten. Bei einer Störung auf der gemeinsamen Strecke würden dann beide Verbindungen unterbrochen. Im Rahmen der Kooperation hat die Arbeitsgruppe an der TU Berlin ein algorithmisches Verfahren entwickelt, das computergestützt die billigsten Verbindungen zwischen zwei Orten berechnet und dabei garantiert, daß je zwei Verbindungen nicht mehr über gemeinsame Kabelabschnitte laufen. Dabei werden auftretende Mehrfachbenutzungen von Kabelstücken mit höheren Kosten "bestraft", wodurch sie in einer weiteren Berechnung der Verbindungen vermieden werden. Das von der Arbeitsgruppe entwickelte Verfahren sucht so lange nach einer optimalen Verbindung, bis sicher gestellt ist, daß es keine bessere Schaltung geben kann.

Für die Ablaufplanung von Produktionsprozessen entwickelte die Arbeitsgruppe gemeinsam mit der BASF AG in Ludwigshafen ein weiteres Optimierungsverfahren, in dem mathematische Methoden zum Einsatz kommen. Dort geht es um die Herstellung von chemischen Produkten in einem Anlagenpark mit unterschiedlichen Maschinen. Das Problem ist, daß die Produktion der Produkte in eine Reihe einzelner Arbeitsschritte wie etwa das Anrühren, Erhitzen, Mischen oder Abkühlen einzelner Substanzen unterteilt ist, die zeitlich voneinander abhängig sind. Das heißt in erster Linie, daß bestimmte Prozesse erst starten können, wenn andere abgeschlossen sind bzw. ihre Zwischenprodukte zur Verfügung stehen. Auch müssen zeitliche Maximalabstände zwischen verschiedenen Produktionsschritten beachtet werden, die nicht überschritten werden dürfen. Für die einzelnen Produktionsschritte wird jeweils eine bestimmte Anzahl entsprechend qualifizierter Mitarbeiter benötigt, die aber nur begrenzt zur Verfügung stehen (knappe Ressourcen).

Die Aufgabe eines Planers im Unternehmen besteht nun darin, einen Produktionsplan zu erstellen, der unter Berücksichtigung der zur Verfügung stehenden Maschinen und Mitarbeiter die Herstellung aller Produkte in minimaler Gesamtdauer gewährleistet. Die Arbeitsgruppe "Kombinatorische Optimierung und Graphenalgorithmen" hat hierfür ein maßgeschneidertes "Branch-and-Bound" Verfahren entwickelt, mit dem sich eine solche Ablaufplanung effektiv am Computer realisieren läßt. Dabei wird ermittelt, zu welchem Zeitpunkt welcher Prozeß eingeplant werden soll, und welche Anzahl von Mitarbeitern zu welcher Zeit zur Verfügung stehen muß. Ähnliche Verfahren werden zum Beispiel auch bei der Planung von Bauvorhaben eingesetzt, wobei es zusätzlich möglich ist, auch Unsicherheitsfaktoren wie etwa Wettereinflüsse zu berücksichtigen.

Die Arbeitsgruppe "Kombinatorische Optimierung und Graphenalgorithmen" der TU Berlin bietet ihr Know-how allen Interessenten an, die durch speziell angepaßte Optimierungsverfahren ihre Wettbewerbsfähigkeit steigern möchten. Auf der diesjährigen CeBIT stellt die Arbeitsgruppe einige ihrer Projekte vor und steht für Gespräche mit weiteren Interessenten am Stand des "Forschungsmarktes Berlin" (Stand D23, Halle 16) zur Verfügung.

Mirjam Schmidt