@MASTERSTHESIS{ 2017:972499484,
 	title = {Casos especiais ótimos de algoritmos aproximativos para problemas de escalonamento com restrições de precedência em processadores paralelos idênticos},
 	year = {2017},
 	url = "https://tede.ufam.edu.br/handle/tede/6556",
 	abstract = "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.",
 	publisher = {Universidade Federal do Amazonas},
 	scholl = {Programa de Pós-graduação em Informática},
 	note = {Instituto de Computação}
}