• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Thèse de Doctorat
DOI
https://doi.org/10.11606/T.45.2018.tde-01022018-180800
Document
Auteur
Nom complet
Oberlan Christo Romão
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2017
Directeur
Jury
Birgin, Ernesto Julian Goldberg (Président)
Morabito Neto, Reinaldo
Munari Junior, Pedro Augusto
Poldi, Kelly Cristina
Yanasse, Horacio Hideki
 
Titre en portugais
O problema de corte não-guilhotinado multiperíodo com sobras aproveitáveis
Mots-clés en portugais
Horizonte rolante
Otimização
Problemas de corte multiperíodo
Programação dinâmica aproximada
Relax-and-fix
Sobras aproveitáveis
Resumé en portugais
Neste trabalho, estudamos o problema de corte bidimensional multiperíodo com sobras aproveitáveis, que consiste em cortar objetos grandes visando a produção de um conjunto de itens menores. Supomos um horizonte de planejamento finito com uma quantidade finita de períodos entre os tempos inicial e final. Primeiramente consideramos uma versão determinística em que conhecemos, à priori, os itens solicitados em uma ordem de trabalho e o custo dos objetos a cada período. Algumas das sobras geradas durante o processo de corte dos itens solicitados em um período podem ser utilizadas como objetos no futuro. As sobras que podem ser usadas no futuro são denominadas sobras aproveitáveis. De forma geral, uma sobra é considerada aproveitável se possui dimensões iguais ou superiores as de algum item de uma lista pré-definida para o período. O objetivo é minimizar o custo total dos objetos utilizados para satisfazer a ordem de trabalho dos itens solicitados de todo o horizonte considerado. Havendo soluções com o mesmo custo, desejamos encontrar aquela que, no fim do horizonte de tempo considerado, maximize o valor das sobras aproveitáveis remanescentes. Apresentamos uma modelagem matemática do problema usando uma formulação em dois níveis, que é transformada em um modelo de programação linear inteira mista, devido às características do problema. Considerando a dificuldade em resolver o modelo desenvolvido, apresentamos uma proposta de uma abordagem heurística baseada em Programação Dinâmica Aproximada (PDA) para lidar com o problema proposto. Outras opções baseadas em estratégias do tipo horizonte rolante e relax-and-fix também são consideradas. Consideramos também o cenário onde não conhecemos de antemão os itens da ordem de trabalho e o custo dos objetos, mas temos informações das distribuições de probabilidade de ambos. Nesse caso, apresentamos uma abordagem baseada em programação dinâmica aproximada para estimar a melhor estratégia a ser seguida em cada período. Comparamos os resultados obtidos pela PDA com os resultados encontrados por um método guloso. Em cenários adequados, os resultados mostram que a PDA consegue soluções superiores ao método guloso.
 
Titre en anglais
Multi-period non-guillotine cutting problem with usable leftover
Mots-clés en anglais
Approximate dynamic programming
Multi-period cutting problems
Optimization
Relax-and-fix
Rolling horizon
Usable leftover
Resumé en anglais
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.
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
TeseOberlanRomao.pdf (16.83 Mbytes)
Date de Publication
2018-02-19
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs.
CeTI-SC/STI
© 2001-2024. Bibliothèque Numérique de Thèses et Mémoires de l'USP.