Uni-Logo Institut für Informatik - Arbeitsgruppe Medieninformatik

Genetische Algorithmen für kombinatorische Pack und Platzierungsprobleme

Projektlaufzeit: April 1994 - Dezember 1996
Projektleiter: Prof. Dr. Oliver Vornberger
Projektmitarbeiter: Dipl.-Inform. Volker Schnecke
Studentische Hilfskräfte: Gunther Imeyer (Juli 94 - Dezember 94)
Frank Lauxtermann (Juli 94 - Dezember 95, Mai 96 - September 96)
Curd Reinert (Januar 96 - September 96)
Andreas Rother (November 95 - September 96)
Finanzierung: BMBF-Verbundprojekt HYBRID


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

Eine weitere Anwendung ist die Bearbeitung des Facility Layout Problems. Hier muß 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 plazierten 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.