Electronic Thesis and Dissertation Repository

Thesis Format

Monograph

Degree

Master of Science

Program

Computer Science

Supervisor

Solis-Oba, Roberto

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.

Summary for Lay Audience

Packing problems typically involve maximizing the number of objects that can be placed into a container or minimizing the number of containers needed to hold a set of objects. Many industrial problems can be modeled as packing problems involving rectangles and squares.

Solutions for rectangle packing problems are useful, for example, for loading pallets and shipping containers for storage and transport, for designing transistor layouts for computer chips, and for optimizing workflow in a workplace. There is a quantifiable difference between good and bad solutions in the industrial environment. Wasted space during storage and transport costs companies resources: time might need to be spent re-packing containers, additional containers might need to be shipped, or product might be lost if certain weight restrictions are not satisfied. Many companies still use trial-and-error approaches while packing items for storage and transport.

In this thesis we consider the two-dimensional high multiplicity strip packing problem. In this problem 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. We consider the problem for the cases when there are 3 different rectangle types and 4 different rectangle types.

Efficient algorithms for packing problems translate into improved industrial practices that reduce company expenses and improve product delivery. Furthermore, algorithm design techniques specifically developed for rectangle and square packing problems contribute to the design of efficient algorithms for other types of optimization problems. As research into packing problems expands, more industrial problems will be solved using these algorithms and more packing and optimization problems will be able to leverage the algorithmic techniques that are discovered.

Download

Share

COinS