@MASTERSTHESIS{ 2017:1817033495,
 	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}
}