Hybrid Genetic Metaheuristic for Two-Dimensional Constrained Guillotinable Cutting Problems

Hybrid Genetic Metaheuristic for Two-Dimensional Constrained Guillotinable Cutting Problems

Hamza Gharsellaoui (National Institute of Applied Sciences and Technology (INSAT), Carthage University, Tunisia) and Hamadi Hasni (National School of Computer Science, ENSI, University of Manouba, Tunisia)
Copyright: © 2015 |Pages: 12
DOI: 10.4018/978-1-4666-5888-2.ch017
OnDemand PDF Download:
$30.00
List Price: $37.50

Chapter Preview

Top

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). In this book chapter we propose two approaches for the construction of algorithms for optimization 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 (Ntene & van Vuuren, 2009). In this book chapter, 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. This book chapter is organized as follows. In Section 2, we provide the backgroundwhere we describe a brief literature review, and some known concepts in the genetic algorithmstheory. In Section 3, we present the resolution methods which use the bottom left algorithm and the guillotine constraint. Section 4 presents some major problems in industry. In Section 5, we show howour two hybrid algorithms can be adapted for solving the general 2DC problem. In Section 6, we undertake a comparative study of our proposed algorithms and evaluate their performance for the2DC problem using benchmark problems from the literature. Finally, in Section 7, we summarize thecontributions of this book chapter and explain their possible extensions.

Key Terms in this Chapter

Hybrid Methods: Methods or approaches which are composed of the combination of two or three methods or algorithms.

Metaheuristic: A computational method that optimizes a problem by iteratively trying to improve a candidate solution among very large spaces of candidate solutions with regard to a given measure of quality.

Guillotine Cutting: A method where parts are cut horizontally or vertically from a sheet of glass, wood, etc. from edge to edge, which is referred to as a guillotine cutting.

Complete Chapter List

Search this Book:
Reset