by Heidi Smith
You can view demonstrations of all the algorithms explained below by clicking on the one you are interested in
* Next-Fit Decreasing Height * First-Fit Decreasing Height * Next-Fit Shelf * First-Fit Shelf *
The performance of all the demonstrations is assessed, and displayed on the screen after all of the rectangles have been placed in the bin. This is shown as the percentage of wasted space (space not filled by a rectangle) in the bin. It is calculated by finding the ratio of the total area of all the rectangles in the list, and the area of bin used to pack them, (the area below the top of the highest rectangle).
Level Algorithms
Level algorithms are off-line algorithms. Their first step involves pre-sorting the list of rectangles into order of decreasing heights, i.e. the first rectangle to be packed will be the tallest and the last, the shortest. The packing is then made up of a series of levels. Each rectangle is successively packed into the bin by placing its bottom edge so as it rests on one of the levels. The first level is the bottom of the bin and each new level is defined by drawing a horizontal line across the bin through the top of the tallest (i.e. first) rectangle on the previous level.
Next-fit decreasing height (NFDH) algorithm
The NFDH algorithm is a level algorithm which uses the next-fit approach to pack the sorted list of rectangles. The rectangles are packed, left-justified on a level until the next rectangle will not fit. This rectangle is used to define a new level and the packing continues on this level. The earlier levels are not revisited.
To view a demonstration of the NFDH algorithm click here
First-fit decreasing height (FFDH) algorithm
This is another level algorithm which this time uses the first-fit approach. Each rectangle is placed on the first (i.e. lowest) level on which it will fit. If none of the current levels have room, a new level is started.
To view a demonstration of the FFDH algorithm click here
Shelf Algorithms
Shelf algorithms are variants of the level algorithms which avoid pre-sorting the list of rectangles. Therefore, unlike the level algorithms, shelf algorithms are on-line. To achieve this, the levels, rather than being determined by their tallest rectangle, come in fixed sized shelves, whose heights are determined by a parameter r, ( 0 < r < 1 ). Each arriving rectangle is classified according to its height. Then, the packing is constructed as a series of shelves, with rectangles of similar heights being packed onto the same shelves.
Shelf sizes come in the form rk. Each rectangle of height h, is packed onto a shelf having height rk, which satisfies the equation,
rk+1<= h <= rk
for some integer value k. The parameter r is pre-specified, and its aim is to limit the amount of wasted space allowed on each shelf. You are able to vary r in the demonstration applets to see how it affects the packing.
For small r, (r approximately equal to zero), the range of heights allowed on each shelf is large. This would often be required if there was only a small number of rectangles to pack, as you would not want every rectangle on its own individual shelf with the shelves not getting full up. It would also be useful if the list of rectangles had a wide selection of heights. In general, for small r, there would be a fewer amount of shelf heights to choose from, with each shelf containing rectangles with a larger range of heights.
For large r, (r approximately equal to one), each shelf would contain only rectangles that were very similar in height. This may be used if the list of rectangles was very long, because it would mean the likelihood of each different sized shelf becoming full up, would be increased. Another reason for having a large r, would be if the rectangles in the list, all had similar heights, so the algorithm would distinguish between the smaller differences in height. Generally, a large r would produce a wider selection of shelf heights, with the rectangles on each shelf having very similar heights.
Next-fit shelf (NFS) algorithm
Using the next-fit approach, this algorithm packs each rectangle as far to the left as possible on the highest shelf that has the required height. (The currently active shelf of this height) If there is no room on this shelf, or there is not yet a shelf of this height in the packing, a new such shelf is created and becomes the currently active shelf for that height. Shelves of the same height, below the active shelf are not revisited.
To view a demonstration of the NFS algorithm click here
First-fit shelf (FFS) algorithm
With the first-fit approach, the lowermost shelf of the correct height, onto which the rectangle will fit, is chosen. If there is no shelf of the required height, or none of the appropriate shelves have sufficient room, then a new shelf of that height is created.
To view a demonstration of the FFS algorithm click here