FB6 Mathematik/Informatik/Physik

Institut für Informatik


Osnabrück University navigation and search


Main content

Top content

Paralleles zweidimensionales Binpacking

Leitung Prof. Dr. Oliver Vornberger
Mitarbeiter Dr. Berthold Kröger, Dipl.-Math. Peter Schwenderling, Dipl.-Math. Andreas Fritsch
Förderung DFG
Laufzeit 11/1988 - 11/1994

Schwerpunkt der Arbeit war die Entwicklung von genetischen Algorithmen, die aufgrund ihrer Struktur einer massiv-parallelen Bearbeitung zugänglich sind. Als Problemklasse diente das zweidimensionale Packproblem, wo es darum geht, mehrere kleine Rechtecke möglichst verschnittfrei in ein großes zu packen. Als Hardwareplattform kam ein Multiprozessorsystem mit 64 Trans­putern zum Einsatz. Nach einer aufwändigen Analyse der Beschaffenheit des Lösungsraums wurden die problemspezifischen Datenstrukturen entwickelt, die für eine effiziente Umsetzung des evolutionären Konzepts erforderlich waren. Als Konse­quenz entstand ein Approximationsverfahren, welches alle in der Literatur bekannten Verfahren in puncto Packqualität ge­schlagen hat.