In vielen Anwendungen müssen Objekte gestapelt oder in Behälter gepackt werden. Probleme dieser Art werden auch Packprobleme genannt. Neben dem bekannten Bin Packing Problem und dem Rucksackproblem (Knapsack Problem) wird ein weiterer Vertreter dieser Problemklasse als Strip Packing Problem bezeichnet.  In der zweidimensionalen Variante existieren n rechteckige Objekte, welche in einen Strip mit fester Breite und unbeschränkter Höhe zu packen sind, sodass die resultierende Höhe des Strips minimiert wird. Die Objekte müssen so positioniert werden, dass keine Überlappung auftritt. Das beschriebene Problem findet u.a. Anwendung im Stapeln von Objekten, Zuschneiden von Papierrollen oder Textilien sowie in ressourcenbeschränkten Scheduling Problemen.

 

Im Vortrag wird ein lineares Modell für das Strip Packing Problem mit Vorrangbeziehungen vorgestellt: Zwischen den Objekten bestehen Abhängigkeiten, welche die Positionierung im Strip einschränken. Es wird weiterhin untersucht, wie die auf der Erde wirkende Gravitationskraft im Modell umgesetzt werden kann. Das Strip Packing Problem ist NP-schwer und erfordert mitunter hohe Laufzeiten bei Verwendung von exakten Lösungsverfahren. Aus diesem Grund werden Beschleunigungstechniken aufgezeigt.