A squeaky wheel optimisation methodology for two-dimensional strip packing

Abstract

The two-dimensional strip packing problem occurs in industries such as metal, wood, glass, paper, and textiles. The problem involves cutting shapes from a larger stock sheet or roll of material, while minimising waste. This is a well studied problem for which many heuristic methodologies are available in the literature, ranging from the basic ‘one-pass’ best-fit heuristic, to the state of the art Reactive GRASP and SVC(SubKP) iterative procedures. The contribution of this paper is to present a much simpler but equally competitive iterative packing methodology based on squeaky wheel optimisation. After each complete packing (iteration), a penalty is applied to pieces that directly decreased the solution quality. These penalties inform the packing in the next iteration, so that the offending pieces are packed earlier. This methodology is deterministic and very easy to implement, and can obtain some best results on benchmark instances from the literature.

Introduction

Optimisation problems involving cutting stock arise in many industries such as metal, wood, glass, paper, and textiles. These problems generally involve cutting stock sheets of material into smaller shapes, and a typical objective is to minimise the waste. These problems form part of a wider set of cutting and packing problems (see the typologies presented in [1], [2]). This paper addresses the two-dimensional orthogonal strip packing problem, where a set of rectangular shapes must be arranged onto a larger rectangle of fixed width and infinite height, while minimising the height of the highest rectangle in the solution, corresponding to a ‘guillotine cut’ across the width of the sheet. The rectangles must not intersect each other, or exceed the edges of the large rectangle, and the resulting arrangement corresponds to a cutting pattern which will obtain the necessary set of shapes from the stock sheet.

The exact problem that we address in this paper can be defined, by reference to the typology of Wäscher et al. [2], as the two-dimensional orthogonal open dimension problem. We do not use piece rotations, and guillotine cuts are not required, so the problem can also be referred to as the ‘OF’ sub-type (oriented, free cutting) [3], [4].

‘Best-fit’ is a constructive heuristic for the two-dimensional orthogonal stock cutting problem. A detailed description of the algorithm is given in [5], [6], [7], but a brief summary is given here as some of the concepts are used in our squeaky wheel optimisation approach. Best-fit represents the stock sheet as a set of dynamic slots where pieces can be placed. At the start of the packing, there is only one slot extending across the width of the sheet. Given a list of pieces to pack, best-fit iteratively packs a piece into the lowest available slot, and the slot structure is updated after each iteration. The piece that is chosen for the slot is the piece with the largest width, from all of those which can fit. If the lowest available slot is too narrow for any piece, the slot is raised to the level of its lowest neighbour, and they are merged, producing a wider slot. The packing continues in this manner until there are no pieces left to pack.

Burke et al. [6] presented a simulated annealing enhancement to the best-fit heuristic (BF+SA). This was motivated by the observation that the choice of pieces to pack was increasingly limited towards the end of the packing. This often produced ‘towers’ protruding from the top of the solution, reducing the solution quality. This was initially addressed with a post-processing stage which turned these tall pieces on their side, but there was rarely a good place to put them at that late stage. BF+SA stops packing when m rectangles are left (a parameter which one must tune depending on the size of the instance), and then the rest of the pieces are iteratively packed using a simple bottom-left-fill heuristic, with a simulated annealing algorithm to optimise the piece order.

The current state of the art methodologies are the Reactive GRASP [8] and SVC(SubKP) [9]. The GRASP algorithm involves a constructive phase and a subsequent iterative improvement phase. The method is a complex algorithm with many parameters, which are chosen by hand, and obtains some of the best results in the literature. The SVC (SubKP) uses a constructive heuristic which fills the lowest slot by solving a one-dimensional knapsack problem with a pseudo-profit for each item. The packing is split into horizontal slices determined by the positions of the pieces, and the profits of the items are based on their size, the size of the slices containing them, and a random scaling variable. In each iteration the profits are updated meaning that the pieces will be packed differently in the next iteration. The algorithm is stochastic. In a given run, probabilities are randomly chosen for changing the order of the pieces in a slot, moving all the pieces to the left or right of the slot, and changing the scaling variable for the pseudo-profits. These probabilities are also modified during the run.

The contribution of this paper is to present a very simple, yet effective, deterministic packing methodology based on ‘squeaky wheel optimisation’ [10], [11]. Squeaky wheel optimisation is a metaheuristic search technique which attempts to identify the most difficult elements of a problem by iteratively constructing a solution, each time analysing the solution to assess which elements are causing problems. In the next iteration, those elements that have been judged to be most difficult are dealt with earlier in the solution construction. BF+SA, GRASP, and SVC (SubKP) are stochastic algorithms, and as such they may require multiple runs to obtain their best solution. In contrast, the squeaky wheel optimisation methodology is deterministic, and therefore requires only one run. While it was not our initial aim, the squeaky wheel optimisation approach is competitive (and sometimes better than) these much more complex algorithms.