Article ID: | iaor2000893 |
Country: | Netherlands |
Volume: | 112 |
Issue: | 1 |
Start Page Number: | 158 |
End Page Number: | 166 |
Publication Date: | Jan 1999 |
Journal: | European Journal of Operational Research |
Authors: | Martello Silvano, Vigo Daniele, Lodi Andrea |
Keywords: | heuristics |
Given a set of rectangular items which may not be rotated and an unlimited number of identical rectangular bins, we consider the problem of packing each item into a bin so that no two items overlap and the number of required bins is minimized. The problem is strongly NP-hard and finds practical applications in cutting and packing. We discuss a simple deterministic approximation algorithm which is used in the initialization of a tabu search approach. We then present a tabu search algorithm and analyze its average performance through extensive computational experiments.