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.
|
