Simulationen – Optimierung

Pictures of the Future

Simulationen – Optimierung

Mathematik weist den Weg zum Optimum

Mehr Produktivität bei geringeren Kosten – davon träumt jeder Manager. Doch die wenigsten wissen, dass sich viele Entscheidungsprozesse und Automatisierungsaufgaben mittels Mathematik optimieren lassen. Siemens hat dafür ein Fachzentrum bei Corporate Technology eingerichtet.

Dr. Johannes Nierwetberg zeigt, wie sich der Weg zum Ziel (blau) mathematisch optimieren lässt: Algorithmen berechnen die Ideallinie (dicke gelbe Linie), indem sie sich lokal jeweils für den besten der kurzen Wege entscheiden

Eigentlich ist die Regel klar: Zeigt die Ampel Rot, muss man halten, bei Grün darf man fahren. Und bei Gelb? Flotte Fahrer erfinden hier Farbschattierungen wie dunkelgelb oder hellorange, um mit einigermaßen reinem Gewissen über die Kreuzung rasen zu können. Der Fahrer trifft eine Entscheidung mit Konsequenzen – vielleicht ist er schneller am Ziel, oder er wird geblitzt und muss Strafe zahlen.

Für Mathematiker ist die Entscheidung an der Ampel ein klassisches Optimierungsproblem, bei dem die eingesparte Fahrzeit und die Kosten des Strafzettels abgewogen werden müssen. Auch in Firmen gilt es ständig, Entscheidungen zu treffen, nur dass diese – wenn sie sich als falsch erweisen – teurer kommen als ein Strafzettel. Zudem sind hier oft viele Lösungswege möglich, deren Zusammenhänge nicht mehr zu durchblicken sind. "In komplexen, vernetzten und dynamischen Situationen macht unser Gehirn Fehler", warnt der Bamberger Kognitionsforscher Prof. Dietrich Dörner.

Gut, dass uns elektronische Gehirne einen Teil der Last abnehmen. Gefüttert mit mathematischen Algorithmen optimieren Computer heute viele Prozesse. Einer der Pioniere dieser Disziplin ist Prof. Ulrich Lauther bei Siemens Corporate Technology (CT) in München. Der gelernte Elektrotechniker, der an den Universitäten Berkeley und Stuttgart gelehrt hat, bekam bei Siemens 1992 eine harte Nuss zu knacken. Lauther sollte das Telefonnetz der indischen Drei-Millionen-Stadt Pune optimieren. Das Rückgrat des Netzes sollte aus Glasfasern bestehen, die letzten 300 m zu den Häusern aus Kupferkabeln – dazwischen Verteiler (Multiplexer) für jeweils maximal 60 Leitungen. Lauthers Vorgabe: die Gesamtkosten für Leitungen, Multiplexer, Erdarbeiten und so weiter zu minimieren. Dank seiner Computeralgorithmen löste er die knifflige Aufgabe mit Bravour: 15 % Kostenersparnis im Vergleich zum herkömmlichen, von Hand gezeichneten Plan sprangen heraus. Außerdem war sein Resultat korrekt – im Gegensatz zum Plan auf Papier, bei dem an einem Multiplexer aus Versehen auch mal 70 Haushalte angeschlossen waren.

Offensichtliche Wettbewerbsvorteile. Der Erfolg sprach sich herum. Heute kümmern sich 20 Mitarbeiter, meist Mathematiker, im Fachzentrum "Diskrete Optimierung" bei Siemens CT um alles, was sich mathematisch optimieren lässt. "Das Tolle an der Optimierung ist, dass sie sich beim Kunden sofort als Wettbewerbsvorteil bemerkbar macht", sagt Dr. Johannes Nierwetberg, der das Fachzentrum leitet. Ein zweistelliger Prozentsatz bei Zeit- und Kostenersparnis sei fast immer drin. Nierwetbergs Abteilung hat dazu einen ganzen Werkzeugkasten mit Algorithmen entwickelt: Damit konnte etwa die Komponentenbereitstellung beim Bestücken von Leiterplatten optimiert werden, was den Durchsatz um 13 % erhöhte. Doch obwohl Nierwetberg die Vorteile auf Euro und Cent beziffern kann, fällt die "Evangelisierung" mitunter schwer. Seine Experten müssten oft den Managern erst klarmachen, dass sich viele ihrer Probleme mathematisch lösen lassen.

Für einen Kunden in der Stahlproduktion hat Siemens das Auswalzen von Rohstahlblöcken unter die Lupe genommen. Weil die Rotation der Walzen, die Transportzeiten, die Abkühlung der Blöcke, die Bearbeitungszeit und die Eingriffe der Bediener nicht genau vorhersagbar sind, muss ein Steuerprogramm, das den Durchsatz der Walzstraße erhöhen soll, diese Unwägbarkeiten einkalkulieren. "Wie ein Schachspieler berechnet unsere Software alle paar Sekunden die beste Strategie", sagt Nierwetberg. Meist reicht die Zeit für einen "optimalen Zug" aus, wenn nicht, dann macht die Software einen "sicheren Zug" und steuert den Durchlauf so, dass es zu keinen Problemen kommt. Die Software läuft mittlerweile erfolgreich in mehreren Stahlwerken: Das Produktionstempo wurde deutlich gesteigert.

Mathematik auf der Spitze: Wie labil der Zustand am mathematischen Optimum sein kann, zeigt Siemens-Forscher Prof. Albert Gilg. Wie auf einem Berggipfel droht hier nach allen Seiten die Gefahr, abzurutschen

Mit denselben mathematischen Prinzipien lässt sich auch die Datenübertragung über Kabel oder Funk beschleunigen. So werden bei automatischen Produktionsanlagen große Datenmengen zwischen Sensoren, Aktoren und Rechnern hin und her geschickt. Das Zusammenspiel klappt nur, wenn die richtigen Daten zur richtigen Zeit am richtigen Ort bereitstehen. Ein neues Konzept sieht vor, an Stelle spezieller Busleitungen Standard-Ethernetkabel einzusetzen. Doch beim klassischen Ethernet-Protokoll könnten Staus entstehen, wenn zu viele Datenpakete eine Leitung belegen – die Synchronisation der Antriebe in der Produktionsstraße würde aus dem Takt geraten. Daher müssen der Weg der Datenpakete und ihre zeitliche Abfolge vorab geplant werden. Solche "Scheduling"-Probleme, bei denen bestimmte Aktionen zu bestimmten Zeiten erfolgen müssen, kennt jeder aus dem Alltag. Bauherren können ein Lied von Handwerkern singen, die das Dach decken wollen, obwohl der Rohbau noch gar nicht steht.

Datenverkehr effizient planen. Auch Profinet RT, eine Automatisierungslösung des Siemens-Bereichs Automation and Drives, hatte mit diesen Einschränkungen zu kämpfen. Für die Version Profinet IRT hat Ulrich Lauther ein Software-Werkzeug zur Planung von Echtzeitnachrichten in einem Netz aus Ethernetkabeln und zeitsynchronisierten Knoten entwickelt – daher der Name Isochronous Real-Time (IRT). Es errechnet, wie und wann welche Daten über das Netzwerk geschickt werden, so dass der Zeittakt eingehalten und möglichst wenig Zeit pro Zyklus verbraucht wird. Die dank der effizienten Planung freigehaltenen Zeiten können für herkömmlichen TCP/IP-Verkehr, etwa für Browser oder Software-Downloads, genutzt werden. Das wichtigste Prinzip: Zeitkritische Daten haben Vorfahrt. Sie werden zu immer gleichen Zeiten in den Informationsfluss eingespeist und erreichen zuverlässig und fast in Echtzeit ihren Empfänger – weniger wichtige Daten teilen sich die übrige Bandbreite.

Zum Vergleich: Ein Befehlszyklus dauert bei Profinet IRT weniger als 1 ms, beim Vorgänger Profinet RT waren es 10, bei Standard-Internetverbindungen 100 ms. Die Optimierung dauert nur einen Wimpernschlag. Ein Netzwerk aus 124 Knoten – etwa Maschinenantrieben –, 465 Nachrichten und 576 Empfängern benötigt weniger als eine Sekunde Rechenzeit für einen Zeitplan, wann welche Nachricht über welchen Weg an welchen Empfänger geschickt wird.

Profinet IRT wird beim Pilotkunden MAN Roland, einem Hersteller von Druckmaschinen in Offenbach, bereits mit Erfolg eingesetzt. Die Walzen einer Illustrations-Druckmaschine rotieren so schnell, dass sie 90 000 Druckseiten pro Stunde schaffen. Dabei sind sie so präzise, dass sie die Farbpunkte auf 5 µm genau übereinander drucken. In der ganzen Anlage weichen die Signale jetzt nur noch 0,5 ms vom vorgegebenen Zeitplan ab. Das steigert das Drucktempo, erhöht die Präzision und beugt Papierriss vor. Alle künftigen Automatisierungslösungen von Siemens werden auf Profinet IRT basieren, das seit Frühjahr 2006 auf dem Markt ist. Mitgeliefert wird ein Engineering-Werkzeug mit dem Optimierungsalgorithmus von Ulrich Lauther.

Beschleunigung um Faktor 200. Noch kritischer, weil teurer, ist die Datenübertragung per Funk. So wird bei einem Satellitenmautsystem, wie es in Deutschland existiert, von Zeit zu Zeit neue Software in die On-Board-Units (OBU) der Fahrzeuge geladen, etwa wenn neue kostenpflichtige Straßen hinzukommen. Bislang mussten die Lkw in die Werkstatt, künftig soll neue Software automatisch per Mobilfunk aufgespielt werden. In Deutschland sind fast eine halbe Million OBU unterwegs, in anderen Ländern, die eine Maut für Pkw planen, werden es noch deutlich mehr sein. Jedes Mal die komplette Software mit etwa 2,5 Mbyte auszutauschen, wäre enorm teuer.

Ulrich Lauther hat ein Verfahren entwickelt, das die Software-Updates auf nur 12 kbyte und damit auf ein Zweihundertstel schrumpfen lässt. Die Datenübertragung ist so in Sekundenschnelle erledigt. Der Trick: Lauthers Algorithmus überträgt nur die Differenz aus zwei Dateien. Dabei errechnet der Algorithmus nicht irgendeinen Unterschied, etwa indem er einfach die geänderten Passagen in der Software ausschneidet, sondern er findet stets die kleinstmögliche Differenz zwischen altem und neuem Programmcode, was Lauther auch mathematisch beweisen kann.

Ein vergleichbares Projekt führt Lauther auch für BenQ, den neuen Besitzer der Siemens-Mobilfunksparte, durch. Die Software eines Handys verschlingt heute 25 Mbyte. Updates, die Fehler ausmerzen oder neue Funktionen enthalten, sollen aber nur wenige Kilobyte groß sein, weil sie künftig automatisch per Mobilfunk geladen werden sollen.

Auch mit den Mobilfunknetzen selbst beschäftigt sich das Fachzentrum. Dr. Hans Heller entwickelt Algorithmen, um die optimalen Standorte für Mobilfunkmasten zu finden, sodass die Netzabdeckung fast lückenlos und die Kosten dennoch gering sind. "Da ist noch eine Menge rauszuholen", verspricht der Mathematiker. Siemens möchte beim Aufbau von UMTS-Netzen möglichst die vorhandenen Masten der GSM-Infrastruktur nutzen, um den Kunden Kosten zu ersparen. Allerdings muss eine optimal platzierte GSM-Basisstation nicht unbedingt auch für UMTS optimal sein. Die Zeit drängt: Gerade baut Siemens in Shanghai ein UMTS-Netz auf, das Heller als Testfall durchspielt. Wenn die Ergebnisse überzeugen, wird Hellers Optimierungsalgorithmus in das Site-Selection-Programm integriert, das der Bereich Communications erstmals in Shanghai einsetzen will.
Bernd Müller

Gierig und tabu – Optimierungsverfahren

Der Koch einer Klinik soll mit vorgegebenen Lebensmittelnund wenig Geld eine ausgewogene Ernährung zusammenstellen. Diese Knobelei ist ein Klassiker der mathematischen Optimierung. Man bezeichnet diese Aufgabe als linear, weil die Variablen ohne Sprünge voneinander abhängen: doppelt so viel Orangensaft gleich doppelt so viele Vitamine. Die optimale Lösung findet der Koch vielleicht durch Wälzen von Nährwert- und Preistabellen. Doch in Produktionsprozessen lauern noch viel komplexere Optimierungsprobleme. In der 60-jährigen Geschichte der mathematischen Optimierung haben Mathematiker viele Algorithmen ausgetüftelt – die ersten linearen Verfahren dienten im Zweiten Weltkrieg zur Versorgungsplanung mit Ausrüstung und Lebensmitteln. Software für lineare Probleme gibt es heute quasi von der Stange zu kaufen.

Neuer sind Algorithmen der diskreten Optimierung, bei denen sich die Variablen nur in zählbaren (diskreten) Schritten ändern: Ein gekochtes Ei wird meist ganz oder gar nicht gegessen, das macht es für den Koch schwieriger, das richtige Maß an Eiweiß und Cholesterin zu treffen. Ein wichtiger Teil des Know-hows, das im Siemens-Fachzentrum "Diskrete Optimierung" gebündelt ist, besteht darin, aus den vielen Algorithmen den zu finden, der zum Problem passt. Um nicht jedes Mal das Rad neu erfinden zu müssen, hat Prof. Ulrich Lauther die C⁺⁺-Klassenbibliothek TURBO aufgebaut, einen Baukasten mit bekannten und weiterentwickelten Algorithmen zur diskreten Optimierung in der Programmiersprache C⁺⁺. "Die Algorithmen sind vielfach getestet und weitgehend fehlerfrei, was bei solchen komplexen mathematischen Werkzeugen keineswegs selbstverständlich ist", sagt Lauther. Er kenne kein anderes Unternehmen, das über einen so gut bestückten Werkzeugkasten zur Optimierung verfüge. Einen Universalalgorithmus, der alle Aufgaben mit einem Schlag erledigt, gibt es zwar nicht, doch viele Optimierungsaufgaben lassen sich in Teilprobleme zerlegen und mit den Algorithmen der TURBO-Bibliothek lösen. Dabei kommen in der Regel 70 % des Programmcodes aus der Bibliothek, 30 % müssen projektspezifisch neu erzeugt werden. Bei Profinet IRT stammen fast drei Viertel der 23 000 Programmzeilen des Optimierungsalgorithmus aus der Bibliothek. Hier eine kleine Auswahl von Strategien der diskreten Optimierung:

• Greedy: Bei diesem "gierigen" Algorithmus wählt man aus einem vorgegebenen Startzustand Schritt für Schritt den nächsten Zustand so, dass der Gewinn möglichst groß wird. Gut geeignet ist dies etwa für das Problem des Handlungsreisenden, bei dem man eine möglichst kurze Reiseroute durch mehrere Städte finden möchte und der auch beim Entwurf von Leiterbahnen auf Mikrochips zum Einsatz kommt. Nicht immer führt jedoch ein Greedy-Algorithmus zur optimalen Lösung. So kann es bei der Platzierung von Mobilfunkmasten vorteilhaft sein, einige Masten ungünstiger zu platzieren bei insgesamt dennoch besserer Netzabdeckung und geringeren Kosten.
• Tabu-Suche: Im Gegensatz zum Greedy-Algorithmus werden bei der Tabu-Suche auch – möglichst geringe – Verschlechterungen zugelassen. Damit sich das Verfahren nicht im Kreis dreht, werden die zuletzt durchgeführten Schritte als tabu markiert – sie dürfen nicht rückgängig gemacht werden. Damit findet man auch Lösungen außerhalb der Reichweite eines Greedy-Verfahrens.
• Simulated annealing: Mit diesem Algorithmus kann es gelingen, das "globale Minimum" eines Systems zu finden. Im Allgemeinen ähnelt die Abhängigkeit von vielen Parametern einer Hügellandschaft – eine herabrollende Kugel wird selten im globalen Minimum landen, weil sie vorher in einem der vielen lokalen Minima stecken bleibt. Der Annealing-Algorithmus verwendet eine Analogie aus der Festkörpertheorie – die Temperaturschwingung der Atome hilft, aus lokalen Minima zu entkommen. Beim langsamen Abkühlen landet das System vorzugsweise im globalen Minimum, analog zum Aushärten (annealing) von Metallen. Das Verfahren wird etwa benutzt, um die gegenseitige Beeinflussung von Mobilfunkfrequenzen in benachbarten Regionen zu minimieren.