## 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* = {*r _{1}*, ...,

*r*} of

_{n}*n*rectangular items into a strip of width 1 and unbounded height, where each rectangular item

*r*has width 0 <

_{i}*w*≤ 1 and height 0 <

_{i}*h*≤ 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

_{i}**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·*h _{max}*, where

*h*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

_{max}*OPT*+ 2·

*h*. Although this improvement looks small,

_{max}*OPT*+ 2·

*h*is already close to

_{max}*OPT*and we expect further improvements to be hard to obtain.

## Recommended Citation

Yu, Andy, "High Multiplicity Strip Packing Problem With Three Rectangle Types" (2019). *Electronic Thesis and Dissertation Repository*. 6684.

https://ir.lib.uwo.ca/etd/6684