Um estudo da natureza biobjetiva do problema de sequenciamento just-in-time flow shop

Abstract

Nessa tese é tratado o Problema de Sequenciamento em Just-In-Time Flow shop (JIT-FSP) com as medidas adiantamento total e atraso total. A natureza biobjetiva dessas medidas é deixada em segundo plano pela literatura ao tratar o problema de forma monoobjetiva, mostrando uma lacuna ainda inexplorada, sendo contribuir para fechar essa lacuna o principal objetivo dessa tese. Conceitos básicos sobre otimização multiobjetivo são apresentados, assim como, os métodos de solução exatos: epsilon-restrito, epsilon-restrito aumentando, caixa balanceada e branch-and-bound. Ferramentas matemáticas são propostas para analisar a solução da metodologia monoobjetivo dentro de uma perspectiva biobjetivo. Os métodos exatos são pouco explorados para resolver o JIT-FSP devido ao porte de problemas reais. Para contornar a dificuldade com o porte dos problemas reais, aplica-se o método de decomposição de Benders e são propostas 5 variações do método. Resultados do estudo computacional, 1100 execuções com tempos máximos de 3600 segundos em cada execução, mostraram que a metodologia utilizada pela literatura para resolver o JIT-FSP pode obter soluções indesejáveis para alguns cenários industriais. Além disso, evidencia-se as vantagens de utilizar a abordagem biobjetivo, chamando a atenção para a necessidade de utilizar métodos capazes de encontrar toda a fronteira de Pareto principalmente com o aumento do porte das instâncias. As variações do método de Benders mostraram um aumento no desempenho em relação ao método clássico, principalmente quando é utilizado uma busca em árvore única.

This thesis deals with the Just-In-Time Flow Shop Scheduling Problem (JIT-FSP) with the measures total earliness and total tardiness. The bi-objective nature of these measures is left in the background by the literature when treating the problem in a mono-objective way, showing an gap, and contributing to closing this gap is the main objective of this thesis. Basic concepts of multi-objective optimization are presented, as well as exact solution methods: epsilon-constrained, augmented epsilon-constrained, balanced box and branch-and-bound. Mathematical tools are proposed to analyze the solution of the mono-objective methodology within a bi-objective perspective. Exact methods have been little explored to solve the JIT-FSP due to the size of real problems. To overcome the difficulty with the size of real problems, the Benders decomposition method is applied and 5 variations of the method are proposed. The results of the computational study, 1100 runs with a maximum time of 3600 seconds for each run, showed that the methodology used in the literature to solve the FSP-JIT can obtain undesirable solutions for some industrial scenarios. It also shows the advantages of using the bi-objective approach, drawing attention to the need to use methods capable of finding the full Pareto frontier, especially as the size of the instances increases. Variations of the Benders method showed an increase in performance compared to the classic method, especially when a single tree search is used.