On a Genetic-Tabu Search Based Algorithm for Two-Dimensional Guillotine Cutting Problems

On a Genetic-Tabu Search Based Algorithm for Two-Dimensional Guillotine Cutting Problems

Hamza Gharsellaoui (INSAT Institute, University of Carthago, Tunisia) and Hamadi Hasni (ENSI School, University of Manouba, Tunisia)
DOI: 10.4018/japuc.2012040103
OnDemand PDF Download:
No Current Special Offers


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, they undertake an extensive experimental study with a large number of problem instances extracted from the literature by the Hopper’s benchmarks in order to support and to prove their approach and to evaluate the performance.
Article Preview

A Brief State Of The Art

Because of its importance and despite its NP-hardness, the Two Dimensional Cutting (TDC) problem has been widely studied in the literature. Indeed, there are three key components of the problem under consideration; bin packing, guillotine cuts and regular shapes (rectangular form). To our knowledge there are no papers that tackle these three together with a hybrid genetic algorithm. In addition, regular shape packing literature is almost exclusively strip packing; one infinite length stock sheet, and a finite fixed set of rotation angles. In this paper all pieces are regular with a rectangular form; instead the key challenge arises in modeling efficiently continuous rotation of the pieces, which is not commonly dealt with in the literature.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2019)
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