Efficient Algorithms for 2-D Rectangle packing
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:

In the end, we expect to have a software package with all coded algorithms, and a website with all testing and evaluation results. There are two groups in the project.
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)
The German group (from University of Kiel) is presented by
  • Prof. Dr. Klaus Jansen (group leader)
  • Aleksei V. Fishkin (Siemens AG, Munich, Germany)
  • Ralf Thoele
  • Florian Diedrich (PhD student)
  • Oezguen Bayramoglu (diploma student)
The experience of British group in codeing and experimental work and theoretical knowledge on approximation algorithms for packing problems by the German group can be used complementary to each other. In addition to expected results, this project primary aims at training the students in both groups.

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.
Even very simple cases of these problems are known to be NP-hard, and hence, it is very likely that no efficient algorithms for them exist. So, we should look for alternative algorithmic solutions.
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.