Electronic Thesis and Dissertation Repository

High Multiplicity Strip Packing

Andrew Bloch-Hansen, The University of Western Ontario

Abstract

In the two-dimensional high multiplicity strip packing problem (HMSPP), we are given k distinct rectangle types, where each rectangle type Ti has ni rectangles each with width 0 < wi and height 0 < hi The goal is to pack these rectangles into a strip of width 1, without rotating or overlapping the rectangles, such that the total height of the packing is minimized.

Let OPT(I) be the optimal height of HMSPP on input I. In this thesis, we consider HMSPP for the case when k = 3 and present an OPT(I) + 5/3 polynomial time approximation algorithm for it. Additionally, we consider HMSPP for the case when k = 4 and present an OPT(I) + 5/2 polynomial time approximation algorithm for it.