Problemas de Agendamento

Os problemas de agendamento constituem uma classe essencial de desafios em otimização e computação, especialmente em sistemas operacionais, processamento paralelo e aplicações em tempo real. Apesar de sua ampla utilização prática, diversas variantes permanecem computacionalmente intratáveis, mesmo sob fortes restrições estruturais. Este artigo investiga a NP-completude de duas versões específicas do problema de escalonamento: o agendamento com tempo de execução unitário e o agendamento com dois processadores em tarefas de duração igual a uma ou duas unidades. A fundamentação teórica baseia-se em reduções polinomiais clássicas, em particular a partir do problema 3-SAT, que permite codificar atribuições lógicas diretamente nas restrições de precedência e capacidade dos processadores. Além disso, transformações adicionais entre versões restritas do problema são utilizadas para preservar a equivalência estrutural das soluções. As contribuições incluem uma reconstrução didática das provas originais, a análise dos mecanismos que geram dureza computacional e uma discussão sobre as implicações práticas desses resultados em sistemas reais de escalonamento. Os resultados apresentados na literatura reforçam que mesmo cenários aparentemente simples apresentam comportamento NP-completo.