Problemas de corte com sobras aproveitáveis e eliminação de simetrias / Cutting stock problems with usable leftover and symmetry breaking
AUTOR(ES)
Ricardo Luiz de Andrade Abrantes
FONTE
IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia
DATA DE PUBLICAÇÃO
20/09/2012
RESUMO
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
ASSUNTO(S)
cutting problems eliminação de simetrias optimization otimização packing problems problemas de corte de estoque problemas de empacotamento sobras aproveitáveis symmetry breaking constraints usable leftover
Documentos Relacionados
- Algumas extensões do problema de corte de estoque com sobras de material aproveitáveis
- Geração de colunas para problemas de corte em duas fases
- Problema de corte de estoque unidimensional com sobras aproveitáveis: solução via metaheurística GRASP
- Inferência fuzzy para o problema de corte de estoque com sobras aproveitáveis de material
- Algoritmos para problemas de corte e empacotamento