Mainzer Computer-Algorithmus ausgezeichnet
Das US-amerikanische Time Magazine hat einen in Mainz entwickelten Computer-Algorithmus als eine der 50 wichtigsten Erfindungen des Jahres 2009 bezeichnet. Der Algorithmus wurde an der Universität Mainz von Dr. Johannes Josef Schneider, Professor Dr. Elmar Schömer und André Müller entwickelt und dient dem Lösen von Packproblemen.
Konkret löst die Rechenvorschrift die Aufgabe, wie man mehrere, unterschiedlich große Scheiben so in einem Kreis anordnen kann, dass sie möglichst wenig Platz brauchen. Nach Angaben der Universität Mainz konnte Schneider mit seiner Lösung die bisherigen Weltrekorde übertreffen, die bei einem internationalen Wettbewerb zu diesem Problem aufgestellt wurden.
“Dabei ist unser Algorithmus nicht nur für das Kreisscheiben-Problem bestens geeignet, sondern er löst auch andere Packprobleme und lässt sich zudem auf Fragestellungen aus der Tourenplanung, der Produktionsplanung oder der Personaleinsatzplanung anwenden”, sagt Schneider.
Praktische Anwendungen des Algorithmus gibt es nach diesen Angaben in der Autoindustrie: Mit Hilfe des Computers kann beispielsweise für die Endmontage ermittelt werden, in welcher Reihenfolge die vorgefertigten Karosserien aufs Fließband gebracht werden müssen, um kostengünstig zu produzieren. Derzeit untersucht die Gruppe für einen großen deutschen Automobilhersteller, wie man das Volumen eines Kofferraums am besten ausnutzen kann. Aber auch für Transportunternehmen und in der Logistik können Optimierungsalgorithmen wichtig sein.
Das beste Lösungsverfahren finden die Mainzer Wissenschaftler, indem sie sich durch Annäherung an die Lösung herantasten. Dazu werden mit sogenannten Monte-Carlo-Simulationen zufällige Ereignisse am Computer simuliert. “Das geht wie im Casino, wo zufällig die Zahl zwölf am Roulette-Tisch fällt, so erzeugt der Computer zufällig eine Anordnung”, erläutert Schneider.
Im Beispiel mit den Kreisscheiben versetzt der Rechner dann eine der Scheiben irgendwo hin und vergleicht diese neue Lösung mit der vorherigen. Diese Veränderung wird rückgängig gemacht, wenn das Ausmaß der Verschlechterung zu groß ist, ansonsten bleibt es bei der neuen Lösung. “Auf diese Weise verändert man die Anordnung der Kreisscheiben Schritt um Schritt, so lange, bis das Endergebnis vorliegt.”
