An exact strip packing algorithm based on canonical forms

Yohei Arahori

doi:10.1016/j.cor.2012.03.003

2012-12-01

PRE

Yohei Arahori *

Takashi Imamichi

Hiroshi Nagamochi

DOI：10.1016/j.cor.2012.03.003

原文链接

原文求助

摘要

En 中文

Given a set of rectangles and a rectangular container with a fixed width, called a strip, the two-dimensional strip packing problem (2SP) requires all the given rectangles to be placed orthogonally without overlap within the strip so as to minimize the height of the strip. 2SP and its variants have many applications in steel and textile industries, including an indirect application in scheduling problems. However, 2SP is known to be NP-hard. In this paper, we propose an exact algorithm to 2SP with and without rotations of 90 degrees. The algorithm is designed by a branch-and-bound method that solves subproblems represented by g-staircase placements to 2SP with fixed height. We derive a new lower bound on the optimal value to 2SP by relaxing it to the problem of partitioning a set of integers into two subsets with the same total sum (PARTITION). We also design a new exact algorithm to the one-dimensional contiguous bin packing problem with fixed height (1CBPFH) using a g-staircase-placement-based branch-and-bound method. To reduce the search space, we introduce several new ideas to the branch-and-bound method. For example, we define canonical forms of feasible solutions to 2SP and 1CBPFH to limit the search space by looking for only a canonical solution. Our computational experiments on benchmark instances indicate that the proposed algorithm is competitive with the other algorithms. Our algorithm succeeded to find the optimal values for most of the instances in a practical time. Especially, it determined that the optimal values of instances gcut02 and cgcut02 (without rotations) are 1187 and 64, respectively, which have not been obtained by any of the other existing algorithms. (C) 2012 Published by Elsevier Ltd.

Keyword:

Two-dimensional strip packing problem

One-dimensional contiguous bin packing problem

Branch-and-bound

Canonical form