Programação de máquinas paralelas
Alocar trabalhos em múltiplas máquinas paralelas. Aloca trabalhos em máquinas paralelas idênticas usando regras de despacho (SPT, LPT, EDD, FCFS, CR, WSPT).…
Aloca trabalhos em máquinas paralelas idênticas usando regras de despacho (SPT, LPT, EDD, FCFS, CR, WSPT). Visualiza o cronograma com gráfico de Gantt e compara a utilização das máquinas.
O que é programação de máquinas paralelas?
O sequenciamento em máquinas paralelas aloca um conjunto de tarefas em várias máquinas idênticas para otimizar objetivos como minimizar o makespan (tempo total de conclusão) ou o atraso total. Ele estende o sequenciamento de máquina única para ambientes com múltiplas máquinas, comuns na manufatura, na computação e na logística.
A regra LPT (maior tempo de processamento primeiro) é uma heurística consagrada para minimizar o makespan em máquinas paralelas: ordene as tarefas por tempo de processamento decrescente e atribua cada tarefa à máquina que ficar disponível mais cedo. A LPT garante um makespan dentro de 4/3 do ótimo para máquinas idênticas. Outras regras (SPT, EDD, WSPT) otimizam objetivos diferentes.
A utilização das máquinas — a fração do tempo total em que cada máquina está ocupada — revela a qualidade do balanceamento de carga. Uma utilização igual entre as máquinas indica bom equilíbrio. A visualização em gráfico de Gantt mostra a linha do tempo da programação de cada máquina, tornando imediatamente visíveis o tempo ocioso e o desbalanceamento de carga.
Formula: Makespan = max(Completion Time of all machines) Utilization = Σ Processing Time / (Makespan x m) Tardiness = max(0, Completion - Due Date) LPT: Assign longest job to earliest available machine SPT: Assign shortest job to earliest available machine
Exemplo de cálculo
4 tarefas (p=8,6,5,3) em 2 máquinas usando a LPT. Atribua Tarefa1(8)→M1, Tarefa2(6)→M2, Tarefa3(5)→M2 (carga 6→11), Tarefa4(3)→M1 (carga 8→11). Makespan = 11. Utilização: M1=11/11=100%, M2=11/11=100%. Perfeitamente balanceado. Sem a LPT (por ordem de chegada): o makespan poderia chegar a 14, com balanceamento ruim.
Quando usar esta calculadora
- Ao programar um lote de trabalhos em múltiplas máquinas idênticas para minimizar makespan ou atraso total
- Durante planeamento de capacidade para avaliar se adicionar uma máquina reduziria significativamente o makespan
- Ao comparar regras de despacho para o seu mix específico de trabalhos
- Após uma avaria para reprogramar rapidamente os trabalhos restantes
- Ao balancear carga entre máquinas para minimizar tempo ocioso
Erros comuns a evitar
- Usar SPT para minimizar makespan — use LPT que atribui os trabalhos mais longos primeiro
- Assumir que mais máquinas sempre reduzem makespan proporcionalmente — retornos decrescentes
- Não considerar release times quando trabalhos chegam em momentos diferentes
- Ignorar o balanço de utilização de máquinas — um programa ótimo pode deixar máquinas ociosas
Como interpretar os resultados
- Utilização igual em todas as máquinas (>90%) — carga bem balanceada; regra funciona eficientemente
- Uma máquina a 100% enquanto outras significativamente abaixo — essa máquina é o gargalo
- Total tardiness = 0 — todos os trabalhos terminam antes das datas de entrega
- Alta tardiness com muitos trabalhos atrasados — carga excede capacidade; considere horas extra ou mais máquinas
- LPT e SPT dão makespan similar — tempos de processamento são relativamente uniformes
Normas e referências relacionadas
- APICS CPIM Body of Knowledge — Cobre conceitos de programação de máquinas paralelas
- ISA-95 (IEC 62264) — Norma que define níveis de programação incluindo programação detalhada ao nível da máquina
Perguntas frequentes
Qual regra de despacho minimiza o makespan em máquinas paralelas?
A LPT (maior tempo de processamento primeiro) é a melhor heurística para minimizar o makespan. Ao atribuir primeiro as tarefas mais longas, ela evita que tarefas grandes criem gargalos no final. A LPT garante uma solução dentro de 4/3 - 1/(3m) do ótimo, em que m é o número de máquinas. Para 2 máquinas, isso corresponde a 7/6 (≈17%) do ótimo.
Como lidar com tarefas que têm tempos de liberação ou datas de entrega diferentes?
Com tempos de liberação, as tarefas só podem começar após o respectivo instante de liberação — use um despacho dinâmico que reavalie as prioridades à medida que cada máquina fica disponível. Com datas de entrega, as regras EDD ou CR ajudam a minimizar o atraso. Para problemas complexos com ambas as restrições, simule várias regras e compare as métricas de desempenho. A melhor regra depende do conjunto específico de tarefas e do objetivo.