stiefels.net Just another WordPress weblog

Best-Fit Placement Heuristic

## Introduction

Often one has to solve the problem of arranging objects so that they use as less room as possible. In the days before Christmas, for example, people try to utilize the expensive wrapping paper fully in order to save to money for a second roll. Depending on the arrangement of the presents this may work, or not. In the industry, a can factory tries to stamp different sized cans out of a roll of sheet metal. To minimize the waste (and to save money) the company has to think about the cutting of the metal sheet.
Both of these examples describe a problem known as the [two-dimensional cutting stock problem](http://en.wikipedia.org/wiki/Cutting_stock_problem).

Although there is no algorithm available which produces an optimal solution to this problem several heuristics can identify usable solutions within an acceptable timeframe.
One of these heuristics is the *Best-Fit* heuristic (described [here](http://or.journal.informs.org/cgi/content/abstract/52/4/655)), developed by [E. K. Burke](http://www.cs.nott.ac.uk/~ekb/), [G. Kendall](http://www.cs.nott.ac.uk/~gxk/) and [G. Whitwell](http://www.cs.nott.ac.uk/~gxw/home-gxw.shtml) of the [University of Nottingham](http://www.nottingham.ac.uk/).

This project visualizes the different steps the *Best-Fit* heuristic performs in order to gain an acceptable solution (placing rectangles in a way so that waste is reduced) for a given set of different sized rectangles. We (Benjamin Clauss and I) started this project in the context of an assignment for our [university](http://www.hs-esslingen.de).

Beside the original paper written by the people mentioned above, you also may want to read the more [detailed description of this project](http://www.stiefels.net/wp-content/uploads/2009/07/Dokumentation.pdf) (german) to get comfortable with the terminology and the basic ideas behind this heuristic.

## Requirements

The tools described below are written in Java, so it should work on all systems that can run a Java VM. As we make use of the JAXB API, using Java 1.6 is recommended (as it includes JAXB). Previous versions of Java may also work but are untested.

## The XML file format

The rectangles (i.e. their dimensions) which define the actual problem are stored in a XML file which may look like the following:

247
184


202
239

Each rectangle has:

* an ID (to identify the rectangle later on)
* a height
* and a width

Currently, the width of the stockroll (that is the place where the rectangles are being placed) is fixed to 400 units. Therefore, the size of the rectangle is constrained so that at least one dimension has to be equal or less than 400 units.

For convenience, the JAR file also includes a random generator which creates a XML file with randomly sized rectangles.

java -cp scp.jar scp.cli.Generator testdata.xml -m 250 -n 500

This call generates a file *testdata.xml* with 500 rectangles each having a maximum size of 250 units (in each direction).

## Applying the Heuristic

Now, as we have a concrete problem (that is, arranging the rectangles in a way that we reduce waste) we can apply the *Best-Fit* heuristic to solve this for us.

java -cp scp.jar scp.cli.Solver testdata.xml

This call takes the content of the testdata.xml file, solves it (by applying the *Best-Fit* heuristic), and enhances the XML file with the solution (in a step-by-step manner).

## Watching the *Best-Fit* Heuristic Work

After solving the problem the XML file contains the problem and the step-by-step solution. Trying to read the XML file in order to follow the steps made by the heuristic is hard and isn't much fun. For this, we wrote a tool that does a great job visualizing each step from the beginning to the end.

This *Best-Fit* "player" has controls that allow you to watch the heuristic like a movie, with different playback speeds, reset, and a way to play single steps backwards.

You can start the player by invoking the following command:

java -cp scp.jar scp.gui.StockCutterGUI

## Downloads

* [Project documentation](http://www.stiefels.net/wp-content/uploads/2009/07/Dokumentation.pdf) (german)
* [Java JAR file](http://www.stiefels.net/wp-content/uploads/2009/07/scp.jar) (scp.jar)
* [Source code](http://github.com/simonboots/BestFitPlacementHeuristic/)

## Feedback

Feedback is always welcome. Just leave a comment or write an [e-mail](/contact).