This paper discusses a particular “packing” problem, namely the two dimensional strip packing problem, where a finite set of objects have to be located in a strip of fixed width and infinite height. The variant studied considers regular items, rectangular to be precise, that must be packed without overlap, not allowing rotations. The objective is to minimize the height of the resulting packing. In this regard, the authors present a local search algorithm based on the well-known tabu search metaheuristic. Two important components of the presented tabu search strategy are reinforced in attempting to include problem knowledge. The fitness function incorporates a measure related to the empty spaces, while the diversification relies on a set of historically “frozen” objects. The resulting reinforced tabu search approach is evaluated on a set of well-known hard benchmark instances and compared with state-of-the-art algorithms.
TopIntroduction
In packing problems, “small” items (also called “boxes”, “modules”, “objects”, or “pieces” e.g.) of various shapes (regular or not) and dimensions have to be packed (i.e., located) without overlap, with rotation and “guillotine” cuts (see Figure 1) allowed or not, in other “larger” items of regular forms or not1. These larger objects are usually called “containers” or “pallets” for the three-dimensional cases (3D, all dimensions fixed or infinite height) and “bins”, “plates”, or “(stock) sheets” (all dimensions fixed) or “strips” (only width fixed, infinite height) in 2D.
Figure 1. The guillotine constraint imposes a pattern where the items can be extracted by a sequence of “edge-to-edge” cuts, i.e., the cutting tool cannot change of direction within the same cutting step (dark zones map wasted areas).
Objectives are, for instance, to minimize the number of containers or to maximize the material used (hence to minimize the “trim loss”, i.e. the wasted area). A huge number of practical or industrial applications are concerned, such as truck loading, cardboard packing, facilities, fashion, plant, machine, newspaper, or web page layout design, VLSI macro-cell placement, glass, cloth, metal, paper, or wood industries, dynamic memory allocation, meta-computing, multi-processor or publicity scheduling for instance. This may explain why (commercial) software packages exist, sometimes for a long time. See (Dowsland & Dowsland, 1992; Lodi et al., 2002; Wäscher et al., 2007) just to mention a few surveys.
These problems are usually generalizations or restrictions of the well-known NP-hard (or NP-complete for decision variants) quadratic assignment, bin packing, knapsack, or quadratic set covering problems. Packing problems are thus optimization or satisfaction problems (sometimes with multiple objectives) that are NP-hard or NP-complete in the general case (Fowler et al., 1981; Garey & Johnson, 1979).
This paper is dedicated to the NP-hard 2D Strip Packing Problem (2D-SPP) which can be informally stated as follows: Given a finite set of objects, pack all of them without overlap in one strip of an infinite height and fixed width (also called “basis”) while minimizing the height of the resulting packing. The guillotine constraint is not considered here. Furthermore, all objects are regular (rectangular to be more precise) and cannot be rotated, i.e., they have a fixed orientation (Figure 1).
In this paper, we introduce CTS (for “Consistent Tabu Search”); a reinforced tabu search algorithm dedicated to the 2D-SPP. Compared with previous algorithms for the 2D-SPP, our CTS has several notable features. First, it handles a consistent neighborhood. Second, CTS evaluates packings, possibly partial, using problem knowledge. Finally, our algorithm includes a diversification mechanism relying on a set of historically “frozen” rectangles. Computational results suggest that CTS may be of great interest to solve the 2D-SPP.
In the two next sections, the 2D-SPP is formally stated and a brief description of various existing methods is given. Section 4 is devoted to the detailed presentation of our dedicated tabu search algorithm for the 2D-SPP. Experimental results are finally shown in Section 5 on a set of well-known benchmarks and compared with previous attempts including best performing state-of-the-art algorithms.
TopA “strip” is a 2D vertical space with fixed width W and infinite height, see Figure 2. The bottom-left (BL) corner of the strip stands for the (0, 0) point of a xy-plane where the x-axis (respectively y-axis) is the direction of the width (resp. height).
Figure 2. A strip with basic notations
The set of n ≥ 2 Rectangles to be positioned in the strip is R = {r1,…, rn} where the weight (resp. height) of each object r1≤i≤n is 
(resp. 
).