Top content

Paralleles zweidimensionales Binpacking

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.