Programação Job-Shop (GA)

O que é programação Job-Shop? Como um GA resolve?

Atribui operações de múltiplos trabalhos a máquinas para minimizar makespan ou atraso. Cada trabalho tem sequência ordenada de operações em máquinas específicas.

JSSP é NP-difícil. GA evolui população de cronogramas candidatos. Cruzamento POX preserva ordem; mutação swap troca posições.

JSSP é crítico em manufatura. Redução de 10-15% no makespan aumenta diretamente a capacidade sem investimento de capital.

Formula: Makespan = max(tempos de conclusão) Atraso = Σ max(0, Conclusão_j − Prazo_j) GA: Inicialização → Avaliação → Seleção → POX → Mutação → Iteração

Exemplo de cálculo

3 trabalhos, 3 máquinas. Trabalho 1: M1(3)→M2(2)→M3(4). Makespan ótimo = 12. GA (população 100, 200 gerações) tipicamente encontra isso ou dentro de 5%.

Quando usar esta calculadora

• Um planejador de produção programando múltiplos trabalhos em uma oficina mecânica com equipamento compartilhado para minimizar o tempo de conclusão
• Um engenheiro de manufatura avaliando o impacto de adicionar uma nova máquina ou mudar sequências de operação no throughput geral
• Um programador em uma gráfica ou fábrica de semicondutores determinando prioridades de trabalho para cumprir datas de entrega do cliente com mínimo atraso
• Um pesquisador de operações comparando programação baseada em GA contra métodos atuais de programação manual ou por regras de prioridade

Erros comuns a evitar

• Definir um tamanho de população muito pequeno para problemas complexos — com 10+ trabalhos e 5+ máquinas, use pelo menos 100-200 indivíduos para manter a diversidade genética e evitar convergência prematura
• Executar poucas gerações e aceitar uma solução subótima — monitore se o fitness ainda está melhorando; se estabiliza, a solução convergiu; se ainda melhora, aumente as gerações
• Ignorar tempos de liberação e datas de entrega quando existem — sem estas restrições, o GA otimiza apenas o makespan, o que pode produzir programações que violam requisitos de tempo do mundo real
• Não executar o GA múltiplas vezes com diferentes sementes aleatórias — o GA é estocástico; uma única execução pode ficar presa em um ótimo local; execute 3-5 vezes e tome o melhor resultado

Como interpretar os resultados

• Se o atraso total é zero, todos os trabalhos são completados antes das suas datas de entrega — a programação é viável e o foco deve mudar para reduzir ainda mais o makespan
• Se o makespan está próximo da soma dos tempos de processamento na máquina gargalo, a programação está perto do ótimo — pouco espaço para melhoria resta
• O gráfico de Gantt revela tempo ocioso nas máquinas: grandes lacunas indicam ineficiência de programação ou restrições de sequenciamento inevitáveis

Normas e referências relacionadas

• Garey, Johnson & Sethi (1976) — estabeleceram a NP-dificuldade da minimização do makespan no job-shop
• Makespan (C_max) e atraso total — as funções objetivo padrão no escalonamento da produção
• Algoritmos genéticos (Holland, 1975) — a classe de metaheurística aplicada aqui para explorar o espaço de escalonamentos

Perguntas frequentes

Como configurar parâmetros do GA?

População 50-200, taxa de mutação 0,05-0,15, 200-500 gerações. Para 10+ trabalhos use população ≥100, gerações ≥300.

Diferença entre otimizar makespan e atraso?

Makespan minimiza tempo total — ideal para maximizar capacidade. Atraso prioriza cumprimento de prazos. Podem conflitar; otimização multi-objetivo pode equilibrar ambos.