DOI
https://doi.org/10.11606/T.45.2012.tde-16122012-183550
Documento
Autor
Nome completo
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2012
Birgin, Ernesto Julian Goldberg (Presidente)
Morabito Neto, Reinaldo
Poldi, Kelly Cristina
Wakabayashi, Yoshiko
Yanasse, Horacio Hideki

Título em português
Problemas de corte com sobras aproveitáveis e eliminação de simetrias
Palavras-chave em português
eliminação de simetrias
otimização
problemas de corte de estoque
problemas de empacotamento
sobras aproveitáveis
Resumo em português

Título em inglês
Cutting stock problems with usable leftover and symmetry breaking
Palavras-chave em inglês
cutting problems
optimization
packing problems
symmetry breaking constraints
usable leftover
Resumo em inglês
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

AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2013-01-02

AVISO: O material descrito abaixo refere-se a trabalhos decorrentes desta tese ou dissertação. O conteúdo desses trabalhos é de inteira responsabilidade do autor da tese ou dissertação.
• ANDRADE, R., and BIRGIN, E. G.. Symmetry-breaking constraints for packing identical rectangles within polyhedra [doi:10.1007/s11590-011-0425-9]. Optimization Letters [online], 2013, vol. 7, n. 2, p. 375-405.

Todos os direitos da tese/dissertação são de seus autores.
CeTI-SC/STI
© 2001-2024. Biblioteca Digital de Teses e Dissertações da USP.