Upper bounds for heuristic approaches to the strip packing problem. (30th May 2014)

• Record Type: Journal Article
• Authors: Buchwald, Torsten; Scheithauer, Guntram
• Is Part Of: International transactions in operational research. Volume 23:Number 1/2(2016:Jan./Mar.)
• Page Start: 93
• Page End: 119
• Publication Date: 2014-05-30
• Subjects: cutting and packing -- strip packing problem -- performance ratio; Operations research -- Periodicals; 003
• DOI: 10.1111/itor.12100
• Languages: English
• ISSNs: 0969-6016

Abstract

Abstract: We consider the 2D and 3D strip packing problem (SPP): given a set of rectangular items and a strip, find the minimal height needed to pack all items. Rotation of the items is not permitted. We present an algorithm for the 2D SPP, which improves the packing of the well‐known FFDH heuristic and state theoretical results for this algorithm. Furthermore, we prove new upper bounds for the 3D SPP in special cases. Moreover, we present an implementation of the FFDH heuristic for the 3D case, which is used to construct a new algorithm, called COMB‐3D heuristic, with absolute performance ratio of at most 5. Based on the new algorithm, we also prove a general upper bound for the optimal height, which depends on the continuous lower bound and the maximum height lower bound, and we show that the combination of both lower bounds also has an absolute worst‐case performance ratio of at most 5.