• 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
 
 
Dissertação de Mestrado
DOI
https://doi.org/10.11606/D.18.2021.tde-19072021-182420
Documento
Autor
Nome completo
Edson Antonio Gonçalves de Souza
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Carlos, 2021
Orientador
Banca examinadora
Nagano, Marcelo Seido (Presidente)
Ribeiro, José Francisco Ferreira
Tavares Neto, Roberto Fernandes
Título em inglês
Bounded Dynamic Programming Approach to minimize Makespan for the Blocking Flow Shop problem with Sequence Dependent Setup Times Constraints
Palavras-chave em inglês
B&B
blocking flow shop
Bounded Dynamic Programming
makespan
MILP
setup times
Resumo em inglês
Throughout the decades, the flow shop scheduling problem has appeared in a variety of manufacturing scenarios and, as a consequence of that fact, several branches of it have taken place and are frequently studied by researchers so as to develop efficient methods to solve these problems that stem from the classic version. A problem that is frequently found on the shop floor is the blocking flow shop with sequence dependent setup times (BFSP-SDST) with makespan optimization, which can be found on electronics, metallurgy, chemical and food industries and it comes to show the importance of improving systems that can be modelled via this problem. However, when gathering information on stateof- art references, one will notice that little has been made regarding BFSP-SDST and, consequently, only few methods have been applied with the intent of optimizing makespan. Furthermore, research has shown that dynamic programming is a method that has not been given much attention with regard to the flow shop environment and therefore, its contribution has become, thus far, limited. Hence, this research aims at applying Bounded Dynamic Programming (BDP), which is a DP-based method, to solve the BFSP-SDST so as to enlarge the number of methods that are related to such problem. The BDP is employed in two sets of problems and for the first set, it is compared to a MILP and B&B methods, while the comparison occurs only between the BDP and MILP for the second set. The results have shown that BDP outperforms the MILP in both scenarios and the B&B in terms of CPU times and success rate. In addition, a trade-off analysis is provided in order to determine which method is a better choice for the scheduler in terms of solution quality and CPU times and, once again, BDP proves to be better for the job and machine sets considered. Sequentially, some suggestions are furnished to improve the method and develop further research considering this approach.
Título em português
Análise de Bounded Dynamic Programming com minimização do Makespan para o problema de Flow Shop com bloqueio e restrições de tempos de setup dependentes da sequência
Palavras-chave em português
Bounded Dynamic Programming
flow shop com bloqueio
makespan
B&B
MILP
tempos de setup
Resumo em português
Ao longo das décadas, o problema de sequenciamento em ambiente flow shop tem aparecido em uma variedade de cenários de manufatura e, como consequência, diversas ramificações se estabeleceram, sendo frequentemente estudadas por pesquisadores com o intuito de desenvolver métodos eficientes para resolver esses problemas originados da versão clássica do flow shop. Um problema comumente encontrado no chão de fábrica é o flow shop com bloqueio e tempos de setup dependentes da sequência (BFSP-SDST) com minimização do makespan, que pode ser encontrado em indústrias de eletrônicos, metalúrgicas, química e de alimentos e portanto, demonstra a importância de aperfeiçoar sistemas que possam ser modelados através do mesmo. Todavia, ao organizar informações de referências que são estado-da-arte, pode-se notar poucas referências acerca do BFSP-SDST e, por consequência, apenas poucos métodos foram aplicados com o intuito de minimizar o makespan para tal problema. Além do mais, as pesquisas mostraram que a programação dinâmica não tem recebido devida atenção quando se trata do ambiente flow shop e portanto, sua contribuição se tornou limitada, até o momento. Logo, essa pesquisa tem como objetivo aplicar Bounded Dynamic Programming (BDP), que é um método baseado em programação dinâmica, como solução para o BFSP-SDST para aumentar o número de métodos de solução para tal problema. O BDP é empregado em dois conjuntos de instâncias e, para o primeiro conjunto, o mesmo é comparado com os métodos MILP e B&B, enquanto a comparação ocorre apenas entre BDP e MILP para o segundo conjunto. Os resultados mostraram que BDP supera o MILP em ambos os cenários e o B&B em termos de eficiência computacional e qualidade de solução através da taxa de acerto do algoritmo. Adicionalmente, uma análise de trade-off é fornecida para se determinar qual método representa uma melhor escolha para o programador em termos de qualidade da solução e esforço computacional e, mais uma vez, BDP se mostra uma escolha melhor para os conjuntos de tarefas e máquinas considerados. Sequencialmente, algumas sugestões são fornecidas para refinar o método e e desenvolver futuras pesquisas considerando essa abordagem.
 
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
2021-08-09
 
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
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2024. Todos os direitos reservados.