Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems. (English) Zbl 1034.90500

Lodi, Andrea; Martello, Silvano; Vigo, Daniele

INFORMS J. Comput. 11, No. 4, 345-357 (1999).

Summary: Two-dimensional bin packing problems consist of allocating, without overlapping, a given set of small rectangles (items) to a minimum number of large identical rectangles (bins), with the edges of the items parallel to those of the bins. According to the specific application, the items may either have a fixed orientation or they can be rotated by \(90^\circ\). In addition, it may or not be imposed that the items are obtained through a sequence of edge-to-edge cuts parallel to the edges of the bin. In this article, we consider the class of problems arising from all combinations of the above requirements. We introduce a new heuristic algorithm for each problem in the class, and a unified tabu search approach that is adapted to a specific problem by simply changing the heuristic used to explore the neighborhood. The average performance of the single heuristics and of the tabu search are evaluated through extensive computational experiments.

MSC:

90Bxx	Operations research and management science
90C59	Approximation methods and heuristics in mathematical programming
90C27	Combinatorial optimization