• 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
 
 
Disertación de Maestría
DOI
https://doi.org/10.11606/D.18.2021.tde-19072021-182420
Documento
Autor
Nombre completo
Edson Antonio Gonçalves de Souza
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Carlos, 2021
Director
Tribunal
Nagano, Marcelo Seido (Presidente)
Ribeiro, José Francisco Ferreira
Tavares Neto, Roberto Fernandes
Título en inglés
Bounded Dynamic Programming Approach to minimize Makespan for the Blocking Flow Shop problem with Sequence Dependent Setup Times Constraints
Palabras clave en inglés
B&B
blocking flow shop
Bounded Dynamic Programming
makespan
MILP
setup times
Resumen en 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 en 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
Palabras clave en portugués
Bounded Dynamic Programming
flow shop com bloqueio
makespan
B&B
MILP
tempos de setup
Resumen en 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.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2021-08-09
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2022. Todos los derechos reservados.