O problema de corte não-guilhotinado multiperíodo com sobras aproveitáveis (2017)
- Authors:
- Autor USP: ROMãO, OBERLAN CHRISTO - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Subjects: TEORIA DE SISTEMAS E CONTROLE; CONTROLE ÓTIMO; PROGRAMAÇÃO MATEMÁTICA; PROGRAMAÇÃO DINÂMICA
- Keywords: Approximate dynamic programming; Horizonte rolante; Multi-period cutting problems; Optimization; Otimização; Problemas de corte multiperíodo; Programação dinâmica aproximada; Relax-and-fix; Relax-and-fix; Rolling horizon; Sobras aproveitáveis; Usable leftover
- Agências de fomento:
- Language: Português
- Abstract: 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çãoDinâ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
- Imprenta:
- Data da defesa: 18.10.2017
-
ABNT
ROMÃO, Oberlan Christo. O problema de corte não-guilhotinado multiperíodo com sobras aproveitáveis. 2017. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2017. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-01022018-180800/. Acesso em: 16 abr. 2024. -
APA
Romão, O. C. (2017). O problema de corte não-guilhotinado multiperíodo com sobras aproveitáveis (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-01022018-180800/ -
NLM
Romão OC. O problema de corte não-guilhotinado multiperíodo com sobras aproveitáveis [Internet]. 2017 ;[citado 2024 abr. 16 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-01022018-180800/ -
Vancouver
Romão OC. O problema de corte não-guilhotinado multiperíodo com sobras aproveitáveis [Internet]. 2017 ;[citado 2024 abr. 16 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-01022018-180800/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
