Novel Hybrid Genetic Approach for Two Dimensional Guillotinable Cutting Problems

Novel Hybrid Genetic Approach for Two Dimensional Guillotinable Cutting Problems

Hamadi Hasni (ENSI School, University of Manouba, Manouba, Tunisia) and Hamza Gharsellaoui (INSAT Institute, University of Carthage, Tunis, Tunisia)
DOI: 10.4018/japuc.2012070101

Abstract

The paper deals with the purpose of one hybrid approach for solving the constrained two-dimensional cutting (2DC) problem. The authors study this hybrid approach that combines the genetic algorithm and the Tabu search method. For this problem, they assume a packing of a whole number of rectangular pieces to cut, and that all cuts are of guillotine type in one sheet of a fixed width and an infinite height. Finally, the authors undertake an extensive experimental study with a large number of problem instances extracted from the literature by the Burke Benchmarks and the Beasley Benchmarks in order to support and to prove their approach and to evaluate the performance.
Article Preview

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.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2019): Forthcoming, Available for Pre-Order
Volume 10: 4 Issues (2018)
Volume 9: 4 Issues (2017)
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing