Casos especiais ótimos de algoritmos aproximativos para problemas de escalonamento com restrições de precedência em processadores paralelos idênticos - Lever, Elton Carlos Costa (Universidade Federal do Amazonas, 2018)
Esta dissertação aborda a classe de problemas de escalonamento de tarefas com restrições de precedências e tempos unitários em processadores paralelos idênticos. Tal classe de problemas tem uma grande importância em teoria da complexidade computacional, uma vez que pequenas variações nas condições envolvidas no esca- lonamento, fazem com que um problema fácil se torne muito difícil. Dois grandes problemas envolvem a condição do número de processadores, onde, se o número de processadores for variável, dado como entrada, tal problema é provado ser NP-completo, mas, se o número de processadores for fixo, o problema ainda está em aberto. Neste contexto, o foco da pesquisa envolve o problema já provado ser NP-completo, onde para qual se investigou os principais algoritmos aproximativos existentes na literatura e suas provas de razão de aproximação do ótimo, tais como o algoritmo 2-aproximativo de Garey & Jonhson e as melhorias de Hu, Coffman & Graham e de Gangal & Ranade (GR) com 2 −(7/(3P+1)), o de melhor razão de aproximação da literatura. As provas de razão de aproximação de tais algoritmos foram detalhadas. Como principal contribuição da pesquisa, foram determinados casos especiais ótimos, para classes específicas de grafos direcionados acíclicos que envolvem arborescências (árvores de precedência, como in-tree e out-tree) para o melhor algoritmos aproximativo da literatura.