High Multiplicity Strip Packing Problem With Three Rectangle Types

Andy Yu, The University of Western Ontario

Abstract

The two-dimensional strip packing problem (2D-SPP) involves packing a set R = {r₁, ..., r_n} of n rectangular items into a strip of width 1 and unbounded height, where each rectangular item r_i has width 0 < w_i ≤ 1 and height 0 < h_i ≤ 1. The objective is to find a packing for all these items, without overlaps or rotations, that minimizes the total height of the strip used. 2D-SPP is strongly NP-hard and has practical applications including stock cutting, scheduling, and reducing peak power demand in smart-grids.

This thesis considers a special case of 2D-SPP in which the set of rectangular items R has three distinct rectangle sizes or types. We present a new OPT + 5/3 polynomial-time approximation algorithm, where OPT is the value of an optimum solution. This algorithm is an improvement over the previously best OPT + 2 polynomial-time approximation algorithm for the problem.