💻 ciência da computação

A Block-Guided Artificial Bee Colony Algorithm for Distributed Assembly Flowshop Scheduling with Sequence-Dependent Setup Times

Este artigo propõe um algoritmo de Colônia de Abelhas Artificial Guiada por Blocos (BG-ABC) que integra um mecanismo de compressão de blocos consciente de ociosidade, uma seleção de operador adaptativa por Janela Deslizante Upper Confidence Bound 1 (SW-UCB1) e uma busca local focada em tarefas críticas para minimizar efetivamente o makespan para o Problema de Escalonamento de Fluxo de Permutação de Montagem Distribuída com Tempos de Preparação Dependentes de Sequência (DAPFSP-SDST).

Autores originais: Ji-Feng Xu, Hong-Bo Song

Publicado 2026-10-30

📖 4 min de leitura☕ Leitura rápida

CC BY 4.0

Autores originais: Ji-Feng Xu, Hong-Bo Song

Artigo original sob licença CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

No vasto e interconectado mundo da manufatura moderna, a jornada de um produto muitas vezes não começa em uma única fábrica, mas através de uma rede de instalações especializadas espalhadas pelo globo. Imagine um carro sendo construído onde os motores são feitos em um país, a eletrônica em outro e a montagem final acontece em um terceiro. Essa abordagem distribuída oferece flexibilidade e eficiência, mas cria um enorme quebra-cabeça logístico. O desafio reside em decidir qual fábrica deve construir qual peça, em que ordem essas peças devem ser processadas e, finalmente, como trazê-las todas para a montagem. Complicando ainda mais essa realidade é o fato de que as máquinas nem sempre estão prontas para trabalhar imediatamente; elas requerem tempo para limpar, trocar ferramentas ou ajustar dispositivos entre as tarefas. O tempo necessário para essa preparação muitas vezes depende inteiramente de qual trabalho acabou de ser finalizado e qual será o próximo. Essa natureza "dependente de sequência" significa que uma pequena mudança na ordem de trabalho pode repercutir por todo o sistema, alterando drasticamente quanto tempo leva para terminar tudo. Resolver esse quebra-cabeça é crítico para indústrias que vão desde a automotiva até a de móveis, pois encontrar o cronograma mais eficiente impacta diretamente os custos, os prazos de entrega e a capacidade de atender à demanda dos clientes.

Os pesquisadores Ji-Feng Xu e Hong-Bo Song enfrentaram esse complexo problema de agendamento ao desenvolver um novo método computacional que imita o comportamento de forrageamento das abelhas melíferas para encontrar os melhores cronogramas de produção possíveis. A abordagem deles, projetada especificamente para cenários onde os tempos de configuração variam com base na ordem dos trabalhos, foca em minimizar o tempo total necessário para completar todos os produtos, conhecido como makespan. A equipe observou que, nos cronogramas mais eficientes, certos pares de produtos aparecem consistentemente um ao lado do outro porque exigem a menor quantidade de tempo de configuração e não deixam tempo de espera ociosa para a máquina de montagem. Para aproveitar isso, eles criaram um sistema que identifica esses pares ideais e os trava juntos em "blocos" fixos, tratando-os como unidades únicas durante a busca por uma solução. Essa estratégia reduz efetivamente o enorme número de cronogramas possíveis para um conjunto muito menor e mais gerenciável, permitindo que o computador foque sua energia nas arranjos mais promissores em vez de desperdiçar tempo com combinações improváveis.

No entanto, travar esses blocos juntos carrega um risco: o algoritmo pode ficar preso em um ótimo local, perdendo uma solução melhor que exija a separação de um bloco. Para evitar isso, os pesquisadores incorporaram um sistema de seleção dinâmica na fase de "abelha empregada" do algoritmo. Esse sistema atua como um gerente inteligente que observa quais estratégias de busca estão funcionando melhor no momento atual e desloca sua atenção de acordo, em vez de se manter fiel a um plano rígido. Quando o algoritmo fica travado, um mecanismo de "abelha batedora" intervém para dissolver os blocos travados e reconstruir o cronograma do zero, garantindo que a busca continue explorando novas possibilidades. Além disso, os pesquisadores perceberam que nem toda parte do cronograma precisa do mesmo nível de atenção. Eles direcionaram o algoritmo para focar seus esforços de busca detalhada apenas na sequência específica de trabalhos que estão causando gargalos, ignorando partes do cronograma que já estão funcionando sem problemas. Essa abordagem direcionada economiza poder computacional significativo, permitindo que o sistema avalie mais soluções potenciais no mesmo intervalo de tempo.

A equipe testou seu novo método, que chamam de Algoritmo de Colônia de Abelhas Artificiais Guiado por Blocos (Block-Guided Artificial Bee Colony algorithm), contra uma ampla gama de problemas de referência padrão usados por pesquisadores na área. Esses testes envolveram milhares de cenários diferentes com variados números de fábricas, máquinas e produtos. Os resultados mostraram que o método deles superou consistentemente os algoritmos de ponta existentes, encontrando cronogramas significativamente mais curtos em duração. Ao combinar a eficiência do agrupamento de pares ideais de produtos com a adaptabilidade de uma busca inspirada em abelhas, os pesquisadores demonstraram uma maneira robusta de lidar com a intrincada coordenação necessária nas cadeias de suprimentos modernas. O trabalho deles sugere que, ao compreender os padrões estruturais específicos desses problemas de agendamento, é possível projetar ferramentas inteligentes que façam as redes de manufatura global complexas funcionarem de forma mais fluida e eficiente.

Resumo Técnico: Um Algoritmo de Colônia de Abelhas Artificial Guiado por Blocos para Escalonamento de Fluxo de Montagem Distribuído com Tempos de Preparação Dependentes de Sequência

Definição do Problema
Este artigo aborda o Problema de Escalonamento de Fluxo de Permutação de Montagem Distribuída com Tempos de Preparação Dependentes de Sequência (DAPFSP-SDST). O problema modela uma cadeia de suprimentos de múltiplos estágios onde $n$ tarefas são processadas em $f$ fábricas idênticas, cada uma contendo $m$ máquinas em uma configuração de fluxo de produção (flowshop). Após a conclusão, as tarefas são transportadas para uma instalação centralizada para serem montadas em $d$ produtos em uma única máquina de montagem. O objetivo é minimizar o tempo de execução total (makespan, $C_{max}$ ).

Uma complexidade crítica deste problema é a inclusão de Tempos de Preparação Dependentes de Sequência (SDST) tanto nos estágios de manufatura quanto no de montagem. No estágio de manufatura, os tempos de preparação dependem de tarefas consecutivas dentro de uma fábrica; no estágio de montagem, eles dependem de produtos consecutivos. O problema é identificado como fortemente NP-difícil, exigindo a otimização simultânea da atribuição de tarefas às fábricas, do sequenciamento de tarefas dentro das fábricas e do sequenciamento de montagem dos produtos.

Metodologia: O Algoritmo BG-ABC
Os autores propõem um algoritmo de Colônia de Abelhas Artificial Guiado por Blocos (BG-ABC). O design fundamenta-se na observação de que minimizar o makespan é equivalente a minimizar a soma do tempo total de preparação de montagem (TSTA) e o tempo total de ociosidade de montagem (TITA). Soluções de alta qualidade frequentemente exibem pares de produtos adjacentes que alcançam simultaneamente o SDST mínimo e tempo de ociosidade de montagem zero.

O algoritmo integra quatro mecanismos específicos à estrutura padrão do ABC:

Compressão de Blocos Consciente de Ociosidade:
O algoritmo identifica "blocos compressíveis", definidos como pares de produtos consecutivos $(\pi_l, \pi_{l+1})$ onde $\pi_{l+1}$ é o sucessor de SDST-mínimo de $\pi_l$ e o tempo de ociosidade entre eles é zero. Esses pares são travados em blocos atômicos. O espaço de busca é reduzido de permutações de produtos individuais para permutações desses blocos, diminuindo significativamente a dimensionalidade do espaço de busca enquanto preserva padrões estruturais promissores.
Seleção Adaptativa de Operadores (SW-UCB1):
Na fase de abelhas operárias empregada, o algoritmo opera sobre a sequência de blocos comprimida usando três operadores de vizinhança: Troca (Swap), Inserção (Insertion) e Inversão (Inversion). Para selecionar dinamicamente o operador mais eficaz conforme a pesquisa progride, é utilizado um esquema de Janela Deslizante de Limite Superior de Confiança 1 (SW-UCB1). Este mecanismo monitora as recompensas recentes de cada operador dentro de uma janela deslizante, permitindo que o algoritmo adapte sua estratégia de busca sem a complexa sintonia de parâmetros exigida pelo Q-learning.
Busca Local de Subsequência de Tarefas Críticas (CJS):
A busca local é restrita à "Subsequência de Tarefas Críticas" (CJS). Com base na observação de que os tempos de ociosidade para produtos que aparecem após o último tempo de ociosidade positivo não podem ser reduzidos além disso, o algoritmo concentra o esforço computacional apenas no prefixo da sequência de produtos (a Sequência de Produtos Crítica) que contém tempos de ociosidade positivos. Uma estratégia de avaliação de dois níveis é usada: uma avaliação parcial rápida dos primeiros $K$ produtos filtra candidatos antes que uma avaliação completa do makespan seja acionada, reduzindo a sobrecarga computacional.
Refinamento-e-Reconstrução (Fase da Abelha Exploradora/Scout):
Para neutralizar o risco de convergência prematura causado pela compressão de blocos, um mecanismo de abelha exploradora é implementado. Se um indivíduo estagnar além de um limite $\theta$ , o algoritmo primeiro tenta um refinamento direcionado usando o declive de vizinhança (neighborhood descent) em produtos não críticos e na CJS. Se nenhum melhoria for encontrada, o algoritmo realiza um reinício estrutural: ele dissolve os blocos travados, permuta aleatoriamente os produtos restantes e embaralha as ordens de tarefas dentro dos produtos, restaurando assim a diversidade estrutural e escapando de ótimos locais.

Principais Contribuições
O artigo reivindica quatro contribuições primárias:

Insight Estrutural: A proposta de um mecanismo de compressão de blocos consciente de ociosidade que trava pares de produtos de SDST-mínimo e ociosidade zero em blocos atômicos, reduzindo efetivamente a dimensionalidade do espaço de busca.
Seleção Adaptativa: A integração do esquema SW-UCB1 para selecionar dinamicamente operadores de vizinhança com base no desempenho recente, aumentando a adaptabilidade da busca.
Exploração Focada: A restrição da busca local à Subsequência de Tarefas Críticas combinada com uma estratégia de avaliação de dois níveis, que concentra os recursos computacionais nas regiões de gargalo do cronograma.
Gestão de Estagnação: O design de um mecanismo de refinamento-e-reconstrução na fase da abelha exploradora que visa especificamente os riscos de estagnação introduzidos pela compressão de blocos.

Resultados Experimentais
O algoritmo foi avaliado em 540 instâncias de referência derivadas do conjunto de dados DAPFSP-SDST de Hatami et al. [7], cobrindo várias escalas de problema ( $n \in \{100, 200\}$ , $m \in \{5, 10, 20\}$ , $f \in \{4, 6, 8\}$ , $d \in \{30, 40, 50\}$ ).

Comparação: O BG-ABC foi comparado contra quatro algoritmos de ponta: Iterated Greedy (IG), Genetic Programming Hyper-Heuristic (GP-HH), Novel Biogeography-Based Optimization (NBBO) e Two-Stage Heuristic Algorithm (TSHA).
Desempenho: O BG-ABC alcançou o menor Desvio Percentual Relativo Médio (ARPD) de -1,95%, superando significativamente o TSHA (-1,28%), o NBBO (-1,32%), o GP-HH (-0,49%) e o IG (0,81%). A análise estatística usando o teste de Friedman e o teste post-hoc de Bonferroni-Dunn confirmou que a superioridade do BG-ABC é estatisticamente significativa em ambos os níveis de confiança de 95% e 99%.
Estudo de Ablação: Variantes do BG-ABC carecendo de componentes específicos (compressão de blocos, seleção adaptativa, busca CJS ou reconstrução guiada) foram testadas. O BG-ABC completo superou significativamente todas as variantes, confirmando que cada componente é não redundante e contribui para o desempenho geral.

Significância e Alegações
O artigo afirma que o algoritmo BG-ABC fornece uma ferramenta de otimização inteligente prática e robusta para ambientes de cadeia de suprimentos de múltiplos estágios. Sua significância reside no sucesso ao incorporar insights estruturais específicos do problema (especificamente a relação entre SDST, tempo de ociosidade e formação de blocos) em uma meta-heurística de população. Ao equilibrar a profundidade da busca e o custo computacional através da compressão de blocos e da busca local focada, o algoritmo supera as limitações de heurísticas de descida única (como o TSHA) e meta-heurísticas genéricas que falham em explorar totalmente as propriedades específicas do DAPFSP-SDST. Os autores concluem que o método proposto melhora efetivamente a eficiência operacional e a tomada de decisão em sistemas de montagem distribuída.

Mais como este