Article ID: | iaor20031911 |
Country: | Netherlands |
Volume: | 141 |
Issue: | 2 |
Start Page Number: | 341 |
End Page Number: | 358 |
Publication Date: | Sep 2002 |
Journal: | European Journal of Operational Research |
Authors: | Young Gilbert H., Wong C.K., Wu Yu-Liang, Huang Wenqi, Lau Siu-chung |
Keywords: | heuristics |
In this paper, we introduce an effective deterministic heuristic, Less Flexibility First, for solving the classical NP-complete rectangle packing problem. Many effective heuristics implemented for this problem are CPU-intensive and non-deterministic in nature. Others, including the polynomial approximation methodology are too laborious for practical problem sizes. The technique we propose is inspired and developed by enhancing some rule-of-thumb guidelines resulting from the generation-long work experience of human professionals in ancient days. Although the Less Flexibility First heuristic is a deterministic algorithm, the results are very encouraging. This algorithm can consistently produce packing densities of around 99% on most randomly generated large examples. As compared with the recent results of a well known simulated annealing based Rectangle Packing (RP) algorithm, the results are much better both in less dead space (4% vs 6.7%) and much less CPU time (9.57 vs 331.78 seconds). Experimenting our heuristics on a public rectangle packing data set covering instances of 16–97 rectangles, the average unpack ratio is quite satisfactory (0.92% for bounding boxes limited to be optimum and 2.68% for the completed packing), while most cases spend only a few minutes in CPU time.