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.

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.