Casos especiais ótimos de algoritmos aproximativos para problemas de escalonamento com restrições de precedência em processadores paralelos idênticos

• Ano de defesa: 2017
• Autor(a) principal: Lever, Elton Carlos Costa
• Outros Autores: http://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4480323A3
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal do Amazonas; Instituto de Computação; Brasil; UFAM; Programa de Pós-graduação em Informática
• Palavras-chave em Português: Approximative Algorithms; Graphs theory; Parallel processors; Precedence tree; Processing unitary time; Scheduling theory; Algoritmos Aproximativos; Árvores de Precedência; Tempo Unitário de Processamento; Processadores Paralelos; Teoria de Escalonamento; Teoria dos Grafos; CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO: TEORIA DA COMPUTAÇÃO
• Link de acesso: https://tede.ufam.edu.br/handle/tede/6556

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.