Submitted by Elton Lever (elton@icomp.ufam.edu.br) on 2018-08-23T20:26:01Z
No. of bitstreams: 1
DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) / Approved for entry into archive by Secretaria PPGI (secretariappgi@icomp.ufam.edu.br) on 2018-08-23T20:35:20Z (GMT) No. of bitstreams: 1
DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-08-24T13:35:27Z (GMT) No. of bitstreams: 1
DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) / Made available in DSpace on 2018-08-24T13:35:28Z (GMT). No. of bitstreams: 1
DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5)
Previous issue date: 2017-06-22 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This dissertation addresses the class of job scheduling problems with precedence
constraints and unit execution times, in identical parallel processors. Such a class of
problems is of great importance in computational complexity theory, since small varia-
tions in the conditions involved in scheduling make an easy problem very difficult. Two
major problems involve the condition of the number of processors, where, if the number
of processors is variable, given as input, such problem is proved to be NP-complete, but
if the number of processors is fixed, the problem is still open. In this context, the focus
of the research involves the problem already proven to be NP-complete, where for which
we investigated the main approximation algorithms in the literature and their proofs of
approximation ratio of the optimal, such as of the Garey & Jonhson’s 2-approximation
algorithm, of the Hu, of the Coffman & Graham, and of the Gangal & Ranade with
2 − (7/(3P + 1)), the best approximation ratio in the literature. The approximation ratio proofs
of such algorithms were detailed. As the main contribution of this research, were proved
the optimality for specific classes of acyclic directed graphs involving trees (prece-
dence trees, such as in-tree and out-tree) for the best approximation algorithms literature. / 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. / Compreender o que querem em alguns momentos.
| Identifer | oai:union.ndltd.org:IBICT/oai:http://localhost:tede/6556 |
| Date | 22 June 2017 |
| Creators | Lever, Elton Carlos Costa, 92 991210234 |
| Contributors | rosiane@icomp.ufam.edu.br, Rodrigues, Rosiane de Freitas, Barreto, Raimundo da Silva, Pio, José Luiz de Souza |
| Publisher | Universidade Federal do Amazonas, Programa de Pós-graduação em Informática, UFAM, Brasil, Instituto de Computação |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFAM, instname:Universidade Federal do Amazonas, instacron:UFAM |
| Rights | http://creativecommons.org/licenses/by/4.0/, info:eu-repo/semantics/openAccess |
| Relation | 1052477850274827528, 500 |
Page generated in 0.002 seconds