Algoritmos Polinomiais Exatos ou Aproximativos para Certos Problemas em Sheduling

O presente trabalho examina alguns problemas da Teoria de Scheduling, propondo algoritmos polinomiais para minimização do tempo máximo de processamento e da soma dos tempos de processamento, tanto para um problema de máquinas paralelas, com máquinas uniformes e tempos unitários, como para uma particularização do problema de Flow-shop Scheduling, abordando tanto o caso de armazenamento ilimitado, como caso de armazenamento zero (no wait).

Propomos, ainda, um algoritmo aproximativo para a minimização do tempo máximo de processamento, em um problema especial de duas máquinas não relacionadas, com os tempos de processamento sujeitos à restrição qi = api + B, com qualidade melhor que a existente.