Nícolas Samuel Assis Um estudo da natureza biobjetiva do problema de sequenciamento just-in-time flow shop São José do Rio Preto 2024 Nícolas Samuel Assis Um estudo da natureza biobjetiva do problema de sequenciamento just-in-time flow shop Tese apresentada à Universidade Estadual Paulista (UNESP), Instituto de Biociências, Letras e Ciências Exatas, São José do Rio Preto, para obtenção do título de Doutor em Matemática. Orientadora: Profa. Dra. Socorro Rangel Coorientador: Prof. Dr. Hélio Yochihiro Fuchigami São José do Rio Preto 2024 A848e Assis, Nícolas Samuel Um estudo da natureza biobjetiva do problema de sequenciamento just-in-time flow shop / Nícolas Samuel Assis. -- São José do Rio Preto, 2025 121 p. : il., tabs. Tese (doutorado) - Universidade Estadual Paulista (UNESP), Instituto de Biociências Letras e Ciências Exatas, São José do Rio Preto Orientadora: Maria do Socorro Nogueira Rangel Coorientador: Hélio Yochihiro Fuchigami 1. Otimização multiobjetivo. 2. Planejamento da produção. 3. Adiantamento total e atraso total. 4. Métodos exatos. 5. Decomposição de Benders. I. Título. Sistema de geração automática de fichas catalográficas da Unesp. Dados fornecidos pelo autor(a). NÍCOLAS SAMUEL ASSIS UM ESTUDO DA NATUREZA BIOBJETIVA DO PROBLEMA DE SEQUENCIAMENTO JUST-IN-TIME FLOW SHOP Tese apresentada à Universidade Estadual Paulista (UNESP), Instituto de Biociências, Letras e Ciências Exatas, São José do Rio Preto, para obtenção do título de Doutor em Matemática. Área de Concentração: Matemática Data da defesa: 12 / 12 / 2024 Banca Examinadora: ______________________________________ Profa. Dra. Socorro Rangel UNESP Instituto de Biociências, Letras e Ciências Exatas - Campus de São José do Rio Preto ______________________________________ Prof. Dr. Reinaldo Morabito UFSCar São Carlos ______________________________________ Prof. Dr. Bruno de Athayde Prata UFC - Fortaleza ______________________________________ Profa. Dra. Daniela Renata Cantane UNESP - Botucatu ______________________________________ Prof. Dr. Thiago Alves de Queiroz UFCat - Catalão Agradecimentos Agradeço, primeiramente, aos meus pais e familiares por todo o carinho, apoio, com- preensão e orgulho que sempre demonstraram. Agradeço imensamente à minha esposa, Drielly, por todo o companheirismo, paciência e carinho nos momentos mais difíceis. Sou grato por toda a sua contribuição e ajuda no desenvolvimento da pesquisa, pelas discussões sempre tão valiosas e por compartilhar seus conhecimentos comigo. Agradeço profundamente à minha orientadora, Profa. Dra. Socorro Rangel, pelos grandes ensinamentos que vão além da universidade. Agradeço por ter aceitado e continuado a trabalhar comigo, mesmo em momentos difíceis para nós dois. Sou imensamente grato por sempre manter o alto nível de orientação. Agradeço muito ao meu coorientador, Prof. Dr. Hélio Yochihiro Fuchigami, por fazer parte dessa jornada. Sou grato pelos ensinamentos, pela parceria e por não perder o foco nos objetivos da pesquisa. Agradeço também por evidenciar todas as contribuições do trabalho, mesmo quando eu não conseguia enxergá-las. Agradeço ao Prof. Dr. Reinaldo Morabito Neto, ao Prof. Dr. Bruno de Athayde Prata, à Profa. Dra. Daniela Renata Cantane e ao Prof. Dr. Thiago Alves de Queiroz por aceitarem o convite para compor a banca de defesa e pelos comentários que contribuíram para a redação da tese e para as propostas de trabalhos futuros. Agradeço aos meus colegas de trabalho do SESI 298 e da Miró por me incentivarem a não desistir e a seguir firme nesta empreitada. Sou também grato aos meus amigos pelo companheirismo e pelos momentos de lazer, tão importantes para que eu concluísse esta jornada. O presente trabalho foi realizado com apoio da Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Código de Financiamento 001, à qual agradeço. RESUMO 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 apresen- tados, assim como, os métodos de solução exatos: ε-restrito, ε-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. Palavras-chave: otimização multiobjetivo; planejamento da produção; adiantamento total e atraso total; métodos exatos; decomposição de Benders. ABSTRACT 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: ε-constrained, augmented ε-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 atten- tion 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. Keywords: multiobjective optimization; production planning; total earliness and to- tal tardiness; exact methods; benders decomposition. Lista de figuras Figura 1 – Regiões de dominância no espaço critério . . . . . . . . . . . . . . . . . 18 Figura 2 – Fronteiras de Pareto de um problema biobjetivo . . . . . . . . . . . . . 19 Figura 3 – Legenda dos pontos no espaço critério do Problema 1 . . . . . . . . . . 20 Figura 4 – Espaço critério do Problema 1 . . . . . . . . . . . . . . . . . . . . . . . 20 Figura 5 – Região dominada pelo conjunto limitante inferior L . . . . . . . . . . . 27 Figura 6 – Conjunto limitante superior U . . . . . . . . . . . . . . . . . . . . . . . 27 Figura 7 – Dominância parcial de conjuntos limitantes (condição 3 para sondagem biobjetivo) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Figura 8 – Espaço critério associado à resolução do nó raiz do Problema 1 . . . . . 30 Figura 9 – Espaço critério associado à resolução do segundo nó da fila branch-and- bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Figura 10 – Espaço critério associado à resolução do oitavo nó da fila branch-and-bound 32 Figura 11 – Ramificação do espaço critério . . . . . . . . . . . . . . . . . . . . . . . 33 Figura 12 – Hipervolume e quantidade de pontos da AFP1 e AFP2 . . . . . . . . . 34 Figura 13 – Hipervolume e diversidade da AFP3 e AFP4 . . . . . . . . . . . . . . . 35 Figura 14 – Hipervolume da fronteira de Pareto . . . . . . . . . . . . . . . . . . . . 36 Figura 15 – Regiões de equilíbrio baseado em distância e µ como referência . . . . . 38 Figura 16 – Aumento percentual da soma ponderada em relação à solução monoobjetivo 38 Figura 17 – Sequenciamento de 5 tarefas em 3 máquinas . . . . . . . . . . . . . . . 41 Figura 18 – Sequenciamento e valor das medidas E, T , F e Cmax . . . . . . . . . . 42 Figura 19 – Sequenciamento com tempos ociosos . . . . . . . . . . . . . . . . . . . 49 Figura 20 – Diagrama da decomposição de Benders aplicado ao ε-restrito aumentado 61 Figura 21 – Diagrama da variação Bseq . . . . . . . . . . . . . . . . . . . . . . . . . 66 Figura 22 – AFP’s de configurações do BIOBAB da instância (20, 10)1 . . . . . . . 71 Figura 23 – AFP’s dos métodos do sistema BIOBAB e dos métodos GRBmultp e GRBmultl na instância (20, 10)1 . . . . . . . . . . . . . . . . . . . . . 75 Figura 24 – Métrica hipervolume da instância 1 para as classes (n, m) . . . . . . . . 76 Figura 25 – Métrica hipervolume das instâncias 2, 3 e 4 para as classes (20, m) . . . 79 Figura 26 – Métrica cardinalidade das instâncias 2, 3 e 4 para as classes (20, m) . . 80 Figura 27 – AFP’s dos métodos do sistema BIOBAB e dos métodos GRBmultp e GRBmultl na instância (20, 5)2 . . . . . . . . . . . . . . . . . . . . . . 81 Figura 28 – Métrica hipervolume das instâncias 2, 3 e 4 para as classes (50, m) e (100, m) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 Figura 29 – Métrica cardinalidade das instâncias 2, 3 e 4 para as classes (50, m) e (100, m) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 Figura 30 – AFP’s do sistema BIOBAB e dos métodos GRBmultp e GRBmultl na instância (50, 10)4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 Figura 31 – Gráficos de caixa do número de pontos na fronteira de Pareto por porte do problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 Figura 32 – Gráficos de colunas dos valores das ferramentas de localização por porte do problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 Figura 33 – Gráficos de colunas dos aumentos mínimo, médios e máximos do valor objetivo por porte do problema . . . . . . . . . . . . . . . . . . . . . . 90 Figura 34 – Gráficos de caixas do percentual de pontos não suportados na fronteira de Pareto por cenário . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 Figura 35 – Gráficos de caixas da cardinalidade das AFP’s dos métodos BIO- BAB, caixa balanceada, ε-restrito aumentado e GRBmult nas classes 0,2_0,6_5_3 e 0,4_1,2_5_3 . . . . . . . . . . . . . . . . . . . . . . . 94 Figura 36 – Gráficos de caixas do hiper ratio das AFP’s dos métodos BIOBAB, caixa balanceada, ε-restrito aumentado e GRBmult nas classes 0,2_0,6_5_3 e 0,4_1,2_5_3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 Figura 37 – Gráficos de Gantt de 4 soluções da instância 0,2_1,2_10_3_1 . . . . . 99 Figura 38 – Gráficos de caixas da cardinalidade das AFP’s para cada variação de ϵ 100 Figura 39 – Trade-off entre cardinalidade e hiper ratio para cada classe de instâncias102 Figura 40 – Gráficos de caixas do tempo de resolução para cada variação de ϵ . . . 103 Figura 41 – Gráficos de caixas para o tempo de execução por porte das instâncias . 104 Figura 42 – Gráfico de colunas da cardinalidade das AFP’s para instâncias com 10 tarefas e 7 máquinas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 Figura 43 – Gráficos de caixas do tempo de execução do problema mestre para cada porte de instância . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 Figura 44 – Gráficos de caixas do número de subproblemas resolvidos por porte de instância . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 Figura 45 – Diagrama de módulos do sistema BIOBAB . . . . . . . . . . . . . . . . 120 Lista de tabelas Tabela 1 – Características desejáveis nos métodos de escalarização . . . . . . . . . 21 Tabela 2 – Autores que resolveram o FSP com objetivo JIT . . . . . . . . . . . . . 45 Tabela 3 – Dimensão dos modelos (3.10)-(3.18) e (3.28)-(3.36) . . . . . . . . . . . 51 Tabela 4 – Autores que aplicam o método de decomposição de Benders nos proble- mas de sequenciamento . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Tabela 5 – Variações do método de decomposição de Benders . . . . . . . . . . . . 67 Tabela 6 – Objetivos dos estudos computacionais . . . . . . . . . . . . . . . . . . 69 Tabela 7 – Valores das métricas de cardinalidade e de hipervolume de configurações do BIOBAB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 Tabela 8 – Efeito do tipo de busca na árvore de busca do BIOBAB . . . . . . . . 72 Tabela 9 – Valores das métricas de cardinalidade e de hipervolume dos métodos do sistema BIOBAB e dos métodos GRBmultp e GRBmultl . . . . . . 74 Tabela 10 – Valores das métricas de cardinalidade e de hipervolume das instâncias 2, 3 e 4 para as classes (20, m) . . . . . . . . . . . . . . . . . . . . . . . 78 Tabela 11 – Valores das métricas de cardinalidade e de hipervolume das instâncias 2, 3 e 4 para as classes (50, m) e (100, m) . . . . . . . . . . . . . . . . . 82 Tabela 12 – Esforço computacional das abordagens multiobjetivo e monoobjetivo (média de 10 instâncias) . . . . . . . . . . . . . . . . . . . . . . . . . . 86 Tabela 13 – Valores das ferramentas de localização e aumento de custo do ponto monoobjetivo (média de 10 instâncias) . . . . . . . . . . . . . . . . . . 88 Tabela 14 – Número de pontos suportados e não suportados na fronteira de Pareto (média de cada classe de instâncias) . . . . . . . . . . . . . . . . . . . . 91 Tabela 15 – Valores do tempo de execução e das métricas de cardinalidade e de hiper- volume dos métodos BIOBAB, caixa balanceada, ε-restrito aumentado e GRBmult . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 Tabela 16 – Métricas de cardinalidade e de hiper ratio para variações de ϵ (média das classes) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 Lista de siglas FSP Flowshop Scheduling Problem JIT Just-In-Time JIT-FSP Just-In-Time Flowshop Scheduling Problem BIOBAB Bi-objctive Branch-and-Bound POM Problema de Otimização Multiobjetivo POIB Problema de Orimização Inteiro Biobjetivo LB Lower Bound AFP Aproximação de Fronteira de Pareto MIP Mixed Integer otimization Problem B&B Branch-and-Bound PMB Problema Mestre de Benders PMBB Problema Mestre de Benders Biobjetivo LBBD Logic-Based Benders Decomposition PMB Problema Mestre de Benders (dentro do algoritmo do método ε-restrito aumentado) SPB Subproblema de Benders SPε Subproblema do método ε-restrito aumentado Bcl Decomposição de Benders Clássico Bseq Decomposição de Benders com cortes pré-gerados BRL Decomposição de Benders com Relaxação Linear BRL seq Decomposição de Benders com cortes pré-gerados e Relaxação Linear BBCcl Branch-and-Benders-cut Clássico BBCseq Branch-and-Benders-cut com cortes pré-gerados GRBmult GUROBI Multiobjetivo GRBmono GUROBI Monoobjetivo Sumário 1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2 O PROBLEMA DE OTIMIZAÇÃO LINEAR INTEIRO MULTIOB- JETIVO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.1 Métodos de solução . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.1.1 Métodos de escalarização . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1.2 Branch-and-bound multiobjetivo . . . . . . . . . . . . . . . . . . . . . . . 25 2.2 Métricas de desempenho . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.3 Ferramentas matemáticas propostas para análise de pontos na fron- teira de Pareto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3 O PROBLEMA DE SEQUENCIAMENTO EM FLOW SHOP . . . . 40 3.1 Revisão de literatura sobre os problemas de flow shop com objetivos just-in-time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.2 Modelagem matemática do problema de flow shop . . . . . . . . . . 45 4 MÉTODO DE DECOMPOSIÇÃO DE BENDERS APLICADO NO PROBLEMA DE SEQUENCIAMENTO . . . . . . . . . . . . . . . . 52 4.1 Aplicações de Benders nos problemas de sequenciamento . . . . . . 57 4.2 Variações do método de decomposição de Benders para o JIT-FSP 60 5 RESULTADOS COMPUTACIONAIS . . . . . . . . . . . . . . . . . . 68 5.1 Estudo 1 - O sistema BIOBAB . . . . . . . . . . . . . . . . . . . . . . 70 5.2 Estudo 2 - Vantagens do tratamento biobjetivo comparado ao monoobjetivo do JIT-FSP . . . . . . . . . . . . . . . . . . . . . . . . . 85 5.3 Estudo 3 - Comparação dos métodos biobjetivos . . . . . . . . . . . 91 5.4 Estudo 4 - Variações do método de decomposição de Benders . . . 103 6 CONSIDERAÇÕES FINAIS . . . . . . . . . . . . . . . . . . . . . . . 108 REFERÊNCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 APÊNDICE A - Decomposição de Benders . . . . . . . . . . . . . . 118 APÊNDICE B - O sistema BIOBAB . . . . . . . . . . . . . . . . . . 120 13 1 Introdução Em algumas indústrias, para fazer o planejamento da produção, é necessário determinar uma sequência de tarefas que precisam ser executadas, na mesma ordem, em diferentes máquinas para atender objetivos distintos. Esse sequenciamento de tarefas é uma solução de um problema conhecido na literatura como Problema de Sequenciamento em Flow shop (FSP, sigla em inglês). Um dos objetivos a serem otimizados no FSP é o de concluir a tarefa no prazo (just-in-time), que pode ser modelado através dos objetivos de pontualidade: adiantamento total e atraso total. Para diminuir o adiantamento total, uma possibilidade seria concluir as tarefas no prazo, o que é difícil ser feito para todas as tarefas. Outra possibilidade seria atrasá-las, aumentando o atraso total. Para diminuir o atraso total, de forma análoga, ou conclui-se as tarefas no prazo ou adianta-se a conclusão delas. Essa dinâmica de melhorar o adiantamento total resultar, quase inevitavelmente, em prejudicar o atraso total, e vice-versa, é constantemente deixada em segundo plano pela literatura ao tratar ambos os objetivos simultaneamente em um único objetivo. A globalização econômica e a intensa competição de mercado têm incentivado as empresas a aprimorarem suas estruturas de produção para diminuir os custos, aumentar a qualidade dos processos e aperfeiçoar a satisfação de seus clientes ([1]). No FSP, os objetivos de adiantamento total e atraso total estão, por vezes, relacionados à satisfação do cliente. Esse fato dificulta a atribuição de valores monetários a esses objetivos, fazendo com que a soma deles não reflita as necessidades práticas do problema, resultando em soluções pouco realistas ([2, 3]). Outra dificuldade em combinar objetivos conflitantes em um único critério está na atribuição de pesos aos objetivos, o que pode exigir diversas iterações com o tomador de decisão até se alcançar os resultados desejados ([4]). Uma forma de abordar esse problema, evidenciando o trade-off entre o adiantamento total e o atraso total, é por meio da otimização multiobjetivo, que fornece um leque de soluções para que o tomador de decisão escolha a que mais se adeque ao seu cenário industrial. Na resolução de um problema de otimização multiobjetivo alguns dos principais métodos utilizados são os métodos de escalarização que transformam uma função multiobjetivo em monoobjetivo e encontram um conjunto de soluções através de uma sequência de subproblemas monoobjetivos. A escolha de métodos multiobjetivos adequados é de grande importância, principalmente para problemas de otimização linear inteira, nesse caso, o uso de métodos alternativos como os de busca em árvore tornam-se atrativos. No entanto, métodos de busca em árvore por vezes possuem limitação para resolver problemas realísticos de grande porte. Um recurso utilizado na literatura para resolver problemas maiores são métodos baseados na decomposição de Benders. Assim, essa tese tem como objetivo explorar a natureza biobjetivo do problema de 14 sequenciamento just-in-time flow shop (JIT-FSP). Além disso, é proposto o uso de métodos exatos para resolver o problema, metodologia pouco explorada na literatura, e a aplicação da decomposição de Benders. As principais contribuições são: • Formulação do modelo de otimização linear biobjetivo para o JIT-FSP (Seção 3.2); • Proposição das ferramentas matemáticas para analisar a solução obtida pela aborda- gem monoobjetivo em uma perspectiva biobjetivo (Seção 2.3) • Uso do sistema (BIOBAB) proposto em [5] para resolver o JIT-FSP (Seções 5.1, 5.1 e 5.3); • Implementação de uma relação de dominância da literatura para auxiliar o tomador de decisão na filtragem da fronteira de Pareto (Seção 5.3); • Aplicação da decomposição de Benders em um método de escalarização para resolver o JIT-FSP, bem como cinco modificações de Benders (Seção 4.2); • Estudo computacional e estatístico do impacto no desempenho de cinco modificações no método de Benders clássico (Seção 5.4); Os capítulos dessa tese possuem a seguinte organização, no Capítulo 2 apresentam-se os conceitos básicos da otimização linear inteira multiobjetivo, métodos de solução e as ferramentas matemáticas propostas. No Capítulo 3 é realizado uma revisão do JIT-FSP e se propõe uma modelagem do problema. No Capítulo 4 aplica-se o método de decomposição de Benders no JIT-FSP, bem como, cinco variações no método. No Capítulo 5 realiza-se quatro estudos computacionais com os objetivos de: comparar métodos do sistema BIOBAB, demonstrar as vantagens de fazer uma abordagem biobjetiva do JIT-FSP e analisar os impactos no desempenho das variações do método de descomposição de Benders. 15 2 O problema de otimização linear inteiro mul- tiobjetivo A otimização multiobjetivo é uma área do conhecimento que tem crescido cada vez mais ([6]). Diferente da otimização monoobjetivo, que considera apenas um objetivo, a otimização multiobjetivo leva em consideração vários objetivos conflitantes para o problema. Um problema de otimização multiobjetivo (POM) pode ser representado conforme (2.1)-(2.2). Nesse problema, x são as variáveis de decisão e X ⊂ Rn representa o conjunto factível do problema. A função objetivo f é uma função vetorial com imagem no espaço Rp, com p > 1, no qual cada entrada dessa imagem representa o valor de um objetivo específico. Min f(x) = (f1(x), f2(x), . . . , fp(x)) (2.1) S.a : x ∈ X ⊂ Rn (2.2) A função objetivo f em (2.1)-(2.2) é o que caracteriza o problema como multiobjetivo. Na literatura esse problema multiobjetivo está inserido no contexto da análise de decisão com múltiplos critérios ([7, 8, 6]) pelo fato do decisor possuir diferentes critérios conflitantes para analisar o problema. Também apresenta algumas similaridades com a otimização vetorial ([9, 10]) pois a imagem de cada solução representa um vetor no espaço Rp. Nessa tese utiliza-se as terminologias presentes na otimização multiobjetivo e a principal base teórica é o livro do Greco, Ehrgott e Figueira [6]. Considerando a função f : Rn → Rp, se define os espaços do problema (2.1)-(2.2), Definições 1 e 2. Com essas definições, conclui-se que o conjunto factível do problema é subconjunto do espaço decisão e Y = f(X ) é a imagem do conjunto factível, um subconjunto do espaço critério. Definição 1 (Espaço decisão [6]). Rn representa o espaço decisão. Definição 2 (Espaço critério [6]). Rp é chamado de espaço critério ou espaço objetivo. Em um problema de minimização monoobjetivo, para saber se uma solução é melhor do que outra, basta verificar qual imagem possui o menor valor. Sendo o espaço critério um espaço p−dimensional, existem diferentes relações de ordem para comparar pontos. Na Definição 3 apresentam-se três notações necessárias para estabelecer as relações de ordem para comparar pontos multidimensionais. Definição 3 ([6]). Sejam y1, y2 ∈ Rp, assim: 1. y1 ≦ y2 se y1 k ≤ y2 k, k = 1, . . . , p; 16 2. y1 ≤ y2 se y1 k ≤ y2 k, k = 1, . . . , p e y1 ̸= y2; 3. y1 < y2 se y1 k < y2 k, k = 1, . . . , p. Através dessas notações define-se a relação de Pareto (e.g. [11, 12, 6]). Definição 4 (Relação de Pareto [6]). Considere que y1 é preferível (ou indiferente) do que y2 segundo a relação de Pareto se, e somente se, y1 ≦ y2. A relação de Pareto (Definição 4) é uma relação de ordem parcial. Essa característica possibilita que dois pontos no espaço critério não se relacionem, ou seja, sendo y1, y2 ∈ Rp não ocorre y1 ≦ y2 nem y2 ≦ y1. Esse fato permite que um POM tenha um conjunto de soluções chamadas de Pareto ótimas ou eficientes (Definição 5) com diferentes imagens. Mais duas variações de soluções eficientes são definidas a seguir. Definição 5 (Solução eficiente [6]). Uma solução x∗ ∈ X é eficiente se não existir x ∈ X tal que f(x) ≤ f(x∗). O conjunto de todas as soluções eficientes é representado por XE. Definição 6 (Fracamente eficiente e estritamente eficiente [6]). Considere X ⊂ Rn. 1. x̂ ∈ X é fracamente eficiente se não existir x ∈ X tal que f(x) < f(x̂); 2. x̂ ∈ X é estritamente eficiente se não existir x ∈ X , x̂ ̸= x, tal que f(x) ≦ f(x̂). Utilizando a relação de Pareto, é dito que se x1, x2 ∈ X e f(x1) ≤ f(x2), então x1 domina x2 e f(x1) domina f(x2). Com isso, a imagem das soluções eficientes são chamadas de pontos não dominados (Definição 7) e seu conjunto é chamado de fronteira de Pareto (Definição 8). Definição 7 (Ponto não dominado [12]). Um ponto f(x∗) ∈ Y é não dominado se x∗ é uma solução eficiente. Definição 8 (Fronteira de Pareto). O conjunto de pontos não dominados f(XE) = YN é chamado de fronteira de Pareto. Apesar do problema (2.1)-(2.2) possuir p objetivos, isso não garante que ele seja verdadeiramente multiobjetivo. Essa verificação é feita através do ponto ideal (Definição 9). Se o ponto ideal for imagem de alguma solução factível, então não existe conflito entre os objetivos, ou seja, a fronteira de Pareto é composta por apenas um ponto. Definição 9. O ponto yI = (yI 1 , yI 2 , . . . , yI p) dado por yI k = Min{fk(x) | x ∈ X ⊂ Rn}, k = 1, . . . , p é chamado de ponto ideal. 17 Determinar toda a fronteira de Pareto não é uma tarefa simples, e para o tomador de decisão, analisar a fronteira completa e decidir qual ponto implementar pode ser tão difícil quanto determiná-la ([13]). Além disso, principalmente nas pesquisas que utilizam algoritmos baseados em população (e.g. [14]), existe uma dificuldade em garantir a diversidade da fronteira de Pareto e a convergência dos algoritmos. Para lidar com essas problemáticas, foram desenvolvidas novas relações de dominância, uma delas é a ϵ-dominância proposta por Laumanns et al. [15] (Definição 10). Definição 10 (ϵ-dominância [15]). Sejam y1, y2 ∈ Rp e ϵ > 0. É dito que y1 ϵ-domina y2 se 1 ou 2 ocorrem. 1. Aditiva: y1 k ≤ y2 k + ϵ, k = 1, . . . , p; 2. Multiplicativa: y1 k ≤ (1 + ϵ) · y2 k, k = 1, . . . , p. A ϵ-dominância permite uma tolerância ϵ > 0 para que um ponto domine outro, por exemplo, sejam y1 = (2, 3) e y2 = (5, 2). Esses pontos não se relacionam segundo Pareto, mas pela ϵ-dominância aditiva com ϵ = 1, y1 ϵ-domina y2 pois y1 1 = 2 ≤ 5 + 1 = y2 1 + ϵ e y1 2 = 3 ≤ 2 + 1 = y2 2 + ϵ. Nessa tese será utilizado apenas a ϵ-dominância aditiva, que é referente ao item 1 da Definição 10, pela facilidade de implementação. Por meio da relação de dominância segundo Pareto e da ϵ-dominância é estabelecida uma região de dominância para cada ponto no espaço critério (Definição 11). Na Figura 1 ilustra-se a região R (Figura 1a) e a região Rϵ (Figura 1b) para um problema biobjetivo. É notório que Rϵ ⊃ R por permitir uma tolerância ϵ. Definição 11 (Região de dominância). Seja y1 = f(x1). A região de dominância do ponto y1 é dada por: 1. (segundo Pareto) R = {y2 ∈ Rp | y1 ≤ y2}; 2. (ϵ-dominância) Rϵ = {y2 ∈ Rp | y1 ϵ-domina y2}. Através da ϵ-dominância define-se uma fronteira de Pareto ϵ-aproximada (Definição 12) e uma fronteira ϵ-Pareto (Definição 13). Na Figura 2 estão ilustradas um exemplo das três fronteiras definidas, a fronteira de Pareto (Figura 2a) possui uma quantidade maior de pontos, a fronteira de Pareto ϵ-aproximada (Figura 2b) possui menos pontos e pode conter pontos que não pertencem a fronteira de Pareto e a fronteira ϵ-Pareto (Figura 2c) também possui menos pontos, mas somente pontos da fronteira de Pareto. Definição 12 (Fronteira de Pareto ϵ-aproximada). Sejam Fϵ ⊂ Rp, f(X ) = Y e ϵ > 0. É dito que Fϵ é uma fronteira de Pareto ϵ-aproximada, se para qualquer y ∈ Y existe y′ ∈ Fϵ tal que y′ ϵ-domina y. 18 Figura 1 – Regiões de dominância no espaço critério (a) Segundo Pareto (b) ϵ-dominância Fonte: Elaborado pelo autor. Definição 13 (Fronteira ϵ-Pareto). F∗ ϵ ⊂ Rp é uma fronteira ϵ-Pareto se ele é uma fronteira de Pareto ϵ-aproximada e contém apenas pontos da fronteira de Pareto. Outra relação de ordem importante é a relação lexicográfica. Considerando uma ordem de prioridade Ord = {o1, o2, . . . , op}, diz-se que y1 é preferível (ou indiferente) do que y2 segundo a relação lexicográfica se, e somente se, y1 = y2 ou para algum k, 1 ≤ k ≤ p, y1 i = y2 i , i = o1, o2, . . . , ok−1 e y1 ok < y2 ok . Diferente da relação de Pareto, a relação lexicográfica estabelece uma relação de ordem total. Uma maneira de resolver um POM utilizando a otimização lexicográfica é através de uma sequência de resoluções de subproblemas monoobjetivos dada pelo Algoritmo 1. Para cada i = 1, . . . , p o subproblema monoobjetivo Pi = Min{foi (x) |x ∈ Xi} é resolvido. Se existir apenas uma solução ótima (x∗) para o subproblema Pi, então o método encerra e a solução ótima (x∗) será a saída do algoritmo, pois qualquer outro x ∈ X provocaria foi (x) > f ∗ oi = foi (x∗). Caso contrário, o objetivo foi+1(x) é minimizado sem aumentar o valor do objetivo foi (x), ou seja, restrito a foi (x) ≤ f ∗ oi . Algoritmo 1: Algoritmo lexmin(fo1 , fo2 , . . . , fop) Entrada: f, X , Ord = {o1, o2, . . . , op} Saída: x∗ solução ótima lexicográfica 1 X1 = X ; 2 para i = 1, . . . , p faça 3 Resolva Pi = Min{foi (x) |x ∈ Xi} e obtenha f ∗ oi (valor ótimo de Pi) e x̄i (solução de Pi) ; 4 se x̄i é única então 5 PARE, x∗ = x̄i (solução ótima lexicográfica é a solução atual) 6 senão 7 Xi+1 = Xi ∪ {foi (x) ≤ f ∗ oi } 8 fim 9 fim 19 Figura 2 – Fronteiras de Pareto de um problema biobjetivo (a) Pareto (b) Pareto ϵ-aproximada (c) ϵ-Pareto Fonte: Elaborado pelo autor. A otimização lexicográfica é muito utilizada em etapas de métodos de solução como a caixa balanceada, ε-restrito, soma ponderada e branch-and-bound biobjetivo (e.g. [16, 5]). A solução do problema lexicográfico também é uma solução eficiente segundo Pareto que possui uma característica da fronteira (Definição 14). Na Seção 2.1 são apresentados métodos de solução para a relação de Pareto, que é o foco dessa tese. Definição 14 (Pontos extremos). A solução do Algoritmo 1 é uma solução eficiente e sua imagem é chamada de ponto extremo ou ponto lexicográfico. Os pontos extremos de um problema definem a região que contém a fronteira de Pareto. 20 2.1 Métodos de solução Para facilitar a compreensão de conceitos e dos métodos de solução discutidos nessa seção, considere o Problema 1 = Min{(f1(x), f2(x)) | x ∈ X ⊂ Zn} um problema de otimização inteira biobjetivo (POIB), com espaço critério Y ⊂ Z2 e fronteira de Pareto YN = {A, B, C, D} exibido na Figura 4. Na Figura 3 apresenta-se uma legenda que será utilizada em figuras seguintes. Figura 3 – Legenda dos pontos no espaço critério do Problema 1 Fonte: Elaborado pelo autor. Figura 4 – Espaço critério do Problema 1 Fonte: Elaborado pelo autor. Existem diferentes métodos para encontrar a fronteira de Pareto de um POIB: esca- larização, branch-and-bound, heurísticos e metaheurísticos. No contexto de métodos de solução para um POIB, a Definição 15 auxilia na escolha do método a ser utilizado. 21 Definição 15 (Pontos suportados e não suportados). Sejam x ∈ XE e y = f(x), assim: 1. x é uma solução eficiente suportada se y estiver na parte convexa da fronteira de Pareto. Nesse caso, y é um ponto não dominado suportado; 2. Caso y não esteja na parte convexa da fronteira, então ele é um ponto não dominado não suportado e x será uma solução eficiente não suportada; 3. Os conjuntos das soluções eficientes suportadas e não suportadas são denotados por XsE e XnE. O conjunto das suas imagens são YsN e YnN . Na Figura 4 o ponto B é um ponto não dominado não suportado. Ao traçar o segmento de reta AC nota-se que o ponto B fica acima do segmento. Nos problemas de otimização inteira biobjetivos o espaço decisão não é convexo e por isso, em geral, o espaço critério e a fronteira de Pareto não serão convexos, evidenciando a importância de distinguir esses pontos. 2.1.1 Métodos de escalarização Alguns dos métodos mais populares para encontrar a fronteira de Pareto são os métodos de escalarização. Esses métodos consistem em transformar uma função objetivo vetorial em uma função objetivo escalar, e assim, encontrar os pontos da fronteira através de uma sequência de solução de subproblemas monoobjetivos. Existem diversas formas de se fazer esta transformação: considerar apenas um objetivo e adicionar os outros em restrições, ponderar os objetivos em uma soma, etc. Com essas possibilidades, existem algumas características desejáveis nos métodos de escalarização que são apresentadas na Tabela 1. Tabela 1 – Características desejáveis nos métodos de escalarização Característica 1 Se (2.1)-(2.2) com apenas um objetivo não é NP-difícil, então o problema escalar também não é. Característica 2 Toda solução ótima do problema escalar é uma solução eficiente de (2.1)-(2.2). Característica 3 Todas as soluções eficientes são obtidas pelo problema escalar com parâmetros adequados. Característica 4 Se o problema (2.1)-(2.2) é linear, então o problema escalar é linear. Introduzido por Haimes et al. [17] em 1971, o método ε-restrito é um dos métodos de escalarização mais conhecidos ([12]). Nele, apenas um dos p objetivos em (2.1)-(2.2) é minimizado enquanto os outros são adicionados ao conjunto de restrições do problema. A forma geral do problema escalar é exibido em (2.3)-(2.5). 22 Min fk(x) (2.3) S.a : fj(x) ≤ εj, j = 1, . . . , p, j ̸= k (2.4) x ∈ X (2.5) Dentre as características desejadas nos métodos escalares, o ε-restrito satisfaz 2, 3 e 4. Para problemas biobjetivos, o método ε-restrito é de fácil implementação. Uma maneira de se fazer isso é apresentado no Algoritmo 2. No algoritmo, ρ é um valor estritamente positivo e que varia para cada problema. Em geral, para um problema de otimização inteira em que os parâmetros e variáveis são todos inteiros, ρ = 1 é sempre válido. Vale reforçar que as soluções dos problemas lexicográficos (linhas 1 e 2) fazem parte da saída do algoritmo (são soluções eficientes). Algoritmo 2: Algoritmo ε-restrito biobjetivo Entrada: f, X , ρ Saída: XE 1 Resolva lexmin(f2, f1), obtenha f ∗ 2 e x∗ e adicione x∗ a XE; 2 Resolva lexmin(f1, f2), obtenha f ∗ 1 e x̄ e adicione x̄ a XE; 3 ε = f ∗ 2 + ρ ; 4 enquanto f1(x∗) > f ∗ 1 faça 5 Resolva Min{f1(x) | f2(x) ≤ ε, x ∈ X } = P e obtenha x∗; 6 se x∗ for único então 7 adicione x∗ a XE 8 senão 9 escolha x∗ tal que f2(x∗) ≤ f2(x), ∀ x solução de P ; 10 adicione x∗ a XE 11 fim 12 ε := ε + ρ 13 fim É importante dizer que esse método pode obter soluções fracamente eficientes e que para apenas uma delas a característica 2 da Tabela 1 é satisfeita. Por exemplo, ao utilizar o Algoritmo 2 no Problema 1, nas linhas 1 e 2 são obtidos os pontos D e A respectivamente. Na linha 3 defini-se ε = 8 + 1 = 9. Dentro do laço de repetição, na primeira iteração é obtido o ponto C, na segunda iteração o ponto B e na terceira iteração, com ρ = 11, os pontos W e B são valores ótimos para P. Para identificar qual ponto é não dominado, ou seja, qual das soluções é a eficiente (característica 2) é necessário realizar um teste comparativo de dominância (linha 9). O método ε-restrito é exato e é capaz de determinar toda a fronteira de Pareto de um problema de otimização inteira com parâmetros inteiros e objetivos calculados por variáveis inteiras. Em problemas da literatura, principalmente com instâncias desafiadoras, a resolução dos subproblemas (linha 5 do Algoritmo 2) até a otimalidade pode não ser 23 possível. Quando isso ocorre, o método é utilizado de forma heurística limitando o tempo de solução dos subproblemas para um tempo inferior ao máximo. Dessa forma não há garantia que será encontrada a fronteira de Pareto, mas uma aproximação da fronteira, similar a fronteira de Pareto ϵ-aproximada mas sem saber o valor de ϵ. Uma variação do método ε-restrito é o método ε-restrito aumentado. Em sua versão biobjetivo, um dos objetivos é adicionado ao conjunto de restrições, como no clássico, mas a função objetivo é modificada para uma soma ponderada dos objetivos. Essa ponderação pode ser pré-determinada ou variar conforme mudam os subproblemas (e.g. [18]), mas em geral, é um peso pequeno na casa de milésimos. A forma geral do problema escalar é exibido em (2.6)-(2.8). A proposta dessa variação está em impedir que o método encontre soluções fracamente eficientes ao fornecer informação do segundo objetivo na função objetivo, pois para uma solução eficiente x∗ e uma fracamente eficiente x̄, tal que f1(x∗) = f1(x̄) é válido f2(x∗) < f2(x̄), logo f1(x∗) + µf2(x∗) < f1(x̄) + µf2(x̄) com µ > 0. Min f1(x) + µf2(x) (2.6) S.a : f2(x) ≤ ε (2.7) x ∈ X (2.8) Outro método de escalarização que é muito conhecido é o método da soma ponderada. Ele possui características diferentes do método ε-restrito. Na Tabela 1, o método da soma ponderada satisfaz as características 1, 2 e 4. Problemas que são resolvidos em tempo polinomial mantêm essa característica ao utilizar a soma ponderada. Porém, isso tem um custo, que é não encontrar toda fronteira de Pareto quando a fronteira é não convexa. A forma geral do problema escalar é exibido em (2.9)-(2.10). Min p∑ j=1 wjfj(x) (2.9) S.a : x ∈ X (2.10) Sendo w ∈ Rp ≥, a função objetivo de (2.9)-(2.10) é uma combinação linear não negativa dos objetivos de (2.1)-(2.2). Além disso, se os pesos forem normalizados a função objetivo torna-se uma combinação convexa. Dessa forma, é mais fácil entender quais pontos da fronteira de Pareto o método não consegue encontrar, que são as soluções eficientes não suportadas. Como a imagem de uma solução eficiente não suportada está na parte não convexa da fronteira de Pareto (YnN ), as curvas de níveis da função objetivo sempre terão um ponto não dominado suportado como mínimo. Em geral, utilizar apenas soma ponderada ou ε-restrito apresenta algumas limitações. Um caminho que as pesquisas começaram a seguir foi combinar diferentes métodos de escalarização para obter um novo método, como exemplo o método ε-restrito aumentado 24 que faz uma ponderação dos objetivos, similar à soma ponderada, e adiciona objetivos nas restrições, como no ε-restrito. Em Ehrgott [12], esses métodos são chamados de híbridos. Outros exemplos deles são o algoritmo de particionamento da fronteira ([19]) e o método da caixa balanceada ([16]). O método da caixa balanceada proposto em [16] é uma combinação do Algoritmo 1 e do Algoritmo 2. Para utilizar o método é preciso ter os pontos extremos da fronteira de Pareto. Resumidamente no caso biobjetivo, com os pontos extremos determina-se um retângulo no espaço critério que será a região de busca. Restrito a essa região, encontra-se um novo ponto utilizando o Algoritmo 1. Com esse novo ponto, determina-se um novo retângulo que será a nova região de busca. O método encerra quando não é mais encontrado um ponto na região de busca. Extensão do modelo escalar geral da literatura Em [10] é apresentado um modelo escalar geral que conforme são fixados os parâmetros ele se equivale aos métodos escalares apresentados na Seção 2.1.1. Aqui é proposta uma extensão desse modelo geral para que ele seja capaz de abranger mais métodos de escalarização ao adicionar ∑p k=1 µksk na função objetivo e as restrições (2.12) como, por exemplo, Método ε-restrito com restrições elásticas (e.g. [18]). O modelo é exibido em (2.11)-(2.13). Min pmax k=1 [νk(fk(x) − τk)] + p∑ k=1 λk(fk(x) − τk) + p∑ k=1 µksk (2.11) S.a : fk(x) + γksk ≤ εk, k = 1, . . . , p (2.12) x ∈ X , s ∈ Rp (2.13) A linearização do modelo (2.11)-(2.13) é exibida em (2.14)-(2.17). Min z + p∑ k=1 λk(fk(x) − τk) + p∑ k=1 µksk (2.14) S.a : fk(x) + γksk ≤ εk, k = 1, . . . , p (2.15) νk(fk(x) − τk) ≤ z, k = 1, . . . , p (2.16) x ∈ X , s ∈ Rp, z ∈ R (2.17) Uma prática muito comum na otimização é utilizar a relaxação langrangiana para obter limitantes para o problema. Assim como feito em [12], a relaxação lagrangiana do modelo (2.14)-(2.17) é exibida em (2.18)-(2.19), onde π e π′ são multiplicadores referentes aos conjuntos de restrições (2.15) e (2.16) respectivamente. 25 Min z(1 − ∑p k=1 π′ k) − ∑p k=1(λkτk + πkεk + π′ kνkτk) + ∑p k=1(λk + πk + π′ kνk)fk(x) + ∑p k=1(µk + πkγk)sk (2.18) x ∈ X , s ∈ Rp, z ∈ R, πk, π′ k ∈ R+ (2.19) Sendo τ um ponto de referência, ν, λ e µ pesos positivos, εk parâmetros positivos para todo k e π e π′ multiplicadores não negativos, ao fixar τ, ν, λ, µ, ε, π e π′ o problema (2.18)- (2.19) pode ser analisado, de tal forma que α = ∑p k=1 π′ k, β = ∑p k=1(λkτk + πkεk + π′ kνkτk), wk = ∑p k=1(λk + πk + π′ kνk) e w′ k = ∑p k=1(µk + πkγk). Assim, se obtem o problema (2.20). min x∈X ,s∈Rp,z∈R z(1 − α) − β + p∑ k=1 wkfk(x) + p∑ k=1 w′ ksk (2.20) Analisando o modelo (2.20) percebe-se que se α > 1 o problema é ilimitado. Caso α ≤ 1 o problema se resume a uma soma de somas ponderadas. Isso mostra que a relaxação lagrangiana, que é um recurso utilizado na otimização monoobjetivo, se resume a uma soma ponderada que pode não encontrar todos os pontos da fronteira de Pareto, principalmente na otimização combinatória. Esse fato reforça a importância de explorar métodos diferentes dos métodos de escalarização, como o branch-and-bound multiobjetivo (e.g. [5]) (Ehrgott, [12]). 2.1.2 Branch-and-bound multiobjetivo Os métodos de escalarização apresentados na Seção 2.1.1 são classificados como métodos de busca no espaço critério. Como discutido em [20], esses métodos tendem a ter vantagens sobre os métodos de busca no espaço decisão, pelo fato do espaço critério em geral ter dimensão menor do que o espaço de decisão. Porém, como visto na Seção 2.1.1, os métodos de escalarização possuem suas limitações: não há garantias de encontrar toda a fronteira de Pareto e utilizar a relaxação lagrangiana é equivalente a utilizar a soma ponderada. Dessa forma, assim como sugerido em [12] torna-se interessante investigar outros métodos de solução. Os métodos de busca no espaço de decisão como o branch-and-bound também apre- sentam suas limitações. A principal limitação está no fato que as árvores de ramificações de problemas de médio e grande porte podem ser muito grandes. Para melhorar seu desempenho, são utilizadas técnicas de métodos de busca no espaço critério para melhorar a ramificação e sondagem dos nós (e.g. [5]). Utilizar o método branch-and-bound para resolver um problema multiobjetivo possui algumas diferenças em relação a um problema monoobjetivo (e.g. [21, 22, 23]). Algumas características são mantidas, como: escolha da variável de ramificação e tipos de árvore (binária, ternária etc.). Outras características mantêm a mesma função, porém são bem diferentes: limitantes e testes de sondagem. Além disso, em cada nó da árvore é gerada 26 uma aproximação da fronteira de Pareto e existem novos elementos a serem explorados: ramificação no espaço critério. Na otimização monoobjetivo, utilizar somente dois limitantes (um superior e um inferior) é suficiente para realizar as podas, pois se trata de um problema escalar (dois pontos distintos determinam um intervalo). No problema multiobjetivo, apenas um valor para limitante superior e um para inferior, em geral, é insuficiente ou não gera benefício. Para que se cumpra o objetivo de ter limitantes para um problema será necessário um conjunto de limitantes inferiores e um conjunto de limitantes superiores. Considere Rp ≧ = {y ∈ Rp | y ≧ 0} e para s ∈ Rp, define-se a seguinte adição s+Rp ≧ = {s+y | y ∈ Rp ≧}. Definição 16 (Rp ≧ fechado e limitado [24]). Considere S ⊂ Rp. É dito que S é: 1. Rp ≧ fechado se S + Rp ≧ = {s + y | s ∈ S, y ∈ Rp ≧} é fechado; 2. Rp ≧ limitado se existe s0 ∈ Rp tal que S ⊂ s0 + Rp ≧. Definição 17 (Conjunto de limitantes [24]). Seja Y ⊂ YN . 1. L é um conjunto limitante inferior para Y se L é Rp ≧ fechado e limitado tal que Y ⊂ L + Rp ≧ e L ⊂ (L + Rp ≧)N 2. U é um conjunto limitante superior para Y se U é Rp ≧ fechado e limitado tal que Y ⊂ cl[(U + Rp ≧)c] e U ⊂ (U + Rp ≧)N , com cl representando o fecho do conjunto. A relação de dominância segundo Pareto discutida no início deste capítulo (Definição 11) se extende para conjuntos limitantes (Definição 18). É possível que um conjunto limitante L1 domine outro conjunto limitante L2. Essa dominância pode ser parcial, quando apenas alguns pontos de L2 são dominados, ou total, quando todos os pontos de L2 estão contidos na região de dominância de L1. Definição 18 (Região de dominância de um conjunto limitante). Seja L um conjunto limitante. A região de dominância de L é dada pela união das regiões de dominância de todo y ∈ L. Nas Figuras 5 e 6 estão ilustrados exemplos de conjuntos limitantes inferiores e superiores respectivamente. Na Figura 5 os pontos B1 e C1 formam um conjunto limitante inferior de Y = {A, B, C} pois Y está contido na região colorida em vermelho, que é a região dominada por B1 e C1, e L = {B1, C1} é R2 ≧ fechado e limitado. Na Figura 6, U = {U, V } é um conjunto limitante superior para Y , pois Y está contido na região colorida em verde e U é Rp ≧ fechado e limitado. É interessante ver que L e U são conjuntos limitantes de apenas uma parte da fronteira de Pareto. O ponto D não está limitado por nenhum dos dois conjuntos. Isso evidencia o aumento de complexidade ao trabalhar com conjuntos limitantes. 27 Figura 5 – Região dominada pelo conjunto limitante inferior L Fonte: Elaborado pelo autor. Figura 6 – Conjunto limitante superior U Fonte: Elaborado pelo autor. Na otimização monoobjetivo, um nó pode ser sondado se satisfizer uma das três condições: 1. o problema relaxado é infactível; 2. solução ótima do problema relaxado é inteira; 3. o limitante inferior obtido é pior que o valor da solução incumbente. 28 Na otimização multiobjetivo, apenas a condição 1 é exatamente igual. Em geral, para cada nó da árvore que será explorado é gerada uma aproximação da fronteira de Pareto. Esse nó só poderá ser sondado pela condição 2, se cada uma das soluções encontradas pelo problema relaxado for inteira, que em geral é pouco provável. A condição 3 somente é satisfeita se o conjunto limitante superior dominar toda a aproximação da fronteira de Pareto encontrada naquele nó. Na Figura 7, U = {E, B} é conjunto limitante superior e L = {L1, M1} conjunto limitante inferior. A região que está colorida de vermelho é toda região de dominância de L e a região colorida de verde é a região dominada por U . Percebe-se que U não domina todo L, somente onde as cores se sobrepõem, restando dois retângulos para serem explorados. Note que o ponto D pertence ao retângulo mais a direita e abaixo, ou seja, é importante ramificar esse nó. Figura 7 – Dominância parcial de conjuntos limitantes (condição 3 para sondagem biobje- tivo) Fonte: Elaborado pelo autor. Em resumo para sondar um nó, a condição 1 irá depender do problema e do tipo de busca feita, assim como no problema monoobjetivo. A condição 2, em geral, é satisfeita poucas vezes. Por fim, a condição 3 precisa de um conjunto limitante superior de muita qualidade para sondar o nó. Isso evidencia a dificuldade de reduzir o número de nós na árvore branch-and-bound. Também, reforça ainda mais a importância de se ter um conjunto limitante superior de qualidade. Toda essa discussão feita sobre o branch-and-bound multiobjetivo mostra que o conjunto limitante superior é de grande importância, porém, obter bons limitantes não é uma tarefa fácil. Nesse sentido, os autores Parragh e Tricoire [5] propuseram outros mecanismos para melhorar a sondagem de nós e para melhorar a exploração de nós ramificados em um 29 sistema chamado BIOBAB (biobjective branch-and-bound). Esse sistema será utilizado no estudo computacional, e por isso, um detalhamento é realizado a seguir. O sistema BIOBAB O BIOBAB é um sistema desenvolvido e utilizado em [5], que foi disponibilizado pelos autores no repositório https://github.com/JKU-PLM/BIOBAB. No sistema estão implementados os métodos: branch-and-bound, ε-restrito e caixa balanceada; para resolver problemas de otimização inteira mista biobjetivos. O pseudo-código do seu método branch- and-bound está presente no Algoritmo 3. Os três métodos implementados no sistema são utilizados no estudo computacional apresentado no Capítulo 5. Para detalhar os mecanismos do método branch-and-bound do sistema BIOBAB será utilizado o espaço critério associado ao Problema 1 (Figura 4). Na Figura 3 apresenta-se uma legenda para as Figuras 8, 9, 10 e 11. Para resolver cada nó o BIOBAB inicia utilizando otimização lexicográfica para encon- trar os pontos extremos (linhas 1 e 2). Com os pontos extremos, na linha 6 define-se pesos para os objetivos e utiliza-se a soma ponderada (Seção 2.1.1) para encontrar os pontos não dominados suportados. Quando não são mais encontrados pontos pela soma ponderada, a resolução do nó encerra. É importante dizer que os pontos encontrados são do problema in- teiro ou relaxado (opções do sistema no Apêndice 6), que em geral são limitantes inferiores. O conjunto limitante inferior é dado pelos segmentos que ligam os pontos de LB (linha 7). Isso pode ser observado na Figura 8, os pontos B1, E1, D1, F1 e C1 foram os pontos ótimos obtidos na resolução do nó raiz associado à resolução do Problema 1 e os segmentos em vermelho compõem o conjunto limitante inferior. É interessante dizer que durante a otimização lexicográfica foi encontrada uma solução inteira (possui imagem no ponto F), mesmo não sendo o ótimo da otimização lexicográfica ele foi armazenado pelo BIOBAB e já será utilizado como limitante superior. Nas linhas 1, 2 e 6 o asterisco (*) indica que toda solução factível encontrada durante a resolução é testada para possivelmente atualizar o conjunto limitante superior. 30 Figura 8 – Espaço critério associado à resolução do nó raiz do Problema 1 Fonte: Elaborado pelo autor. O processo realizado pela soma ponderada é pegar os pontos extremos e encontrar um ponto não dominado suportado entre eles. Com esse novo ponto, o mesmo processo se repete alterando esses pontos até que não sejam mais encontrados pontos não dominados suportados. Esse processo é realizado na expectativa de encontrar uma solução factível ou um limitante inferior. Na Figura 9 mostra-se como o segundo nó da fila branch-and- bound é explorado. As regiões em vermelho, que são os triângulos abaixo dos segmentos E1F1, F1D1, D1I1 e I1K1 não possuem pontos inteiros. Como a soma ponderada busca pontos nessas regiões, não há necessidade de resolver esses problemas ponderados. Além disso, esses segmentos já definem limitantes inferiores, então eles podem compor o conjunto limitante inferior para esse nó. É importante dizer que isso só vale para problemas em que os coeficientes e variáveis da função objetivo são inteiros, que é o caso do Problema 1. Essa é uma melhoria presente no BIOBAB, com dois pontos é realizado um teste para verificar se há pontos inteiros na região de busca da soma ponderada. Se não houver pontos inteiros, esses dois pontos são considerados limitantes inferiores e o método segue pulando a resolução desse problema ponderado. Caso contrário, o método segue normalmente. Essa melhoria é chamada de lower bound lifting e é realizada na linha 3 e durante a soma ponderada na linha 6 do Algoritmo 3. 31 Figura 9 – Espaço critério associado à resolução do segundo nó da fila branch-and-bound Fonte: Elaborado pelo autor. Na Figura 10 explora-se o oitavo nó da fila branch-and-bound. Nesse momento U = {A, W, L, D} e L = {S1}. Após definir U , o BIOBAB faz uma filtragem (Linha 9) para ver se esse nó pode ser sondado (condição 3). Então, três artifícios do BIOBAB são ativados. O primeiro artifício é verificar se há pontos inteiros na região não filtrada (região somente em vermelho), caso não tenha, o nó pode ser sondado (Linha 10). Como há pontos inteiros dentro da região é necessário fazer a ramificação. O segundo artifício é válido para problemas em que os coeficientes das variáveis na função objetivo são inteiros. É possível reduzir mais a região colorida de vermelho garantindo que se um ponto for encontrado nessa região ele não será dominado por algum limitante superior (linha 11). Isso não ocorre na Figura 7, o ponto V poderia ser encontrado e seria eliminado por ser dominado. O terceiro artifício é definir cortes no espaço objetivo para restringir a busca somente na região vermelha que tenha pontos inteiros. Esse artifício é chamado de ramificação do espaço objetivo, que é uma técnica utilizada pelos métodos de escalarização. A ramificação do espaço objetivo é representado pelo duplo asterísco (**) na linha 12 do Algoritmo 3. 32 Figura 10 – Espaço critério associado à resolução do oitavo nó da fila branch-and-bound Fonte: Elaborado pelo autor. Algoritmo 3: Algoritmo BIOBAB [5] Entrada: f, X , UB, LB, L Saída: XE, YN 1 e1 = lexmin(f1, f2)∗ ; 2 e2 = lexmin(f2, f1)∗ ; 3 se LowerBoundLifting é aplicável então 4 LB = segment({e1, e2}) 5 senão 6 LB = SPlbl(e1, e2)∗ ; 7 LB = segment(LB) 8 fim 9 LB = Filtering(LB) ; 10 LB = SegmentT ightening(LB) ; 11 LB = IntegerDominance(LB) ; 12 Ramifica LB e adiciona nós a L ∗ ∗ ; 13 enquanto L ̸= ∅ faça 14 Retire um nó de L ; 15 Repita as linhas de 1 a 12 16 fim As melhorias feitas no BIOBAB foram para aprimorar a sondagem multiobjetivo, evitar resolver problemas desnecessários e para reduzir o espaço de busca em cada nó, que são os maiores problemas no branch-and-bound multiobjetivo. É importante dizer que um dos principais usos da ramificação do espaço objetivo pode ser observado na Figura 11. Nela 33 percebe-se que após a filtragem são obtidas duas regiões em vermelho disconexas. Nesse caso a ramificação do espaço objetivo será feita junto com a ramificação das variáveis em cada uma dessas regiões, de forma independente, resultando em 4 nós na árvore. Figura 11 – Ramificação do espaço critério Fonte: Elaborado pelo autor. 2.2 Métricas de desempenho Com tantos métodos de solução diferentes, em que cada método possui vantagens e desvantagens, saber qual método tem o melhor desempenho não é tão simples. Como saber se a aproximação da fronteira de Pareto (AFP) do método A é melhor do que a aproximação da fronteira do método B? Para realizar essa tarefa, na literatura surgiram diversas métricas de desempenho. Como há diferentes fatores a serem analisados em uma AFP, as métricas de desempenho não conseguem avaliar a AFP por completo. Por esse motivo é muito comum nas pesquisas os autores utilizarem mais de uma métrica de desempenho. Em [25] são discutidos três fatores de interesse para serem avaliados em uma AFP. São eles: 1. Convergência: o quanto a AFP está próxima da fronteira de Pareto; 2. Diversidade: extensão e disposição dos pontos da AFP; 3. Cardinalidade: quantos pontos a AFP possui. Em trabalhos mais recentes, como visto em [26], os autores se referem às métricas de desempenho como indicadores de performance, mas não há distinção dos significados. Nessa tese, para analisar o desempenho dos métodos de solução serão utilizados duas métricas: cardinalidade (I#) e Hipervolume (IH). A cardinalidade é uma métrica unária e avalia o número de pontos da AFP, então quanto maior, melhor o método. O Hipervolume 34 [27] é uma métrica unária que consegue avaliar a convergência e diversidade da AFP. Essa métrica calcula o hipervolume da região dominada pela AFP e delimitada por um ponto de referência, em que esse ponto de referência é dominado por todos os pontos da AFP. Assim, quanto maior o hipervolume, melhor o desempenho do método. Para problemas biobjetivos o hipervolume é a área e pode ser calculado pela equação (2.21), no qual A [yi N , r] é a área formada pelo ponto não dominado yi N da AFP e o ponto de referência r. Note que ∩1 k=1 [ yk N , r ] = ∅, ou seja, para o primeiro ponto não é descontado nenhuma área de interseção. IH(YN) = |YN |∑ i=1 ( A [ yi N , r ] − A ∩i k=1 [ yk N , r ]) (2.21) Nas Figuras 12, 13 e 14 mostra-se o hipervolume de algumas AFPs. A AFP observada estará sendo representada por pontos pretos preenchidos (•) e os outros pontos no espaço serão representados por pontos pretos não preenchidos (◦). Na Figura 12 estão o hiper- volume (área dominada) da AFP1 = {T, Q} e da AFP2 = {S} em relação ao ponto de referência M1 (ponto em azul). Nela a métrica hipervolume não reflete a característica cardinalidade das AFPs, pois a AFP1 com mais pontos (Figura 12(a)) tem hipervolume igual a 5 u.a., que é menor do que o hipervolume da AFP2 (Figura 12(b)) com 9 u.a. O fato do ponto S dominar os pontos T e Q faz com que o hipervolume da AFP2, que contém o ponto S, seja maior. Figura 12 – Hipervolume e quantidade de pontos da AFP1 e AFP2 (a) AFP1 (b) AFP2 Fonte: Elaborado pelo autor. Na Figura 13 estão o hipervolume da AFP3 = {H, V, U} e da AFP4 = {H, U, A1} em relação ao ponto de referência M1 e a característica diversidade é analisada. É importante dizer que para isso, as duas AFPs possuem a mesma quantidade de pontos e esses pontos não são comparáveis, dessa forma as AFPs se diferenciam apenas em diversidade. Na Figura 13(a) os pontos V e U estão relativamente próximos, o que reflete em uma área menor de dominância (IH = 38 u.a.), enquanto na Figura 13(b) os três pontos estão melhor distribuídos, provocando uma área de dominancia maior (IH = 42 u.a.). É importante lembrar que a diversidade reflete a extensão e a distribuição dos pontos na AFP. Na Figura 13(b) a AFP4 é mais extensa e está melhor distribuída. 35 Figura 13 – Hipervolume e diversidade da AFP3 e AFP4 (a) AFP3 (b) AFP4 Fonte: Elaborado pelo autor. Na Figura 14 estão o hipervolume da fronteira de Pareto do Problema 1 (IH = 73 u.a.). É notório que o hipervolume da fronteira de Pareto é maior do que as AFPs das Figuras 12 e 13. Além disso, quanto mais próximo a AFP está da fronteira (convergência) mais seus hipervolumes se aproximam. Isso mostra a capacidade do hipervolume em analisar a convergência das AFPs. É claro que para ter a noção de quão próximo da fronteira a AFP está, é necessário ter a fronteira de Pareto. Porém, como em geral a fronteira não é conhecida, é dito que quanto maior o valor do hipervolume da AFP, mais próximo ela está da fronteira de Pareto. É dessa forma que o hipervolume é utilizado para comparar métodos de solução. 36 Figura 14 – Hipervolume da fronteira de Pareto Fonte: Elaborado pelo autor. Duas razões justificam a escolha da métrica cardinalidade e hipervolume para serem utilizadas no estudo apresentado no Capítulo 5. A primeira, é porque o hipervolume junto com o cardinalidade conseguem avaliar todos os critérios de interesse de uma AFP de cada método. A segunda razão é por essas métricas serem uma das mais utilizadas segundo o levantamento feito em [25]. Uma forma alternativa de utilizar informações do hipervolume é através do hiper ratio, que é a razão entre o hipervolume da AFP e da fronteira de Pareto (Equação 2.22) (e.g. [26]). Dessa forma, o valor máximo que o hiper ratio assume é 1, quando a AFP é exatamente a fronteira de Pareto, facilitando a interpretação da métrica. Para contornar a necessidade de ter o hipervolume da fronteira de Pareto, ao avaliar o desempenho de mais de um método, se propõe utilizar o maior hipervolume conhecido para substituir o hipervolume da fronteira de Pareto. Essa prática é utilizada na Seção 5.3 HR(AFP ) = IH(AFP ) IH(YN) (2.22) 37 2.3 Ferramentas matemáticas propostas para análise de pontos na fronteira de Pareto Para alcançar os objetivos dessa tese foram desenvolvidas ferramentas matemáticas capazes de localizar pontos na fronteira de Pareto. Essa necessidade surgiu porque, até onde sabemos, essa pesquisa é a primeira a explorar a natureza biobjetivo do JIT-FSP. Apesar das ferramentas serem propostas para explorar a fronteira de Pareto do JIT-FSP, elas podem ser aplicadas na fronteira de Pareto de qualquer problema de otimização biobjetivo. As três primeiras ferramentas foram desenvolvidas para localizar a imagem da solução monoobjetivo na fronteira de Pareto. O intuito delas é informar, algebricamente, o quão próximo esse ponto está de algum ponto extremo. Para os cálculos não sofrerem distorções, a fronteira de Pareto é normalizada. A primeira ferramenta (DI) é baseada em distância e utiliza do ponto ideal (Definição 9) como referência. A segunda (Dµ) também é baseada em distância com a diferença do ponto de referência ser o ponto médio entre os pontos extremos da fronteira de Pareto. A terceira (D∆) é dada pelo módulo da diferença entre os objetivos. Para as três ferramentas, quanto maior o valor retornado, mais próximo de algum ponto extremo esse ponto está, sendo 1 o valor máximo e 0 o mínimo. Será dito que o ponto está equilibrado quando os objetivos não são priorizados (entre 0 e 0.1), moderado (entre 0.1 e 0.5) e desiquilibrado quando prioriza algum dos objetivos (entre 0.5 e 1). A Dµ será utilizada para explicar como é determinada a posição de um ponto na fronteira de Pareto. Primeiro calcula-se a distância de cada ponto até µ. Em seguida identifica-se o máximo (Max) e o mínimo (Min) dessas distâncias. Finalmente, uma função suave (2.23) é usada para criar uma função teste em (2.24), e através dessa, define-se a Dµ em (2.25). A Dµ é uma função teste que leva o valor da distância entre um ponto não dominado e o ponto de referência até o intervalo entre zero e um. A DI e D∆ são calculadas da mesma forma e também são funções testes. f(x) =  0 , se x ≤ 0 e− 1 x , se x > 0 (2.23) g(x) = f(x) f(x) + f(1 − x) (2.24) Dµ(x) = g ( x − Min Max − Min ) =  0 , se x ≤ Min e− 1 x , se Min < x < Max 1 , se x ≥ Max (2.25) Graficamente, a medida Dµ pode ser representada pela Figura 15. No arco circular verde estão representadas as menores distâncias até o ponto de referência µ ilustrado pelo 38 “x” de cor preta. A seta em verde indica a região dos pontos equilibrados (3 pontos dessa fronteira de Pareto). O arco circular laranja indica o início da região dos pontos moderados (nenhum ponto nessa fronteira) e sua seta exibe a extensão dessa região. Por fim, o arco circular vermelho indica o início da região dos pontos desequilibrados (3 pontos dessa fronteira de Pareto). Figura 15 – Regiões de equilíbrio baseado em distância e µ como referência Além de analisar o desequilíbrio da solução monoobjetivo, será analisado o aumento percentual máximo (SPmax), médio (SPµ) e mínimo (SPmin) da soma ponderada dos pontos da fronteira de Pareto em relação à solução monoobjetivo. Essa medida irá informar o trade-off entre priorizar o valor monoobjetivo e adequar a solução ao cenário industrial, ou seja, essa medida permite conhecer o aumento na solução monoobjetivo para cada ponto na fronteira de Pareto. Na Figura 16 demonstra-se que para a fronteira de Pareto ilustrada na figura, o aumento percentual máximo não chega a 1.5%, em média esse aumento é de 0.61% e existem outras soluções que não apresentam aumento no objetivo. O uso dessa ferramenta, assim como é exibido na Figura 16, pode ser útil para o tomador de decisão, pois o permite visualizar a variação da função objetivo ao mesmo tempo que escolhe um ponto na fronteira de Pareto. Figura 16 – Aumento percentual da soma ponderada em relação à solução monoobjetivo 39 A quarta ferramenta proposta consiste em identificar os pontos não dominados não suportados presentes na fronteira de Pareto. O pseudocódigo utilizado está apresentado no Algoritmo 4. Este algoritmo verifica, para cada par de pontos (A, B) na fronteira de Pareto, se um determinado ponto P está acima do segmento AB, ou seja, se é não suportado. A identificação de pontos não dominados não suportados visa demonstrar a importância da utilização de métodos multiobjetivos adequados. Se os pontos não suportados constituírem a maioria da fronteira de Pareto e for utilizado o método da soma ponderada, a abordagem multiobjetivo pode não fornecer efetivamente uma gama de escolhas para os decisores. Isto poderia também levar à conclusão incorreta de que existe pouco conflito entre os objetivos. Por conseguinte, é importante utilizar um método que determine todos os pontos não dominados, suportados e não suportados. Algoritmo 4: Pseudo-código para identificar pontos não suportados Entrada: YN Saída: YnN , YsN 1 para (A, B) ∈ C |YN | 2 faça 2 para P entre A e B faça 3 se yP > yB−yA xB−xA (xP − xA) + yA então 4 adicione P a YnN (é não dominado não suportado) 5 senão 6 continue 7 fim 8 fim 9 fim 10 YsN = YN − YnN 40 3 O problema de sequenciamento em flow shop O Problema de sequenciamento em flow shop (FSP) é um importante problema de planejamento da produção. A solução do problema consiste em encontrar uma sequência de n tarefas que devem ser processadas por todas as m máquinas, respeitando um fluxo unidirecional, ou seja, sempre da primeira à última máquina. Cada tarefa j possui um tempo pjk para ser processada em cada máquina k. Será considerado que não há tempo de preparo das máquinas e as tarefas em execução não podem ser interrompidas. Além disso, as sequências de execução das tarefas devem ser iguais para todas as máquinas, configurando um problema de sequenciamento em flow shop permutacional ([28]). Um recurso utilizado para visualizar a solução de um problema de sequenciamento é o gráfico de Gantt. Um exemplo de gráfico de Gantt está presente na Figura 17. Nele estão ilustrados o sequenciamento de 5 tarefas (barras coloridas) em 3 máquinas (eixo vertical). Cada barra colorida mostra o instante de início e de término do processamento da tarefa em determinada máquina, sendo o seu comprimento exatamente o tempo de processamento da tarefa naquela máquina. Por exemplo, a tarefa J3 iniciou seu processamento na máquina 1 no instante 0, terminou no instante 50 e já iniciou seu processamento na máquina 2. Essa forma de visualizar a solução também pode servir como recurso para o tomador de decisão, pois facilita a validação e/ou escolha da solução, quando existem diversas soluções eficientes. 41 Figura 17 – Sequenciamento de 5 tarefas em 3 máquinas 0 50 100 150 200 250 300 350 400 M3 M2 M1 n = 5, m = 3 J3 J2 J5 J1 J4 Fonte: Elaborado pelo autor. O problema de sequenciamento pode ser resolvido considerando diversos objetivos. Sejam Cjk o instante de conclusão da tarefa j na máquina k e dj a data de vencimento da tarefa j, se define alguns dos principais objetivos tratados na literatura ([29]). O makespan é definido como sendo o instante de conclusão da última tarefa da sequên- cia na última máquina, ou seja, a duração total da programação. Matematicamente Cmax = max{C1m, C2m, . . . , Cnm}. Minimizar Cmax é um objetivo que visa maximizar a utilização das máquinas ([28]). Outra medida que se relaciona com o aproveitamento das máquinas, é o tempo total de fluxo, ou flowtime (F ), calculado como F = ∑ j Cjm. Outros dois objetivos são minimizar o adiantamento total (Min E) e minimizar o atraso total (Min T ). Considerando Ej = max{0, dj − Cjm} como o adiantamento da tarefa j e Tj = max{0, Cjm − dj} o atraso da tarefa j, são definidos E = ∑ j Ej e T = ∑ j Tj. Essas duas medidas são de pontualidade da entrega das tarefas e, quando minimizada a soma delas, é obtido o objetivo just-in-time, que busca concluir a tarefa no prazo. O objetivo just-in-time, assim definido, será o principal objetivo abordado nessa tese. Para saber de outros objetivos do sequenciamento veja, por exemplo, [28, 29, 30]. É natural que dado um sequenciamento de tarefas, este pode ser benéfico de acordo com alguns objetivos, mas ruim para outros. Na Figura 18 está exibido um gráfico de Gantt com o valor das medidas E, T , F e Cmax. Nesse sequenciamento o objetivo considerado durante a otimização foi a minimização de uma ponderação entre adiantamento total e atraso total. Perceba que para a medida F , este mesmo sequenciamento poderia ser reduzido apenas com o ajuste das conclusões das tarefas J5 (barra azul) e J2 (barra cáqui). Isso não ocorreu porque seria prejudicial para a minimização do adiantamento total. 42 Figura 18 – Sequenciamento e valor das medidas E, T , F e Cmax 0 50 100 150 200 250 300 350 M3 M2 M1 d1d2 d3 d4d5 E = 163, T = 134, F = 1269, C = 347 J5 J2 J3 J1 J4 Fonte: Elaborado pelo autor. Extensas revisões da literatura sobre o problema de sequenciamento em flow shop podem ser encontradas em [31, 32, 33]. Além disso, revisões de flow shop multiobjetivo foram publicadas em [34, 3, 35, 29]. Há na literatura uma predominância de abordagens heurísticas e metaheurísticas para resolver o problema de sequenciamento em flow shop (e.g. [34, 36, 37, 38]), o que possivelmente explica-se por razões práticas, devido ao grande porte dos problemas reais ([3]). Os métodos exatos, como o branch-and-bound, são menos explorados. Geralmente eles estão acompanhados de heurísticas para determinar soluções iniciais ou limitantes para o problema (e.g. [30]). Isto evidencia o potencial de pesquisa considerando modelos matemáticos, métodos de solução exata e métodos de decomposição, como é o caso do presente trabalho. Nas próximas seções, apresenta-se um recorte da literatura dos problemas de sequenci- amento just-in-time flow shop e modelos de otimização matemática para representá-lo. 3.1 Revisão de literatura sobre os problemas de flow shop com objetivos just-in-time Existem mais de uma forma de trabalhar com o objetivo just-in-time no problema de sequenciamento em flow shop. Uma delas é utilizar o adiantamento total e o atraso total. Outras formas podem ser encontradas em [39, 40]. Esse recorte foi definido utilizando a notação de três campos presente em [41] com α = Fm, β qualquer e γ contendo pelo menos um dos seguintes objetivos: ET, wET, (E, T ) ou (wE, wT ). 43 Nesse recorte da literatura foi possível notar que os objetivos adiantamento total e atraso total sempre são tratados simultaneamente em um único objetivo através de uma soma ponderada. Em sua maioria, são considerados pesos unitários para os objetivos (e.g. [42, 43, 44, 45]). Foi visto na Seção 2.1 que essa abordagem corresponde a uma iteração do método da soma ponderada. Dessas pesquisas, poucas trabalham apenas com métodos exatos. Em [46], os autores fazem um estudo comparativo entre modelos posicionais e sequenciais apenas utilizando solvers comerciais. Em [47] também é realizado um estudo computacional para avaliar um modelo posicional para uma outra variante do problema. Por trabalharem com métodos exatos, no estudo computacional de ambas as pesquisas são utilizados instâncias de pequeno porte, máximo de 20 tarefas e máximo de 10 máquinas. Para melhorar o desempenho dos solvers, em [47], são propostos limitantes inferiores e superiores para o problema. Investir em métodos exatos tem grande importância até mesmo para desenvolver e/ou validar novas heurísticas. Em [43], os autores transformaram o problema de m máquinas em máquina única e propuseram um método branch-and-bound para poder avaliar o desempenho de heurísticas. Para instâncias de pequeno porte constatou-se que há um gap significativo entre o valor obtido pelas heurísticas quando comparado ao do método exato (valor ótimo). Isso mostrou a necessidade de aprimorar as heurísticas analisadas pelos autores. Para que esse tipo de comparação seja possível em instâncias de grande porte, é necessário melhorar os métodos exatos de alguma forma. Em [48] o autor propõe um método híbrido combinando a resolução de um problema inteiro misto com limitantes obtidos por uma heurística. Apesar dessa prática ser comum na literatura, nesse recorte somente essa pesquisa utiliza dessa metodologia. Os métodos mais utilizados pela literatura são os heurísticos e metaheurísticos. Em [49, 50, 51, 42] são propostos diferentes heurísticas construtivas e de composição. Em [42] os autores propuseram um método beam search com uma heurística construtiva capaz de aprimorar resultados obtidos em [49]. Essa técnica também é utilizada com métodos exatos, como o branch-and-bound. É uma forma de utilizar métodos exatos de forma heurística. Em [50] é proposta uma heurística construtiva ACH1 e através dela, são propostas 3 heurísticas compostas baseadas na ACH1 com diferentes estratégias de busca. Em seus testes computacionais, a heurística ACH4 que utiliza busca local iterativa obteve melhores resultados. Essa heurística foi utilizada posteriormente em [51] no problema de flow shop permitindo tempos ociosos para diminuir o adiantamento total. Os métodos metaheurísticos em sua maioria são algoritmos genéticos. Na pesquisa [52] são comparados diferentes métodos metaheurísticos e apresentadas vantagens e limitações para diferentes cenários operacionais. Em [44] é abordado o problema sem tempo de espera e com tempos de setup dependendo do sequenciamento. É utilizado um modelo inteiro misto para instâncias pequenas e um algoritmo genético para instâncias de médio e grande 44 porte. Prata e Fuchigami [53] exploram o problema considerando o bloqueio de tarefas em sua posição na máquina. O problema é resolvido utilizando um algoritmo genético guloso iterativo. Outros métodos também são explorados. Em [54] aborda-se o problema sem tempo de espera e utiliza um parallel simulated annealing para resolver o problema. Behnamian [55] faz uma abordagem biobjetiva sendo o primeiro objetivo o makespan e o segundo a soma do adiantamento total e atraso total. Para resolver o problema faz a ponderação dos objetivos e utiliza um algoritmo genético baseado em colônia de formigas. Tavana et al. [45] utiliza dos mesmos objetivos para explorar a variante de bloqueio de tarefas. O problema é resolvido combinando o método ε-restrito e métodos metaheurísticos multiobjetivos. Para todas essas pesquisas o adiantamento total e o atraso total são tratados simultaneamente em um único objetivo. Mesmo em [55, 45] que utilizam métodos multiobjetivos, não há uma separação. Mesmo quando o objetivo just-in-time é proposto de forma mais genérica, utilizando pesos não unitários, as pesquisas não variam esses pesos para implementar o método da soma ponderada, apenas fixam um par de pesos e resolvem o problema de forma monoobjetivo uma única vez, ou seja, uma iteração do método da soma ponderada. Isso pode ser visto em [56] em seu método branch-and-bound e em [57] transformando o problema em máquina única e utilizando programação dinâmica para resolvê-lo. Para essa forma de abordar o problema, as metaheurísticas continuam sendo as metodologias mais utilizadas, predominando os algoritmos genéticos, [58] propõem um modelo matemático que é resolvido pelo algoritmo proposto. Em [59] considera-se três objetivos que são ponderados em uma função objetivo escalar e resolve-se esse problema de forma monoobjetivo utilizando um algoritmo robusto. Um modelo com restrições não lineares é proposto em [60]. Em [61] aborda-se o problema integrado com manutenção das máquinas. Também são encontrados métodos baseados em simulated annealing em [62] para resolver um problema com parâmetros incertos, métodos de busca local iterativo em [63] para resolver uma variação com bloqueio de tarefas e em [64] são propostos quatro modelos matemáticos e quatro métodos baseados no coronavírus. Métodos baseados em particle swarm optimization são vistos em [65] para resolver o problema com setup dependendo do sequenciamento e em [66] o problema com setup dependendo do grupo de tarefas. A Tabela 2 apresenta a lista das pesquisas dentro do recorte feito da literatura. Até o presente momento e conhecimento, essa tese é a primeira a abordar o problema de sequenciamento permutacional em flow shop biobjetivo com o adiantamento total e o atraso total sendo tratados em objetivos distintos. Na Tabela 2, a primeira coluna lista o nome dos autores e na segunda os problemas resolvidos. Na terceira coluna apresentam-se o tipo de modelo, sendo posicional (P), sequencial (S) e temporal (T). A quarta coluna, estão descritos os métodos de solução utilizados: heurístico (H), metaheurístico (MH), branch-and-bound (B&B), otimização inteira mista (MIP) e transformação de problema 45 (Tr). Na última coluna, são exibidas as faixas de variação do porte das instâncias utilizadas nos testes computacionais. Em geral, os modelos matemáticos propostos na literatura são apenas descritos e, em alguns casos, apresentam pequenos comentários sobre sua implementação e desempenho computacional. Tabela 2 – Autores que resolveram o FSP com objetivo JIT Autoria Problema MIP Método Porte (n, m) Chandra et al. (2009) [49] Fm|prmu, dj = d|ET S H ([5, 100] , [5, 20]) Ramezanian et al. (2010) [58] Fm|prmu, rj , δij |wET S MH ([3, 30] , [3, 30]) Madhushini e Rajendran (2011) [56] Fm|prmu|wET + wF B&B ([9, 16] , [5, 20]) Akhshabi et al. (2012) [62] Fm|dj fuzzy|wET P MH ([3, 50] , [3, 45]) Roconi e Birgin (2012) [46] Fm|block|ET P, S MIP ([5, 20] , [3, 10]) Arabameri e Salmasi (2013) [65] Fm|nwt, sijk|wET S MH ([5, 100] , [2, 6]) Schaller e Valente (2013) [52] Fm|prmu|ET MH ([8, 100] , [5, 20]) Behnamian (2014) [55] Fm|sijk|Cmax, ET MH ([6, 100] , [2, 10]) Mhallah (2014) [48] Fm||ET P H, MIP ([10, 100] , [2, 12]) Mohammadi (2015) [59] Fm||wET + Cmax + Nj MH ([20, 200] , [5, 20]) Fernandez-Viagas et al. (2016) [50] Fm|prmu|ET H ([50, 350] , [10, 50]) Hamdi e Loukil (2017) [47] prmu, θjk|ET P MIP ([5, 20] , [3, 10]) Keshavarz et al. (2019) [66] Fm|prmu, shgi, fmls|wET S MH ([4, 100] , [2, 6]) Rezaeian et al. (2019) [60] Fm|prmp|wET P MH ([2, 40] , [2, 5]) Schaller e Valente (2019) [51] Fm||ET H ([15, 100] , [5, 20]) Birgin et al. (2020) [42] Fm|prmu, dj = d|ET S H ([5, 100] , [5, 20]) Schaller e Valente (2020) [43] Fm|nwt|ET P Tr, H, B&B ([8, 100] , [5, 20]) Branda et al. (2021) [61] Fm|maintenance|wET MH ([20, 40] , [5, 5]) Guevara-Guevara et al. (2022) [44] Fm|nwt, sijk|ET S MH ([4, 100] , [3, 20]) Missaoui e Boujelbene (2022) [63] Fm|block, dj = [ d− j , d+ j ] |wET MH ([20, 200] , [5, 20]) Fuchigami e Prata (2023) [64] Fm|prmu|wET + wd P, S MH ([20, 500] , [5, 20]) Geng et al. (2023) [57] Fm|prmu, pij = pj , dj = d, rej|wET + wd + ej Tr, PD (7, 3) Karacan et al. (2023) [54] Fm|nwt|ET S MH ([20, 500] , [5, 20]) Prata e Fuchigami (2023) [53] Fm|block|ET P MH ([20, 100] , [5, 20]) Tavana et al. (2023) [45] Fm|block|Cmax, ET P MH ([50, 500] , [5, 40]) Nessa tese Fm|prmu|E, T P B&B ([5, 100] , [3, 20]) 3.2 Modelagem matemática do problema de flow shop Modelagens matemáticas para o problema de sequenciamento em flow shop têm sido pouco exploradas na literatura ([35]). Nos trabalhos que apresentam modelos matemáticos de otimização para o problema, definem-se três tipos: sequencial, posicional e temporal. Em [29], os autores observam que para variantes do FSP, os tipos de modelos mais utilizados são os sequenciais e posicionais. Os modelos temporais tornam-se restritivos pelo grande aumento no número de variáveis. Um modelo da literatura que tem um bom controle no número de variáveis é o proposto em [67]. Em Wilson [67] é proposto um modelo posicional para o FSP e são definidos dois objetivos possíveis para o problema, minimizar Cmax e minimizar F . Nessa modelagem o autor trabalha com a posição h da tarefa j na sequência (xjh) e com os instantes de início das tarefas, em determinada posição h, na máquina k (Shk). Todos os parâmetros e variáveis do modelo são apresentados a seguir. Índices • j = índice da tarefa, com j = 1 . . . n • h = índice da posição em que a tarefa será processada, com h = 1 . . . n 46 • k = índice da máquina, com k = 1 . . . m Parâmetros • pjk = tempo de processamento da tarefa j na máquina k Variáveis • xjh = 1 se a tarefa j está na posição h para ser processada e 0 caso contrário • Shk = instante de início do processamento da tarefa da posição h na máquina k O modelo de Wilson [67] é apresentado em (3.1)-(3.9). Min Cmax = Snm + n∑ j=1 pjmxjn ou Min F = n∑ h=1 Shm (3.1) S.a : n∑ j=1 xjh = 1 , h = 1 . . . n (3.2) n∑ h=1 xjh = 1 , j = 1 . . . n (3.3) S11 = 0 (3.4) S1,k+1 = S1k + n∑ j=1 pjkxj1 , k = 1 . . . m − 1 (3.5) Sh+1,1 = Sh1 + n∑ j=1 pj1xjh , h = 1 . . . n − 1 (3.6) Sh,k+1 ≥ Sh,k + n∑ j=1 pjkxjh , h = 2 . . . n, k = 1 . . . m − 1 (3.7) Sh+1,k ≥ Shk + n∑ j=1 pjkxjh , h = 1 . . . n − 1, k = 2 . . . m (3.8) Shk ≥ 0, xjh ∈ B (3.9) Em (3.1) é definido o critério de otimização, minimizar o makespan ou minimizar o flowtime, respectivamente, como um dos objetivos do problema. As restrições (3.2) e (3.3) são restrições de designação. Em (3.2) determina-se que para cada posição apenas uma tarefa será processada, e em (3.3), determina-se que cada tarefa ocupará apenas uma posição. A restrição (3.4) garante que o início do processamento da tarefa na posição 1 na máquina 1 comece no instante 0. As restrições (3.5) calculam os instantes de início da tarefa na posição 1 em todas máquinas. As restrições (3.6) determinam os instantes de início de todas as tarefas na máquina 1. As restrições (3.7) e (3.8) garantem os instantes de início de cada tarefa nas máquinas seguintes e os instantes de início das tarefas seguintes em cada máquina. Em (3.9) é dado o domínio das variáveis. No início do capítulo discutiu-se sobre o Cmax e o F serem medidas que são calculadas a partir do instante de conclusão das tarefas. No modelo (3.1)-(3.9) utilizam-se esses mesmos 47 objetivos, porém as variáveis utilizadas para cálculos são os instantes de início. Com isso, é notório que existe uma relação entre as variáveis de início e as de conclusão que é dada por Chk = Shk + ∑n j=1 pjkxjh. Com essa relação propõe-se o modelo (3.10)-(3.18) que é adaptado do modelo (3.1)-(3.9). Min Cmax = Cnm ou Min F = n∑ h=1 Chm (3.10) S.a : n∑ j=1 xjh = 1 , h = 1 . . . n (3.11) n∑ h=1 xjh = 1 , j = 1 . . . n (3.12) C11 = n∑ j=1 pj1xj1 (3.13) C1,k+1 = C1k + n∑ j=1 pj,k+1xj1 , k = 1 . . . m − 1 (3.14) Ch+1,1 = Ch1 + n∑ j=1 pj1xj,h+1 , h = 1 . . . n − 1 (3.15) Ch,k+1 ≥ Ch,k + n∑ j=1 pj,k+1xj,h , h = 2 . . . n, k = 1 . . . m − 1 (3.16) Ch+1,k ≥ Chk + n∑ j=1 pjkxj,h+1 , h = 1 . . . n − 1, k = 2 . . . m (3.17) Chk ≥ 0, xjh ∈ B (3.18) Em (3.10) define-se um dos objetivos para o problema, minimizar o makespan ou minimizar o flowtime, respectivamente. As restrições (3.11)-(3.18)são análogas às restrições (3.2)-(3.9). Em Abreu e Fuchigami [30], os autores propuseram quatro modelos para o FSP com o objetivo de minimizar tempos ociosos e de espera. Dentre os quatro modelos, o que teve melhor desempenho foi uma adaptação do modelo (3.1)-(3.9) (modelo 4). A seguir apresentam-se as variáveis de decisão que se diferem do modelo (3.10)-(3.9). Variáveis • Ihk = tempo ocioso da máquina k antes da tarefa da posição h • Whk = tempo de espera da tarefa na posição h até iniciar na máquina k O modelo 4 proposto em [30] é exibido em (3.19)-(3.27). 48 Min n∑ h=1 m∑ k=1 (Ihk + Whk) (3.19) S.a : n∑ h=1 xjh = 1 , j = 1 . . . n (3.20) n∑ j=1 xjh = 1 , h = 1 . . . n (3.21) n∑ j=1 (pjkxj1) + I1k + W1k = I1,k+1 , k = 1 . . . m − 1 (3.22) C11 = n∑ j=1 pj1xj1 (3.23) Ch,k+1 − Chk − Whk = n∑ j=1 pj,k+1xjh , h = 1 . . . n, k = 1 . . . m − 1 (3.24) Ch+1,k − Chk − Ih+1,k = n∑ j=1 pj,kxj,h+1 , h = 1 . . . n − 1, k = 1 . . . m (3.25) m∑ k=1 W1k = 0 (3.26) Chk, Ihk, Whk ≥ 0, xjh ∈ B (3.27) O objetivo desse modelo (3.19)-(3.27) é minimizar os tempos ociosos das máquinas e de espera das tarefas. Uma forma de visualizar a minimização dessa medida é reduzir as lacunas no gráfico de Gantt, como mostra a Figura 19. As restrições (3.20) e (3.21) são restrições de designação, garantindo que cada tarefa ocupe apenas uma posição e que cada posição tenha exatamente uma tarefa. As restrições (3.22) calculam o tempo ocioso das máquinas até iniciar o processamento da tarefa de posição 1. A restrição (3.23) calcula o instante de conclusão da tarefa de posição 1 na máquina 1. As restrições (3.24) e (3.25) calculam os instantes de conclusão e, respectivamente, o tempo de espera das tarefas e o tempo ocioso das máquinas. A restrição (3.26) garante que a tarefa de posição 1 não terá tempo de espera e em (3.27) é dado o domínio das variáveis. 49 Figura 19 – Sequenciamento com tempos ociosos Fonte: Elaborado pelo autor. Com os modelos (3.10)-(3.18) e (3.19)-(3.27) é interessante notar que ao adicionar variáveis de folga em (3.16) e (3.17) são obtidas as mesmas restrições de (3.24) e (3.25). Para abordar o objetivo just-in-time é proposto uma adaptação do modelo (3.10)- (3.18). Como os objetivos E e T são definidos pela função máximo, é necessários adicionar as variáveis Eh e Th para h = 1, . . . , n e as restrições (3.34) e (3.35) para linearizar, respectivamente, os objetivos. O modelo biobjetivo proposto é apresentado em (3.28)- (3.36). Índices: • j = índice da tarefa, com j = 1 . . . n; • h = índice da posição em que a tarefa será processada, com h = 1 . . . n ; • k = índice da máquina, com k = 1 . . . m. Parâmetros: • pjk = tempo de processamento da tarefa j na máquina k; • dj = data de vencimento da tarefa j. Variáveis: • xjh = 1 se a tarefa j está na posição h para ser processada e 0 caso contrário; • Chk = instante de conclusão da tarefa da posição h na máquina k; 50 • Eh = adiantamento da tarefa da posição h; • Th = atraso da tarefa da posição h. Min ( n∑ h=1 Eh, n∑ h=1 Th) (3.28) s.t. n∑ j=1 xjh = 1, h = 1, ..., n (3.29) n∑ h=1 xjh = 1, j = 1, ..., n (3.30) C11 ≥ n∑ j=1 pj1xj1 (3.31) Ch,k+1 ≥ Chk + n∑ j=1 pj,k+1xjh, h = 1, ..., n, k = 1, ..., m − 1 (3.32) Ch+1,k ≥ Chk + n∑ j=1 pjkxj,h+1, h = 1, ..., n − 1, k = 1, ..., m (3.33) n∑ j=1 (djxjh) − Chm ≤ Eh, h = 1, ..., n (3.34) Chm − n∑ j=1 (djxjh) ≤ Th, h = 1, ..., n (3.35) xjh ∈ {0, 1}, Chk ≥ 0, Eh ≥ 0, Th ≥ 0, j = 1, ..., n, h = 1, ..., n, k = 1, ..., m. (3.36) Em (3.28) é definida a função biobjetivo contendo o adiantamento total como primeira coordenada do espaço objetivo e o atraso total como segunda coordenada do espaço objetivo. As restrições (3.29) e (3.30) são de designação. A restrição (3.31) permite que a tarefa de posição 1 inicie na máquina 1 no instante 0 ou após. As restrições (3.32) calculam os instantes de conclusão das tarefas nas máquinas seguintes e as restrições (3.33) calculam os instantes de conclusão das tarefas seguintes em cada máquina. As restrições (3.34) e (3.35) são usadas para linearizar a função objetivo e calculam, respectivamente, os objetivos adiantamento total e atraso total. Em (3.36) é dado o domínio das variáveis. Ao comparar os modelos (3.10)-(3.18) e (3.28)-(3.36), além da mudança dos objetivos, houve uma alteração nas restrições que calculam os instantes de conclusão. No modelo proposto por Wilson [67], como os objetivos tratados eram o Min Cmax ou Min F , exigir que a conclusão da primeira tarefa nas máquinas seguintes e a conclusão das tarefas seguintes na máquina 1 sejam satisfeitas com igualdade, ajuda restringindo mais o modelo e beneficia o objetivo escolhido por ser de aproveitamento das máquinas. Ao tratar a minimização do adiantamento total, que é um objetivo de pontualidade, manter a igualdade nas restrições faria com que, em geral, a primeira tarefa processada sempre fosse concluída com adiantamento, prejudicando a minimização desse objetivo. Portanto, relaxar as restrições (3.13)-(3.15) é uma forma de atender os objetivos de pontualidade. 51 Um aspecto importante na representação de problemas está no número de variáveis utilizadas para modela-lo. O número de variáveis de um modelo não é o fator decisivo da qualidade do modelo, porém, ter menos variáveis pode contribuir para isso. Em [67] é apresentado a dimensão do modelo (3.10)-(3.18) como 2mn + n − m restrições, n2 variáveis binárias e mn variáveis contínuas. O modelo (3.28)-(3.36) possui um aumento de 2n restrições e variáveis contínuas. Na Tabela, 3 apresenta-se a dimensão do modelo (3.10)-(3.18) com o objetivo Min Cmax ou Min F e do modelo (3.28)-(3.36). Também, apresentam-se os valores numéricos para instâncias de pequeno e de grande porte utilizadas no estudo computacional do Capítulo 5. Tabela 3 – Dimensão dos modelos (3.10)-(3.18) e (3.28)-(3.36) Modelo (3.10)-(3.18) Modelo (3.28)-(3.36) Geral (5, 3) (100, 10) Geral (5, 3) (100, 10) Restrições 2mn + n − m 32 2090 2mn + 3n − m 42 2290 Var. Binárias n2 25 10000 n2 25 10000 Var. Contínuas mn 15 1000 2n + mn 25 1200 52 4 Método de decomposição de Benders apli- cado no problema de sequenciamento No Apêndice 6 é discutida a teoria geral do método de decomposição de Benders, para o leitor não familiarizado com essa teoria. Um questionamento possível de ser feito a respeito da decomposição de Benders é: só é benéfica sua utilização quando há uma estrutura conveniente? Possivelmente, não. Também pode ser levado em conta, se há um conjunto de restrições consideradas complicadas e outros conjuntos de restrições que são mais fáceis ao fixar algumas variáveis. Essa será a ideia utilizada para decompor os modelos. Primeiro será aplicado a decomposição de Benders no modelo (3.10)-(3.18), com o objetivo de minimizar o makespan, por ser mais simples e para auxiliar na decomposição do modelo (3.28)-(3.36), com o objetivo JIT. Ao analisar o FSP, o fator que mais interfere na qualidade da solução é a ordem que as tarefas serão processadas. Ao fixar uma determinada ordem, as outras restrições vão basicamente calcular os instantes de conclusão e o valor dos objetivos. Então, no modelo (3.10)-(3.18) as restrições consideradas complicadas serão as restrições (3.11) e (3.12) de designação (e.g. [68]). Todo o restante será o subproblema Φ(x) cujo dual será usado para gerar os cortes de Benders. Considerando o makespan, Φ(x) é dado por Φ(x) = Min{Cnm | (3.13) − (3.17), Chk ≥ 0}. O dual do problema Φ(x), para x̄ satisfazendo (3.11) e (3.12), é apresentado em (4.1)-(4.11). Max (∑n j=1 pj1x̄j1)λ1 + ∑m−1 k=1 (∑n j=1 pj,k+1x̄j1)λ2 k + ∑n−1 k=1(∑n j=1 pj1x̄j,h+1)λ3 h + ∑n h=2 ∑m−1 k=1 (∑n j=1 pj,k+1x̄jh)λ4 hk + ∑n−1 h=1 ∑m k=2( ∑n j=1 pjkx̄jh)λ5 hk (4.1) S.a : λ1 − λ2 1 − λ3 1 ≤ 0 (4.2) λ3 n−1 − λ4 n1 ≤ 0 (4.3) λ2 m−1 − λ5 1m ≤ 0 (4.4) λ4 n,m−1 + λ5 n−1,m ≤ 1 (4.5) λ3 h − λ3 h+1 − λ4 h+1,1 ≤ 0, h = 1 . . . n − 2 (4.6) λ2 k − λ2 k+1 − λ5 1,k+1 ≤ 0, k = 1 . . . m − 2 (4.7) λ4 nk − λ4 n,k+1 + λ5 n−1,k+1 ≤ 0, k = 1 . . . m − 2 (4.8) λ4 h+1,m−1 + λ5 hm − λ5 h+1,m ≤ 0, h = 1 . . . n − 2 (4.9) λ4 h+1,k − λ4 h+1,k+1 + λ5 h,k+1 − λ5 h+1,k+1 ≤ 0, h = 1 . . . n − 2, k = 1 . . . m − 2 (4.10) λ1, λ2 k, λ3 h, λ4 hk, λ5 hk ≥ 0 (4.11) Um ponto interessante para o problema (3.10)-(3.18) é que dado x̄ satisfazendo (3.11) e (3.12), Φ(x̄) sempre terá solução factível. Como o primal de Φ(x̄) sempre possui solução 53 factível, seu dual (DΦ) também sempre terá soluções factíveis e não haverá raios extremos (Definição 19). Dessa forma, o Problema Mestre de Benders (PMB) para o FSP é dado por (4.12)-(4.16), sendo (4.15) os cortes de otimalidade. Min v (4.12) S.a : n∑ j=1 xjh = 1, h = 1 . . . n (4.13) n∑ h=1 xjh = 1, j = 1 . . . n (4.14) (∑n j=1 pj1xj1)λ̄1 + ∑m−1 k=1 (∑n j=1 pj,k+1xj1)λ̄2 k + ∑n−1 k=1(∑n j=1 pj1xj,h+1)λ̄3 h + ∑n h=2 ∑m−1 k=1 (∑n j=1 pj,k+1xjh)λ̄4 hk + ∑n−1 h=1 ∑m k=2( ∑n j=1 pjkxjh)λ̄5 hk ≤ v, ∀λ ∈ DΦ (4.15) xjh ∈ B (4.16) Como o conjunto de pontos extremos costuma ser muito grande, o PMB é resolvido pelo método de planos de corte, ou seja, os cortes de otimalidade são adicionados itera- tivamente (e.g. [69, 70]). Além disso, sendo o PMB um problema de otimização inteira, é necessário utilizar, por exemplo, o método branch-and-bound ou branch-and-cut para gerar uma solução factível para o problema dual. Como esse processo é muito custoso computacionalmente, na literatura foi proposto o método branch-and-Benders-cut como uma alternativa para acelerar a convergência do método (e.g. [71, 72, 73]). Nele os cortes são adicionados cada vez que é encontrada uma solução factível. A ideia de aplicar a decomposição de Benders no problema (3.28)-(3.36) é a mesma. As restrições (3.29) e (3.30) são as consideradas complicadas e todo o restante irá para o subproblema Φ(x) cujo dual será usado para gerar os cortes de Benders. Porém, o que é o dual de um problema multiobjetivo? Esse é um tema que apresenta uma literatura extremamente escassa. No limite das buscas da literatura dessa tese, os trabalhos de Isermann [74] e TenHuisen e Wiecek [9] são as principais referências a respeito da dualidade multiobjetivo. Nesses trabalhos, assim como em outros [75, 76], antes de definir o problema dual é utilizado algum método de escalarização transformando o problema multiobjetivo em uma sequência de subproblemas monoobjetivos. Com isso, é possível utilizar todos os resultados já existentes dos métodos de escalarização e de dualidade monoobjetivo. Aplicando o método ε-restrito aumentado, o modelo escalar resultante que é utilizado para cada iteração está apresentado em (4.17)-(4.26), com Elexmin21 sendo o valor do adiantamento total obtido na resolução do problema lexicográfico com Ord = {2, 1}. 54 Min ρ · n∑ h=1 Eh + n∑ h=1 Th (4.17) s.a. n∑ j=1 xjh = 1, h = 1, ..., n (4.18) n∑ h=1 xjh = 1, j = 1, ..., n (4.19) C11 ≥ n∑ j=1 pj1xj1 (4.20) Ch,k+1 ≥ Chk + n∑ j=1 pj,k+1xjh, h = 1, ..., n, k = 1, ..., m − 1 (4.21) Ch+1,k ≥ Chk + n∑ j=1 pjkxjh, h = 1, ..., n − 1, k = 1, ..., m (4.22) n∑ j=1 (djxjh) − Chm ≤ Eh, h = 1, ..., n (4.23) Chm − n∑ j=1 (djxjh) ≤ Th, h = 1, ..., n (4.24) n∑ h=1 Eh ≤ Elexmin21 − ε (4.25) xjh ∈ {0, 1}, Chk ≥ 0, Eh ≥ 0, Th ≥ 0, j = 1, ..., n, h = 1, ..., n, k = 1, ..., m. (4.26) Para um x̄ que satisfaça (4.18) e (4.19), o dual do subproblema Φ(x̄) é apresentado em (4.27)-(4.39). 55 Max (∑n j=1 pj1x̄j1)λ1 + ∑n h=1 ∑m−1 k=1 (∑n j=1 pj,k+1x̄jh)λ2 hk+∑n−1 h=1 ∑m k=1( ∑n j=1 pjkx̄jh)λ3 hk + ∑n h=1( ∑n j=1 djx̄jh)(λ4 h − λ5 h)+ (Elexmin21 − ε)λ6 (4.27) S.a : λ1 − λ2 11 − λ3 11 ≤ 0 (4.28) λ2 n1 − λ3 n−1,1 ≤ 0 (4.29) λ2 1,m−1 − λ3 1m + λ4 1 − λ5 1 ≤ 0 (4.30) λ2 n,m−1 + λ3 n−1,m + λ4 n − λ5 n ≤ 0 (4.31) λ2 1k − λ2 1,k+1 − λ3 1,k+1 ≤ 0, k = 1 . . . m − 2 (4.32) −λ2 h1 + λ3 h−1,1 − λ3 h1 ≤ 0, h = 2 . . . n − 1 (4.33) λ2 nk − λ2 n,k+1 + λ3 n−1,k+1 ≤ 0, k = 1 . . . m − 2 (4.34) λ2 h,m−1 + λ3 h−1,m − λ3 hm + λ4 h − λ5 h ≤ 0, h = 2 . . . n − 1 (4.35) λ2 hk − λ2 h,k+1 + λ3 h−1,k+1 − λ3 h,k+1 ≤ 0, h = 2 . . . n − 1, k = 1 . . . m − 2 (4.36) λ4 h − λ6 ≤ ρ, h = 1 . . . n (4.37) λ5 h ≤ 1, h = 1 . . . n (4.38) λ1, λ2 hk, λ3 hk, λ4 h, λ5 h, λ6 ≥ 0, h = 1, . . . , n, k = 1, . . . , m. (4.39) As diferenças desse dual para o visto em (4.1)-(4.11) estão, principalmente, na adição das variáveis duais referentes às restrições de cálculo de atraso total e adiantamento total, que aparecem na função objetivo e em restrições referentes às conclusões na última máquina. Além disso, as restrições (4.37), que são referentes às variáveis de adiantamento, nem sempre serão satisfeitas, exatamente por conta do método ε-restrito aumentado cortar o espaço objetivo exigindo valores menores para o adiantamento total, uma informação que o problema mestre não possui. Dessa forma, além dos cortes de otimalidades em (4.43), também haverá cortes de factibilidade em (4.44). O Problema Mestre de Benders biobjetivo (PMBB) é apresentado em (4.40)-(4.45). 56 PMBBε = Min v (4.40) S.a : n∑ j=1 xjh = 1, h = 1 . . . n (4.41) n∑ h=1 xjh = 1, j = 1 . . . n (4.42) (∑n j=1 pj1xj1)λ̄1+ + ∑n h=1 ∑m−1 k=1 (∑n j=1 pj,k+1xjh)λ̄2 hk + ∑n−1 h=1 ∑m k=1( ∑n j=1 pjkxjh)λ̄3 hk+ + ∑n h=1( ∑n j=1 djxjh)(λ̄4 h − λ̄5 h) + (Elexmin21 − ε)λ̄6 ≤ v, ∀λ ∈ Dε Φ (4.43) ∑n j=1 pj1xj1)λ̄1+ + ∑n h=1 ∑m−1 k=1 (∑n j=1 pj,k+1xjh)λ̄2 hk + ∑n−1 h=1 ∑m k=1( ∑n j=1 pjkxjh)λ̄3 hk+ + ∑n h=1( ∑n j=1 djxjh)(λ̄4 h − λ̄5 h) + (Elexmin21 − ε)λ̄6 ≤ 0, ∀λ ∈ Dε Φ (4.44) xjh ∈ B (4.45) A implementação do método branch-and-Benders-cut também pode ser realizada para cada iteração do método multiobjetivo (e.g. [77]). O método de decomposição de Benders clássico proposto em [78] possui limitações nu- méricas e teóricas: dificuldade para o método convergir e necessidade de uma decomposição do problema bem definida (e.g. [68, 79, 80]). Para aprimorar o método, diversas estratégias são utilizadas em diferentes etapas. Em [79] é feita uma revisão sobre a decomposição de Benders com foco nos problemas de otimização combinatória. Os autores dividem o método em quatro partes: como decompor o problema, como resolver o problema mestre e o subproblema, como gerar ou aprimorar soluções para o problema mestre e como gerar os cortes. Para cada uma dessas partes, são apresentados diferentes trabalhos da literatura que fizeram modificações na decomposição de Benders junto com comentários do desempenho e das possíveis barreiras dessas modificações. Para resumir essa revisão, são apresentados breves comentários: • Estratégia de decomposição: afirma-se que a forma de decompor o problema interfere diretamente no desempenho do método. Deixar o problema mestre sem informações do objetivo pode ser prejudicial, assim como, relaxar pouco o problema dificultando sua resolução. O mesmo vale para o subproblema, resumi-lo a um problema de factibilização é ruim por não fornecer limitantes primais; • Resolução dos problemas: aborda-se a importância de controlar a quantidade de cortes que são adicionados ao problema mestre e possíveis estratégias para isso. Além de métodos para resolver os problemas, como exemplo o branch-and-Benders-cut que resolve o problema mestre com uma árvore de busca única; • Gerar e/ou aprimorar soluções: uma das modificações com maiores possibilidades através do uso de heurísticas, metaheurísticas, warm start, técnicas de estabilização, 57 inequações válidas, múltiplos cortes, etc. Uma delas é a resolução em duas estapas proposta em [81]. Na primeira etapa o problema mestre é relaxado, gerando cortes mais rapidamente, e na segunda etapa o domínio das variáveis é retomado; • Gerar cortes: discute-se sobre a força dos cortes e das dificuldades quando o dual do subproblema possui múltiplas soluções. Também, sobre gerar múltiplos cortes com poucas variáveis em comparação a cortes com muitas variáveis. Além dessas discussões, são feitos breves comentários sobre extensões do método de Benders como Logic-based Benders, Generalized Benders e Nested Benders. Na Seção 4.1 apresenta-se um pequeno recorte mais recente sobre o uso de Benders nos problemas de sequenciamento. 4.1 Aplicaçõ