Use este identificador para citar ou linkar para este item:
https://repositorio.ufu.br/handle/123456789/48015| ORCID: |  http://orcid.org/0009-0001-9537-9556 |
| Tipo do documento: | Trabalho de Conclusão de Curso |
| Tipo de acesso: | Acesso Aberto |
| Título: | Algoritmos para as principais variantes do problema de escalonamento de tarefas |
| Autor(es): | Domingues, Maria Luísa Gabriel |
| Primeiro orientador: | Gabriel, Paulo Henrique Ribeiro |
| Primeiro membro da banca: | Fernandes, Márcia Aparecida |
| Segundo membro da banca: | Travençolo, Bruno Augusto Nassif |
| Resumo: | O problema de escalonamento de tarefas é um dos vários problemas de otimização da computação que pertencem à Classe NP-Completo, evidenciando a alta complexidade na obtenção de soluções exatas, e abrindo espaço para a produção de algoritmos aproximados. Com o estudo de muitos pesquisadores do ramo no decorrer das décadas, vários algoritmos aproximados foram projetados para obter soluções próximas da solução ótima em tempo hábil para várias instâncias do problema, respeitando uma gama de restrições atreladas a cada uma delas, buscando torná-las úteis para aplicação em ambientes reais. Neste trabalho, abordamos as cinco variantes mais conhecidas do problema de escalonamento: escalonamento de tarefas em uma única máquina, multiprocessamento para máquinas idênticas com memória compartilhada ou distribuída, e multiprocessamento para máquinas não-idênticas com memória compartilhada ou distribuída. Para cada uma dessas variantes, então, é descrito o sistema em que elas se inserem e as restrições e custos que elas consideram, além de ser apresentado alguns algoritmos aproximados, analisando a estratégia, complexidade e razão de aproximação de cada um deles. Por fim, é esperado que essa exposição extensa de várias estratégias de aproximação para vários contextos de escalonamento contribua para a sistematização do conhecimento de algoritmos aproximados para esse problema e sirva de base para outras pesquisas. |
| Palavras-chave: | Escalonamento de Tarefas Algoritmos de Aproximação Heurísticas Tarefas Independentes DAG |
| Área(s) do CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::ANALISE DE ALGORITMOS E COMPLEXIDADE DE COMPUTACAO |
| Idioma: | por |
| País: | Brasil |
| Editora: | Universidade Federal de Uberlândia |
| Referência: | DOMINGUES, Maria Luísa Gabriel. Algoritmos para as principais variantes do problema de escalonamento de tarefas. 2025. 68 f. Trabalho de Conclusão de Curso (Graduação em Ciência da Computação) - Universidade Federal de Uberlândia, Uberlândia, 2025. |
| URI: | https://repositorio.ufu.br/handle/123456789/48015 |
| Data de defesa: | 26-Set-2025 |
| Aparece nas coleções: | TCC - Ciência da Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| AlgoritmosPrincipaisVariantes.pdf | 1.04 MB | Adobe PDF |  Visualizar/Abrir |
Este item está licenciada sob uma Licença Creative Commons
