💻 computer science

Solving the flexible job-shop scheduling problem based on the hierarchical collaborative evolution multi-objective artificial raindrop algorithm

Este artigo propõe um algoritmo de gota de chuva artificial multiobjetivo coevolutivo hierárquico (HCMOARA) que integra amostragem de hipercubo latino, subpopulações particionadas com estratégias de busca especializadas e um mecanismo de atualização de fator de fluxo adaptativo para otimizar eficazmente o tempo de execução (makespan), o consumo de energia e o custo em problemas de escalonamento de oficina flexível.

Autores originais: Zhibo Zhai, Shaoxuan Wang, Boyang Shi, Liang Ma, Haolong Wang, Jiangchao Zhou

Publicado 2026-08-27

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Zhibo Zhai, Shaoxuan Wang, Boyang Shi, Liang Ma, Haolong Wang, Jiangchao Zhou

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 coração da manufatura moderna, uma tensão silenciosa se desenrola entre velocidade, custo e o meio ambiente. As fábricas devem produzir bens rapidamente para manter a competitividade, mas também enfrentam uma pressão crescente para usar menos energia e gastar menos dinheiro em cada item que produzem. Esse equilíbrio é conhecido como escalonamento. Imagine uma oficina onde dezenas de produtos diferentes precisam ser construídos, e cada produto requer uma série de etapas realizadas em máquinas específicas. Em uma fábrica simples, uma etapa pode ter apenas uma máquina capaz de realizá-la. Mas em uma oficina flexível, uma única etapa pode ser realizada por qualquer uma de várias máquinas diferentes, cada uma com sua própria velocidade, consumo de energia e custo. O desafio é decidir qual máquina faz qual etapa e em que ordem. Se o plano for ruim, a fábrica fica ociosa, a energia é desperdiçada e os custos disparam. Se o plano for bom, a fábrica funciona como uma máquina bem lubrificada, terminando o trabalho mais rápido enquanto gasta menos.

Por décadas, pesquisadores tentaram resolver esse quebra-cabeça usando algoritmos de computador que imitam a natureza, como a maneira como os pássaros voam em bandos ou as formigas encontram comida. Esses métodos são bons em encontrar soluções decentes, mas muitas vezes têm dificuldade quando o problema se torna muito complexo ou quando os objetivos conflitam entre si. Um plano que minimiza o tempo pode consumir eletricidade demais, enquanto um plano que economiza energia pode demorar muito tempo. O objetivo é encontrar um conjunto de compromissos "possíveis de serem os melhores", onde você não consegue melhorar um objetivo sem tornar outro pior. Este é o desafio central abordado por uma equipe de pesquisadores da Universidade de Engenharia de Hebei, que desenvolveu um novo método para navegar nesse cenário difícil.

Os pesquisadores focaram em um tipo específico de problema de escalonamento onde a fábrica deve equilibrar três objetivos conflitantes: terminar todos os trabalhos o mais rápido possível, usar a menor quantidade de energia total e manter o custo total de produção o mais baixo possível. Para lidar com isso, eles criaram um novo algoritmo de computador chamado algoritmo de gota de chuva artificial multiobjetivo coevolutivo hierárquico. O nome vem da maneira como o algoritmo imita o comportamento de gotas de chuva caindo e fluindo através de uma paisagem. Na natureza, as gotas de chuva se reúnem, fluem para riachos e eventualmente se fundem em rios. Os pesquisadores usam essa ideia para simular como as soluções potenciais para o problema de escalonamento se movem e melhoram ao longo do tempo. No entanto, a versão original deste método de "gota de chuva" tinha limitações; às vezes começava com um conjunto pobre de ideias e tinha dificuldade em equilibrar a busca por novas soluções amplas com o refinamento das boas.

Para corrigir esses problemas, a equipe introduziu um sistema de "coevolução hierárquica". Em vez de tratar cada solução potencial da mesma forma, eles as classificaram em três grupos distintos baseados em quão boas e quão únicas eram em relação às outras. O primeiro grupo, os exploradores, consistia nas soluções mais únicas e diversas. Estes receberam uma estratégia projetada para olhar longe e amplamente em busca de novas possibilidades, garantindo que a busca não ficasse presa em uma área pequena. O segundo grupo, os exploradores de nicho (exploiters), continha as soluções mais fortes que eram muito semelhantes entre si. Estes receberam uma estratégia diferente focada em ajuste fino e polimento, cavando profundamente nas áreas mais promissoras para extrair cada bit de melhoria. O terceiro grupo, a equipe de atualização básica, manteve o método constante e original do algoritmo de gota de chuva para manter um fluxo estável de ideias. Ao permitir que esses três grupos evoluíssem juntos, o algoritmo pôde explorar novos territórios enquanto simultaneamente aperfeiçoava as melhores ideias encontradas.

Os pesquisadores testaram este novo método usando um conjunto padrão de dez problemas de escalonamento difíceis, conhecidos como benchmarks de Brandimarte, que variam em tamanho, desde pequenas oficinas até fábricas grandes e complexas. Eles compararam seu novo algoritmo com vários outros métodos populares que imitam a natureza, incluindo aqueles baseados em enxames de partículas e besouros de esterco. Os resultados mostraram que o novo método de gota de chuva superou consistentemente os outros. Em termos do tempo necessário para terminar todos os trabalhos, o novo método encontrou os cronogramas mais rápidos em sete dos dez casos de teste e empatou como o melhor nos três restantes. Também conseguiu manter o consumo de energia e os custos mais baixos do que os outros métodos na maioria dos cenários.

Além de apenas encontrar cronogramas mais rápidos, o novo método produziu uma coleção muito melhor de opções de compensação. Em um problema de múltiplos objetivos, raramente existe uma única resposta "perfeita"; em vez disso, há uma gama de boas opções. Os pesquisadores descobriram que seu algoritmo gerou um conjunto de soluções que eram mais uniformemente distribuídas e cobriam uma área mais ampla de possibilidades do que os outros métodos. Isso significa que um gerente de fábrica teria um cardápio mais rico de escolhas para escolher, quer ele queira priorizar velocidade, economia de energia ou custo. O estudo também incluiu testes para ver quais partes do novo método eram mais importantes. Quando os pesquisadores removeram a maneira especial como o algoritmo iniciava sua busca, ou quando retiraram a capacidade de ajustar como as "gotas de chuva" fluíam, o desempenho caiu. Isso confirmou que cada parte de seu novo design desempenhava um papel necessário no sucesso final.

O estudo conclui que esta abordagem hierárquica oferece uma nova ferramenta poderosa para a manufatura verde. Ao equilibrar a necessidade de explorar novas ideias com a necessidade de refinar as melhores, o algoritmo pode lidar com as demandas complexas e conflitantes da produção moderna. Embora os testes atuais tenham sido realizados em um ambiente simulado onde as máquinas nunca quebram e os trabalhos nunca chegam atrasados, os resultados sugerem um caminho promissor. O método oferece uma maneira de criar cronogramas que não são apenas eficientes, mas também economicamente e ambientalmente sólidos, ajudando as fábricas a avançar em direção a um futuro mais sustentável sem sacrificar velocidade ou lucro.

Resumo Técnico: Resolução do Problema de Escalonamento de Job-Shop Flexível Baseado no Algoritmo de Gota de Chuva Artificial de Evolução Colaborativa Hierárquica

1. Definição do Problema

O artigo aborda o Problema de Escalonamento de Job-Shop Flexível Multiobjetivo (MOFJSP), uma extensão complexa do clássico Problema de Escalonamento de Job-Shop (JSP). No FJSP, diferentemente do JSP onde as máquinas são fixas para operações específicas, cada operação pode ser processada em qualquer máquina de um conjunto de máquinas elegíveis. Essa flexibilidade aumenta a adaptabilidade, mas expande significamente o espaço de soluções e a complexidade computacional.

O estudo formula um modelo de otimização tri-objetivo visando minimizar simultaneamente:

Makespan ( $f_1$ ): O tempo de conclusão máximo de todos os trabalhos.
Consumo Total de Energia ( $f_2$ ): A soma da energia de processamento e da energia ociosa em todas as máquinas.
Custo Total ( $f_3$ ): O custo cumulativo de processamento baseado no tempo de uso das máquinas.

Estes objetivos são mutuamente conflitantes, tornando difícil otimizá-los simultaneamente. O problema está sujeito a restrições padrão, incluindo precedência tecnológica, exclusividade de máquina (uma operação por máquina por vez) e processamento não-preemptivo.

2. Metodologia: Algoritmo de Gota de Chuva Artificial de Evolução Colaborativa Hierárquica (HCMOARA)

Para superar as limitações dos algoritmos de inteligência de enxame existentes — como a distribuição desigual da população inicial, parâmetros de busca fixos e a falta de equilíbrio entre exploração global e explotação local — os autores propõem o HCMOARA. O algoritmo integra os seguintes componentes principais:

Codificação e Decodificação: É utilizado um esquema de codificação contínua de dois segmentos. O primeiro segmento codifica as prioridades de sequenciamento de operações (ordenadas para determinar a ordem), e o segundo codifica a seleção de máquinas (mapeada para índices de máquinas elegíveis). Isso faz a ponte entre algoritmos de otimização contínua e a natureza discreta do FJSP.
Inicialização via Amostragem de Hipercubo Latino (LHS): Em vez de inicialização aleatória, a LHS é empregada para garantir uma distribuição mais uniforme da população inicial no espaço de decisão, reduzindo o agrupamento e melhorando a cobertura.
Estratificação Hierárquica da População: A população é particionada dinamicamente em três subpopulações baseadas em rank não dominado e distância de agrupamento (crowding distance):
1. Subpopulação de Exploração ( $Pop_1$ ): Consiste em indivíduos de Rank 1 com altas distâncias de agrupamento. Estes são guiados por uma estratégia DE-best-2, utilizando um líder do arquivo Pareto externo (selecionado pelo máximo de distância de agrupamento) e mutação diferencial para aumentar a busca global e a diversidade.
2. Subpopulação de Explotação ( $Pop_2$ ): Compreende indivíduos de Rank 1 com baixas distâncias de agrupamento e todos os indivíduos de Rank 2. Este grupo utiliza uma estratégia híbrida SBX–RHC (Crossover Binário Simulado e Hill Climbing Aleatório) para realizar uma busca local refinada e melhorar a convergência próximo a regiões promissoras.
3. Subpopulação de Atualização Básica ( $Pop_3$ ): Contém indivíduos com Rank > 2. Estes mantêm o mecanismo de atualização original do Algoritmo de Gota de Chuva Artificial (ARA), mas utilizam fatores de fluxo adaptativos ( $c_1, c_2$ ) que mudam linearmente ao longo das iterações para equilibrar dinamicamente a experiência individual e social.
Arquivo Pareto Externo: Um arquivo dedicado mantém soluções não dominadas de alta qualidade, garantindo a preservação da fronte Pareto ao longo de todo o processo de otimização.

3. Principais Contribuições

O artigo reivindica as seguintes contribuições para o campo da otimização multiobjetivo e escalonamento:

Inovação Algorítmica: A proposta do HCMOARA, que introduz um framework de evolução colaborativa hierárquica ao Algoritmo de Gota de Chuva Artificial, especificamente adaptado para o MOFJSP.
Diferenciação Estratégica: O design de estratégias evolutivas diferenciadas (DE-best-2 para exploração, SBX-RHC para explotação e fluxo adaptativo para atualizações básicas) atribuídas a subgrupos específicos da população com base em seu status de não dominância.
Melhoria de Inicialização: A aplicação da Amostragem de Hipercubo Latino ao framework ARA para melhorar a uniformidade da distribuição da solução inicial.
Mecanismo Adaptativo: A introdução de fatores de fluxo adaptativos para substituir parâmetros fixos, permitindo o ajuste dinâmico do comportamento de busca durante o processo de otimização.

4. Resultados Experimentais

O algoritmo foi avaliado nas instâncias de benchmark Brandimarte (MK01–MK10) e comparado com outros cinco algoritmos: o MOARA original, NSPSO, NSOOA, NSDBO e NSCOA.

Desempenho de Otimização: O HCMOARA alcançou os melhores resultados de makespan em sete das dez instâncias (MK02, MK03, MK05, MK06, MK07, MK09, MK10) e empatou como o melhor em outras duas. Também demonstrou desempenho superior na minimização do consumo total de energia e do custo total na maioria das instâncias.
Qualidade da Fronte Pareto:
- Distância Generacional Invertida (IGD): O HCMOARA alcançou os menores valores de IGD em sete instâncias, incluindo valores zero em MK02, MK03, MK06 e MK09, indicando que seus conjuntos de soluções cobrem de perto as frentes Pareto de referência.
- Hipervolume (HV): O HCMOARA obteve o maior HV em nove das dez instâncias, demonstrando cobertura e distribuição superiores no espaço de objetivos.
Convergência: As curvas de convergência mostraram que o HCMOARA convergiu mais rápido e evitou o estancamento melhor do que os algoritmos de comparação, particularmente em instâncias de larga escala.
Estudo de Ablação: Experimentos removendo componentes específicos (LHS, fluxo adaptativo, DE-best-2, SBX-RHC) confirmaram que cada estratégia contribui positivamente para o desempenho geral. O algoritmo completo superou consistentemente suas variantes abladas em termos de IGD, HV e valores de objetivos.

5. Significância e Escopo

Os autores afirmam que o HCMOARA é uma abordagem eficaz para resolver problemas de escalonamento de job-shop flexível multiobjetivo, particularmente no contexto da manufatura verde, onde energia e custo são críticos juntamente com a eficiência. O estudo destaca que a estratégia de evolução colaborativa hierárquica equilibra efetivamente a exploração global e a explotação local, abordando problemas comuns como a convergência prematura e a distribuição desigual de soluções.

O artigo nota explicitamente suas limitações: o modelo atual opera em um ambiente de escalonamento estático, excluindo fatores dinâmicos como quebras de máquinas, chegada de novos trabalhos ou flutuações estocásticas no tempo de processamento. Os autores sugerem que trabalhos futuros devem incorporar esses elementos dinâmicos para aumentar a aplicabilidade em ambientes de produção do mundo real.