Joint Planning of Assembly Sequence Planning and Assembly Line Balancing Based on Improved Artificial Fish Swarm Algorithm

Resumo Técnico: Planejamento Conjunto de Sequenciamento de Montagem e Balanceamento de Linha de Montagem Baseado no Algoritmo de Enxame de Peixes Artificial Melhorado

Definição do Problema
O artigo aborda o desafio complexo de otimizar simultaneamente o Planejamento de Sequência de Montagem (ASP) e o Balanceamento de Linha de Montagem (ALB). Estes dois problemas são inerentemente acoplados; o ASP determina a ordem ideal de montagem dos componentes para minimizar custos, enquanto o ALB atribui essas tarefas a estações de trabalho para minimizar o tempo ocioso e balancear a linha. Ambos são classificados como problemas de Complexidade Polinomial Não-determinística (NP-hard) com complexidade polinomial. Os autores observam que a otimização desses problemas separadamente frequentemente leva a um desempenho global subótimo do sistema. Além disso, os métodos existentes para ASP frequentemente sofrem de "explosão combinatória" ao utilizar busca em grafos, e os métodos tradicionais de geração de matrizes podem ser demorados e ineficientes para produtos complexos. Adicionalmente, muitos estudos de ALB falham em considerar as mudanças dinâmicas de ferramentas de montagem e direções inerentes ao ASP, levando a resultados de balanceamento que podem ser impraticáveis em processos de montagem reais.

Metodologia
A abordagem proposta integra o ASP e o ALB em um framework de otimização multiobjetivo unificado usando um Algoritmo de Enxame de Peixes Artificial Híbrido (HAFSA). A metodologia é estruturada em três fases principais:

1. Modelagem de ASP via BOM e Matriz de Restrições:

   • Em vez de depender apenas de grafos AND/OR que causam explosão combinatória, os autores constroem uma matriz de restrição de montagem modular baseada no diagrama de hierarquia da Lista de Materiais (BOM).
   • A matriz de restrição de montagem ($E(G)$) é definida usando um grafo direcionado onde os elementos representam partes e os valores indicam prioridade e relações de conexão (por exemplo, $1$ para conexão direta antes, $-1$ para depois, $9$ para não direta antes, etc.).
   • Particionamento de Submontagem: Um algoritmo analisa a hierarquia da BOM para determinar a independência das submontagens. Ele verifica iterativamente os valores das colunas na matriz de restrição; se um grupo de partes mostra relações consistentes não positivas ou não negativas com partes externas, elas são identificadas como submontagens independentes. Caso contrário, o algoritmo remove linhas específicas para criar módulos independentes viáveis.
   • Planejamento Interno: Dentro de cada submontagem identificada, um algoritmo específico de troca e solidificação é usado para gerar sequências de montagem internas viáveis com base nos valores da matriz de restrição.

2. Modelo de Otimização Multiobjetivo:
   O modelo integrado busca minimizar três funções objetivo simultaneamente:

   • Balanceamento de Tempo da Estação de Trabalho: Minimizar a variância entre o ritmo de produção ($T_c$) e os tempos individuais das estações de trabalho ($T_m$).
   • Custos de Troca: Minimizar o número total de trocas de ferramentas de montagem e mudanças de direção de montagem entre tarefas consecutivas.
   • Tempo Máximo da Estação de Trabalho: Minimizar o tempo de ciclo (o tempo máximo entre todas as estações de trabalho).

3. Algoritmo de Enxame de Peixes Artificial Híbrido (HAFSA):
   Para resolver este problema multiobjetivo, os autores propõem um HAFSA que combina o Algoritmo de Enxame de Peixes Artificial (AFSA) com a Otimização por Enxame de Partículas (PSO) e conceitos de Pareto-otimalidade.

   • Codificação/Decodificação: As tarefas de montagem são codificadas com base em pesos de prioridade dentro das submontagens. A decodificação atribui tarefas às estações de trabalho sequencialmente, abrindo novas estações apenas quando a restrição de tempo de ciclo é excedida.
   • Conjunto de Soluções de Pareto: Um repositório externo armazena soluções não dominadas. Um mecanismo de distância de agrupamento (crowding distance) é usado para manter a diversidade e gerenciar o tamanho do repositório.
   • Melhorias no Algoritmo:
     • Lógica Comportamental: O algoritmo segue uma ordem de busca serial: perseguição de cauda, busca de alimento, agrupamento e comportamento aleatório.
     • Integração com PSO: Para evitar que o algoritmo caia em ótimos locais (uma fraqueza conhecida do AFSA padrão), operações de PSO são introduzidas. Isso inclui o uso de um critério de Metropolis (conceito de recozimento simulado) para aceitar soluções que deterioram com uma certa probabilidade, permitindo que a busca escape de armadilhas locais.
     • Inércia Dinâmica: O "campo visual" (alcance de busca) dos peixes artificiais é ajustado dinamicamente usando um peso de inércia ($\omega$) inspirado no PSO, começando com um campo grande para exploração global e estreitando para convergência local.

Principais Contribuições

• Framework Integrado: O artigo propõe um método para planejar conjuntamente o ASP e o ALB em vez de tratá-los sequencialmente, reconhecendo sua interdependência.
• Identificação de Submontagem Baseada em Matriz: Uma abordagem inovadora usando a hierarquia da BOM e a matriz de restrição de montagem para identificar automaticamente submontagens independentes, reduzindo o espaço de busca e evitando a explosão combinatória.
• Algoritmo HAFSA: O desenvolvimento de um Algoritmo de Enxame de Peixes Artificial Híbrido baseado em Pareto que melhora o AFSA padrão ao incorporar operações de PSO e princípios de recozimento simulado para aumentar as capacidades de busca global e evitar ótimos locais.
• Tratamento Multiobjetivo: A inclusão explícita de trocas de ferramentas e mudanças de direção como objetivos de otimização ao lado do tradicional balanceamento de tempo.

Resultos
O método proposto foi validado usando um estudo de caso de um produto específico com 21 tarefas de montagem. O HAFSA (rotulado como AFSA&PSO) foi comparado contra um algoritmo de Otimização por Enxame de Partículas (PSO) padrão e um Algoritmo de Enxame de Peixes Artificial (AFSA) padrão.

• Balanceamento de Estação de Trabalho: Todos os três algoritmos atingiram o mesmo tempo máximo de operação da estação de trabalho de 31 minutos. No entanto, o valor de balanceamento entre estações para o HAFSA foi de 0,69, o que foi superior ao resultado do PSO (0,75) e igual ao AFSA padrão (0,69).
• Eficiência de Troca: O HAFSA alcançou um total de 22 mudanças (ferramenta + direção). Isso foi igual ao resultado do PSO (22), mas significativamente melhor que o AFSA padrão, que resultou em 24 mudanças.
• Conclusão dos Dados: O HAFSA demonstrou a capacidade de encontrar uma solução de Pareto-ótima que equilibra os tempos das estações de forma eficaz, enquanto minimiza o número total de trocas operacionais, superando o AFSA padrão na redução de trocas e igualando ou excedendo o PSO nas métricas de balanceamento.

Significância e Alegações
O artigo afirma que sua principal significância reside na melhoria da eficiência e viabilidade do planejamento conjunto de ASP e ALB. Ao utilizar a hierarquia da BOM para o pré-processamento das submontagens, o método torna o espaço de busca mais direcionado, melhorando assim a eficiência da solução e evitando a geração de um grande número de soluções inviáveis.

Os autores afirmam que o HAFSA proposto é mais eficaz do que os algoritmos tradicionais AFSA e PSO para este problema multiobjetivo específico. A integração de operações de PSO no comportamento do enxame de peixes permite que o algoritmo escape melhor de ótimos locais, resultando em soluções de Pareto de maior qualidade. O estudo conclui que esta abordagem integrada fornece um método de planejamento mais razoável e eficiente para linhas de montagem de produtos complexos, particularmente onde as trocas de ferramentas e direções são fatores de custo críticos.