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

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.