Fachbereich 6 Mathematik/Informatik

Institut für Informatik


Navigation und Suche der Universität Osnabrück


Hauptinhalt

Topinformationen

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.