Electronic Thesis and Dissertation Repository

Thesis Format

Monograph

Degree

Master of Science

Program

Computer Science

Supervisor

Solis-Oba, Roberto

Abstract

The two-dimensional strip packing problem (2D-SPP) involves packing a set R = {r1, ..., rn} of n rectangular items into a strip of width 1 and unbounded height, where each rectangular item ri has width 0 < wi ≤ 1 and height 0 < hi ≤ 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.

Summary for Lay Audience

Consider a set of rectangles of three different sizes. The goal of the three-type strip packing problem (3T-SPP) is to pack these rectangles as densely as possible without overlaps or rotations into a single two-dimensional container of fixed width. In an optimum solution for 3T-SPP where we pack rectangles as densely as possible, we denote with OPT the minimum possible height within which these rectangles can be packed into the container.

Many real-life problems, from industrial manufacturing to scheduling, can be modelled in terms of packing rectangular items of various sizes into a two-dimensional container. One example is stock cutting, which involves cutting a roll of flat material into different rectangle sizes while minimizing the material wasted. Another example is scheduling tasks of various types on processors while minimizing the total completion time; each type of task requires a certain number of adjacent processors for a given amount of time. If we can present a procedure that produces an optimum solution to 3T-SPP, then this procedure can also produce optimum solutions to some of these real-life problems.

The two-dimensional strip packing problem (2D-SPP) is a generalization of 3T-SPP that allows any number of different rectangle sizes. 2D-SPP belongs to a class of problems that currently lack any procedure to efficiently produce optimum solutions. As 3T-SPP is a special case of 2D-SPP, we focus on algorithms or procedures that efficiently find solutions that are not optimal, but are always close to the optimum solutions. We present a procedure for 3T-SPP that efficiently finds a packing of height at most OPT + 5/3·hmax, where hmax is the largest height of the rectangles. This procedure is an improvement over the previously best algorithm that finds a packing of height at most OPT + 2·hmax. Although this improvement looks small, OPT + 2·hmax is already close to OPT and we expect further improvements to be hard to obtain.

Download

Share

COinS