Hybrid Genetic Metaheuristic for Two-Dimensional Constrained 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). 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.