Novel Hybrid Genetic Approach for Two Dimensional Guillotinable Cutting Problems

Introduction

The packing problems have been widely studied during the last three decades, as they are often faced in industry. The rectangular pieces packing problem, cutting also from rectangular board, is one particular case of this set of problems. The aim is often to achieve the minimum trim loss (Teng & Liu, 1999).

We had done some studies on packing problems in Gao, Teng, and Yu (1994). In this paper we propose a combination tabu search / genetic algorithms approach to construction of optimization algorithms for problems such as packing problems whose involve constructing an arrangement of items that minimizes the total space required by the arrangement. This is mainly due to the constraints imposed by the industrial applications, e.g., textile, wood, steel and metal industry. A recent survey on packing problems is given in Dowsland and Dowsland (1992). In this paper, we specifically consider the two-dimensional (2D) rectangular strip packing problem based on a new hybrid approach, named hybrid genetic algorithm. The input is a list of n rectangles with their dimensions (length and width). The goal is to pack the rectangles without overlap into a single rectangle of width W and minimum height H. We further restrict ourselves to the oriented, orthogonal variation, where rectangles must be placed parallel to the horizontal and vertical axes, and the rectangles can be rotated. Further, for our test cases, all dimensions are integers. Like most packing problems, 2D rectangular strip packing (even with these restrictions) is NP-hard. Finally, our algorithm naturally solves a more general problem: given a set of rectangles and a target rectangle, find a packing of a subset of those rectangles which gives an optimal packing of the target. Numerical examples also showed the superiority of the proposed algorithm compared with two classical methods in the literature (pure genetic algorithm, Burke results and Beasley results) (Beasley, 1985).

This paper is organized as follows. First, we provide the problem description and the literature review. Then, we present the resolution methods which use the bottom left algorithm and the guillotine constraint. Next, we show how our hybrid algorithm can be adapted for solving the general 2DC problem. Afterwards, we undertake a comparative study of our proposed algorithm and evaluate its performance for the 2DC problem using benchmark problems from the literature. Finally, we summarize the contributions of this paper and explain its possible extensions.