Agendamento de oficina genética

O escalonamento de job shop é um problema desafiador para programação matemática. No entanto, quando aplicável, o impacto operacional pode ser grande. Na postagem do blog de hoje, contribuirei para este tópico com um exemplo técnico que cobre o agendamento de tarefas genéticas.

Um problema simples de programação de tarefas de máquinas de oficina

O exemplo que sugiro compreende 3 máquinas (M1, M2 e M3) e 5 tarefas (T1, T2, T3, T4 e T5). Os trabalhos devem ser processados em um job shop. Cada tarefa pode ser processada em qualquer máquina, mas existem certas restrições que limitam a sequência possível de tarefas em cada máquina.

Por exemplo, as restrições podem ser as seguintes:

T1 deve ser processado antes de T2 em M1
T4 deve ser processado antes de T5 em M2
T2 e T3 não podem ser processados na mesma máquina

Agora quero encontrar um agendamento de tarefas em cada máquina que minimize o tempo total de processamento para todas as tarefas.

Agendamento de tarefas de job shop com algoritmos genéticos

Para resolver esse problema usando um algoritmo genético, represento um cronograma como uma sequência de números inteiros. Cada número inteiro representa a tarefa a ser processada a seguir. Por exemplo, uma programação [1, 2, 3, 4, 5] significa que processamos a tarefa 1 na máquina 1, seguida pela tarefa 2 na máquina 2, seguida pela tarefa 3 na máquina 3 e assim por diante.

Podemos usar uma função de aptidão simples que calcula o tempo total de processamento para um determinado cronograma, levando em consideração as restrições. Por exemplo, podemos calcular o tempo de processamento da seguinte forma:

Para cada máquina, calcule o tempo de processamento como a soma dos tempos de processamento de todas as tarefas atribuídas a essa máquina.
Se houver alguma violação de restrição (por exemplo, se T2 e T3 forem atribuídos à mesma máquina), adicione uma penalidade ao tempo de processamento.
A aptidão de um escalonamento é o negativo do tempo de processamento.

Podemos então usar um algoritmo genético para gerar e evoluir cronogramas até encontrarmos um bom.

Exemplo de algoritmo de agendamento genético

Aqui está um exemplo de como o algoritmo pode funcionar:

Gere uma população inicial de cronogramas, cada um consistindo em uma sequência aleatória de tarefas atribuídas às máquinas.
Calcule a aptidão de cada esquema usando a função de aptidão.
Selecione um subconjunto da população para reproduzir a próxima geração de esquemas, usando um método de seleção como a seleção por torneio.
Gere novos cronogramas usando operadores de cruzamento e mutação.
Substitua a população antiga pela nova população e repita as etapas 2 a 4 por um certo número de gerações.
O melhor escalonamento encontrado é aquele com maior valor de fitness.

Os problemas de agendamento de job shop são conhecidos por serem NP-difíceis, o que significa que encontrar a solução ótima é computacionalmente intratável para grandes instâncias de problemas. Como resultado, os algoritmos genéticos podem levar muito tempo para convergir ou podem não ser capazes de encontrar a solução ótima.

Considerações finais e conteúdo de agendamento de job shop relacionado

O agendamento de job shop é um assunto desafiador. A programação matemática e, neste caso, os algoritmos genéticos, podem ser eficazes em alguns casos. Em outros casos, os problemas podem ser complexos demais para serem resolvidos analiticamente com um esforço razoável. Se este for o caso, a simulação de eventos discretos pode ajudar a superar alguns dos desafios da aplicação de programação matemática. A seguinte postagem no blog do SCDA descreve os desafios do agendamento de job shop:

Link : Desafios de agendamento de job shop

Você pode ler mais sobre simulação, especialmente simulação de eventos distintos, nas seguintes publicações do SCDA. A modelagem de simulação pode implementar soluções de agendamento que podem superar os desafios da programação matemática que a tornam imprópria para aplicação em problemas do mundo real.