FB6 Mathematik/Informatik/Physik

Institut für Informatik


Osnabrück University navigation and search


Main content

Top content

Genetische Algorithmen für kombinatorische Pack- und Platzierungsprobleme

Leitung Prof. Dr. Oliver Vornberger
Mitarbeiter Dipl.-Inform. Volker Schnecke
Förderung BMBF-Verbundprojekt HYBRID
Laufzeit 04/1994 - 12/1996

Genetische Algorithmen eignen sich sehr gut zur Lösung komplexer, kombinatorischer Optimierungsprobleme.
In diesem Projekt wird die Anwendbarkeit dieser Verfahren auf zweidimensionale Pack- und Platzierungspro-
bleme untersucht. Es handelt sich dabei um Packprobleme mit weiteren Nebenbedingungen. In einer Anwen-
dung, der Generierung von VLSI-Layouts, sind rechteckige Module eines Schaltkreises auf einer minimalen
Fläche zu platzieren und zu verdrahten. In diesem Projekt wird ein Verfahren entwickelt, was die Integration
der Verdrahtung in die Optimierung der Platzierung erlaubt.

Eine weitere Anwendung ist die Bearbeitung des Facility Layout Problems. Hier muss unter Berücksichtigung
von Flüssen zwischen den einzelnen Facilities ein Layout ermittelt werden, welches die Summe der Produkte
dieser Flüsse mit der jeweiligen Distanz zwischen den platzierten Facilities minimiert. Anwendungen des Facility
Layout Problems sind die Einteilung von Büroflächen in Neubauten, die Standortplanung von Betrieben und die
Einrichtung von Fabrikationshallen.