by Heidi Smith
The problem of finding an optimal solution for the strip packing problem is NP-complete, so research has focussed mainly on developing approximation algorithms to solve it. Approximation algorithms find near optimal solutions but do not guarantee to find the optimal packing for every set of data. Most algorithms pack the rectangles into the bin using one of five approaches: bottom left, level-orientated, split, shelf or hybrid. I have chosen to concentrate on algorithms which involve packing at various levels. They are termed level-by-level packings. These are the level-orientated and shelf algorithms. However, I have briefly explained the main characteristics of all five types, below.
Bottom-left algorithm
The Bottom-up Left-justified algorithm requires each successive rectangle to be placed as near to the bottom of the bin as it will fit and then as far to the left as it can go at that level without overlapping any other packed rectangles. The list of rectangles require no pre-sorting
Level-oriented algorithms
The list of rectangles are pre-sorted into order of decreasing height. Then the packing is done on a series of levels, that the bottom of each rectangle rests on. The first level is the bottom of the bin and subsequent levels are defined by the height of the tallest rectangle on the previous level.
Split algorithms
The level oriented algorithms split the bin horizontally into blocks of a set width. Split algorithms split the open ended bin vertically into smaller open ended bins depending on the widths of the rectangles. The rectangles are first sorted by width.
Shelf algorithms
These algorithms are modifications of the level algorithms, that avoid pre-sorting the list of rectangles. Rather than being determined by the tallest rectangle, the levels are fixed height shelves. The shelf heights are set by a parameter r. ( 0 < r < 1 )
Hybrid algorithms
These use the characteristics of two or more of the types of algorithms described above. They may or may not involve pre-sorting.
The Slave Algorithm
A slave algorithm is the approach that is used to decide which shelf a rectangle should be put on once all appropriate shelves have been determined.
For the level-by-level algorithms that I have chosen to model, each level, or shelf, in the bin has exactly the same width, C. (the width of the bin itself) This means that, for each rectangle, once the algorithm has calculated the levels it may be placed on, the decision of which of these levels to use is exactly a one-dimensional bin packing problem. That is, the number of levels being used, corresponds to the number of one-dimensional bins, of capacity C, that are required. This one-dimensional problem is solved by the slave algorithm. There are many one-dimensional algorithms that could be used as the slave algorithm, but I have chosen to concentrate on just the Next-fit (NF) and First-fit (FF) algorithms. All slave algorithms have their advantages and disadvantages, and the idea is to use the one that most suits the job in hand.
Next-fit v's First-fit
For the next-fit algorithm, each rectangle is put onto the highest level on which it will fit, i.e. the current level of the required specifications. For the first-fit algorithm, each rectangle is put onto the lowest (first) level that it will fit on.
First-fit is often the most economical choice since it allows you to place the rectangles on all the levels lower down the bin, whereas next-fit only lets you use the current (highest) levels, and no backtracking is allowed. First-fit is a suitable algorithm to use so long as all the rectangles may be arranged in the bin before anything happens to it, e.g. before the jobs are executed, or the strip starts to be cut up. Then it is fine to place the rectangles anywhere on the bin.
The next-fit algorithm would be needed if the job was continuing as the rectangles are placed on the bin. For example, if the height of the bin corresponded to time, and the time was continuously ticking by, you would not be able to go back in time and schedule any jobs for earlier points on the bin since that time has already passed! Another example would be if the bin was a strip of material, going along a conveyor belt. The rectangles get put into position on the material as it precedes, and at the end of the conveyor they get cut out. In these circumstances the levels lower down the bin (closer to the cutters), are continuously getting cut up so no more rectangles could be put on these levels as they would have missed the cutting process.
On-line v's Off-line
When describing the different types of bin packing algorithms, I have made a particular point of indicating whether or not the rectangles required sorting before being placed into the bin. This is an important factor to take into consideration when deciding on an appropriate algorithm for a bin packing problem.
Consider the situation where the list of rectangles arrives one at a time. When each rectangle arrives it must immediately be assigned its place in the bin. Only once this has happened, does the identity of the next rectangle become known. This type of environment is called on-line. Hence, on-line algorithms must assume no prior knowledge of the rectangles in the list, so pre-sorting the list of rectangles is not an option.
In an off-line environment it is possible to view the whole list of rectangles first and so sort them into any order before they are placed on the bin. Off-line algorithms assume prior knowledge of the whole problem before any packing has to be done.
An on-line algorithm would be used in a situation where the jobs had to be done in order. For example, the items may be subject to different priorities or deadlines. An off-line algorithm would be used when the order did not matter. For example, if pieces of material were being cut out to make a jacket, it would not matter if a sleeve was cut out before the collar, just as long as all the required pieces were produced in the end. Another factor to take into consideration when deciding whether to use an on-line or off-line algorithm is the amount of memory space it takes up. An off-line algorithm may give better results, but it also requires more programming to sort the rectangles first and so takes up more of the computers memory.
Guillotine Cuts
Level algorithms and shelf algorithms are both level-by-level packing approaches. Consequently, they are particularly of use in relation to guillotine cuts. (Level-by-level packings involve every rectangle being completely inside or completely outside of each level. This means that every vertical line through a level, intersects at most one rectangle) Guillotine cuts are cuts from one edge, across to the other edge of a rectangular section of bin, either parallel to its height or its width. I.e. they cut the area of rectangle into into two smaller rectangles, since the cuts must go all the way from one edge to the other. Level-by-level packings allow for 3-stage guillotine cuts. These involve first some horizontal guillotine cuts, then some vertical guillotine cuts and lastly, some more horizontal guillotine cuts to trim the rectangles to size.
The most common need for the ability to perform the 3-stage guillotine cuts is for its use in stock-cutting. In a factory situation, the cutting machines are generally set up either perpendicular or parallel to the strip of material (glass, sheet metal, etc) and must cut from one edge to the other.