**
Efficient Algorithms for 2-D Rectangle packing
**

British German Academic Research Collaboration Programme

British German Academic Research Collaboration Programme

This is a project to implement and evaluate known shelf algorithms for 2-D rectangle packing problems. The goal is essentially twofold:

- To implement algorithms (code design) and identify bottlenecks (testing and evaluation);
- To provide improvements (code redesign, testing and evaluation).

The British group (from University of Liverpool) is presented by

- Dr. Prudence Wong (group leader)
- Dr. Russ Martin (faculty member)
- Chang Su (PhD student)
- Xiaohui Zhang (PhD student)

- Prof. Dr. Klaus Jansen (group leader)
- Aleksei V. Fishkin (Siemens AG, Munich, Germany)
- Ralf Thoele
- Florian Diedrich (PhD student)
- Oezguen Bayramoglu (diploma student)

## Key words

Rectangle packing, approximation, shelf algorithms## Objectives

New fast algorithmic solutions for the 2D-rectangle packing problem can have a great impact on a variety of important applications from Computer Science and Operations Research, e.g. cutting stock, VLSI design, image processing, bandwidth management, multiprocessor scheduling, just to name a few. So far, the following versions of the problem have been studied:- 2D-Strip-Packing: Pack a given set of 2D-rectangles into a vertical strip of unit width so that the height to which the strip is filled is minimized.
- 2D-Bin-Packing: pack a given set of 2D-rectangles into unit square bins so that the number of bins is minimized.
- 2D-Storage-Packing: Pack a subset of a given set of 2D-rectangles with profits into an unit square storage so that the total profit of the packed rectangles is maximized.

Indeed, one can use exact methods like Integer Linear Programming, heuristic methods like Local Search and enumeration methods like Branch-and-Bound. Even if these methods could prove to be useful, the underlying algorithms are either very slow or produce very sub-optimal packings. In contrast, we aim at so-called approximation algorithms which run fast and produce near-optimal packings with quality guarantees.

Recently, we have developed a number of best quality guarantee (1+ε)-approximation algorithms. However, the design techniques used in these algorithms are quite complicated. In this project we propose to implement and evaluate so-called shelf algorithms. In the design of such algorithms, a simple shelf technique is used: order the rectangles according to a sorting rule like decreasing width, increasing height, etc. and then greedily pack them one by one in this order overpackage shelves according to some rule, like Bottom-Left, Next-Fit, First-Fit, Best-Fit, and so on. This allows a simple code design, a very fast running time, and a relatively good quality guarantee.