Um Algoritmo Memético Baseado em Algoritmo de Estimação de Distribuição para o Problema de Escalonamento de Fluxo de Montagem em Permutação Distribuída

Neste artigo, propõe-se um algoritmo memético (MA) baseado em um algoritmo de estimação de distribuição (EDA) para resolver o problema de escalonamento de fluxo de montagem em permutação distribuída (DAPFSP) com o objetivo de minimizar o tempo máximo de conclusão. Um novo método baseado em bi-vetores é proposto para representar uma solução para o DAPFSP. Na fase de busca do MA baseado em EDA (EDAMA), a exploração baseada em EDA e a exploração baseada em busca local são incorporadas dentro da estrutura do MA. Para a fase de exploração baseada em EDA, um modelo de probabilidade é construído para descrever a distribuição de probabilidade de soluções superiores. Além disso, um novo mecanismo de amostragem seletiva e aprimoradora é proposto para gerar novas soluções por amostragem do modelo de probabilidade. Para a fase de exploração baseada em busca local, o caminho crítico do DAPFSP é analisado para evitar operadores de busca inválidos. Com base na análise, uma estratégia de busca local baseada em caminho crítico é proposta para melhorar ainda mais as soluções potenciais obtidas na fase de busca baseada em EDA. Além disso, o efeito da configuração de parâmetros é investigado com base no método de Taguchi de desenho experimental. Valores de parâmetros adequados são sugeridos para instâncias com diferentes escalas. Por fim, simulações numéricas com base em 1710 instâncias de referência são realizadas. Os resultados experimentais e as comparações com algoritmos existentes mostram a eficácia do EDAMA na resolução do DAPFSP. Além disso, as melhores soluções conhecidas de 181 instâncias são atualizadas pelo EDAMA.