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 - Lever, Elton; Vilca, Omar; de Freitas, Rosiane (Anais do Encontro de Teoria da Computação (ETC); 2016: Anais do I Encontro de Teoria da Computação, 2016)
Neste artigo é apresentado o problema de escalonamento de tarefas com tempos de execução unitários e 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 − 2/m, para m ≥ 3 máquinas paralelas idênticas, e que perdurou por um longo tempo até que recentemente um algoritmo de fator de aproximação 2 − 7/3m+1 foi proposto por Gangal e Ranade (2008), proporcionando uma melhoria pequena mas significativa e com conceitos teóricos interessantes, cuja análise é apresentada.