DOI
10.11606/T.45.2018.tde-01022018-180800
Documento
Autor
Nome completo
Oberlan Christo Romão
E-mail
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2017
Birgin, Ernesto Julian Goldberg (Presidente)
Morabito Neto, Reinaldo
Munari Junior, Pedro Augusto
Poldi, Kelly Cristina
Yanasse, Horacio Hideki
Título em português
O problema de corte não-guilhotinado multiperíodo com sobras aproveitáveis
Palavras-chave em português
Horizonte rolante
Otimização
Problemas de corte multiperíodo
Relax-and-fix
Sobras aproveitáveis
Resumo em português
Título em inglês
Multi-period non-guillotine cutting problem with usable leftover
Palavras-chave em inglês
Approximate dynamic programming
Multi-period cutting problems
Optimization
Relax-and-fix
Rolling horizon
Usable leftover
Resumo em inglês
In this research, we study the multi-period two-dimensional cutting problem with usable leftover, which consists of cutting objects to produce a set of items. We assume a finite planning horizon with a finite amount of periods between the initial and final times. First we consider a deterministic version in which we know, a priori, the set of ordered items and the cost of the objects at each period. Some of the leftovers generated during the cutting process of the ordered items in a period may be used as objects in the future. The leftovers that can be used in the future are called usable leftovers. In general, a leftover is considered usable if it has dimensions equal to or greater than that of some item from a predefined list for the period. The goal is to minimize the total cost of the objects used to cut the set of ordered items of the entire considered horizon. If there are solutions with the same cost, we wish to find one that, at the end of the considered time horizon, maximizes the value of the remaining usable leftovers. We present a mathematical model of the problem using a bilevel formulation, which is transformed into a mixed integer linear programming model, due to the characteristics of the problem. Considering the difficulty in solving the developed model, we propose a heuristic approach based on approximate dynamic programming (ADP) to deal with the proposed problem. Other options based on the rolling horizon and relax-and-fix strategies are also considered. We also consider the scenario where we do not know in advance the set of ordered items and the cost of the objects, but we have information about the probability distributions of both. In this case, we present an approach based on approximate dynamic programming to estimate the best strategy to be followed at each period. We compared the results obtained by the ADP with the results found by a greedy method. In suitable scenarios, the results show that the ADP achieves superior solutions to the greedy method.

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.
TeseOberlanRomao.pdf (16.83 Mbytes)
Data de Publicação
2018-02-19

AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI