ANÁLISE DE UM ALGORITMO APROXIMATIVO PARA O PROBLEMA DE ESCALONAMENTO DE TAREFAS COM RESTRIÇÕES DE PRECEDÊNCIA EM MÁQUINAS PARALELAS IDÊNTICAS

Neste artigo é apresentado o problema de escalonamento de tarefas com tempos de execução unitários e com restrições de precedência, considerando um número variável de máquinas paralelas idênticas, que é NP-difícil. Para este problema, a melhor razão de aproximação era fornecida pelo algoritmo de Coffman e Graham (1972), de fator de aproximação $2 - \frac{2}{m}$, para $m \geq 3$ máquinas paralelas idênticas, e que perdurou por um longo tempo até que recentemente um algoritmo de fator de aproximação $2 - \frac{7}{3m+1}$ foi proposto por Gangal e Ranade (2008), proporcionando uma melhoria pequena mas significativa e com conceitos teóricos interessantes e difícil entendimento, cuja análise de complexidade é apresentada.