Doctoral Thesis
DOI
10.11606/T.45.2012.tde-16122012-183550
Document
Author
Full name
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2012
Supervisor
Committee
Birgin, Ernesto Julian Goldberg (President)
Morabito Neto, Reinaldo
Poldi, Kelly Cristina
Wakabayashi, Yoshiko
Yanasse, Horacio Hideki
Title in Portuguese
Problemas de corte com sobras aproveitáveis e eliminação de simetrias
Keywords in Portuguese
eliminação de simetrias
otimização
problemas de corte de estoque
problemas de empacotamento
sobras aproveitáveis
Abstract in Portuguese
Title in English
Cutting stock problems with usable leftover and symmetry breaking
Keywords in English
cutting problems
optimization
packing problems
symmetry breaking constraints
usable leftover
Abstract in English
In this work we study two variations of the packing problem where identical rectangular items must be packed into a polyhedron. One of the variations consists in finding the largest amount of rectangular items that can fit in a polyhedron. The other one consists in finding a minimal area polyhedron of a certain type that packs a set of rectangular identical items. We present some symmetry-breaking constraints that reduce the computational effort in solving those problems through a branch-&-bound method. We also studied the cutting stock problem where there are some items to be cut from a set of rectangular objects and we need to satisfy the demand of items to be cut minimizing the cost of the used objects and, among the different ways of doing this, we want that which maximize the usable leftovers. Loosely speaking,usable leftovers can be understood as rectangular regions in an object that has the width and the height greater than or equal to the ones of a reference item. These leftovers can be seen as leftovers from a cutting process that will become items in a new cutting process. We present bilevel programming models to two variations of this problem with usable leftovers: the two-stage cutting stock problem of rectangular items and the non-guillotine cutting stock problem of rectangular items. In order to solve the proposed models we present also MIP reformulations of these bilevel programming problem models. We also developed some symmetry breaking constraints in order to accelerate the solving process of those models. The developed models were computationally programmed and we were able to solve small instances of the proposed problems