Zwei Heuristiken für Strip-Packing-Probleme

Strip-Packing-Probleme stellen mehrdimensionale Packprobleme dar, die sich im dreidimensionalen Fall wie folgt formulieren lassen. Eine gegebene Menge quaderförmiger Packstücke (Kisten) ist vollständig in einem quaderförmigen und in Längsrichtung offenen Container anzuordnen. Die Kistenanordnung ist derart zu bestimmen, daß die benötigte Containerlänge minimiert wird. Der Beitrag stellt zwei Heuristiken für Strip-Packing-Probleme vor, die jeweils auf zweidimensionale wie auch auf dreidimensionale Probleme anwendbar sind. Die erste Heuristik, ein Tabu-Search-Verfahren, ist vor allem auf Probleme mit schwach heterogenem Kistenvorrat zugeschnitten. Hingegen ist die zweite Heuristik, ein genetischer Algorithmus, vor allem für Probleme mit stark heterogenem Kistenvorrat geeignet. Beide Verfahren berücksichtigen einige praxisrelevante Restriktionen. Die vorgestellten Heuristiken werden einem Test unterzogen, der auch Verfahren anderer Autoren einbezieht. Für den zweidimensionalen Fall werden hierzu bekannte Referenzprobleme aus der Literatur herangezogen, während für den dreidimensionalen Fall neue Benchmarkprobleme vorgeschlagen werden.