Título: Escalonamento UET-UCT de Tarefas em Múltiplos Processadores

Resumo: Problemas de escalonamento ocupam, sem dúvida, um local de destaque no conjunto de problemas clássicos de otimização. Isto se deve sobretudo por suas aplicações diretas e extensas. Na indústria, por exemplo, onde o tempo e os custos de produção são determinantes para a obtenção de maiores lucros, existem grandes aplicações para problemas de escalonamento em suas diversas variações. Em um problema de escalonamento em máquinas o objetivo é determinar um agendamento para um conjunto de tarefas em processadores, onde elas serão executadas. Em nosso caso específico desejamos escalonar um conjunto de tarefas que possuem uma relação de precedência, ou seja, uma tarefa i só pode executar após o término da execução de todas as suas predecessoras e além disso se uma predecessora é executada em um processador diferente do que executará i, devemos acrescentar um custo de comunicação entre seus processadores. No problema abordado, os custos são todos unitários (execução e comunicação). O tempo total de execução do conjunto de tarefas deverá ser minimizado. Consideramos duas variações dependentes do número de processadores, na primeira este número faz parte da entrada do problema e é limitado à m. Em uma segunda variação o número de processadores é ilimitado ou de forma mais realista, a quantidade é suficiente para que todas as tarefas sejam executadas sem restrições no número de processadores. Essas duas variações são provadas NP-Difíceis. Abordamos o problema por métodos de Programação Matemática. Elaboramos formulações para as duas variantes do problema, além disso, melhoramos os limites inferior e superior existentes na literatura. Estudamos comparativamente as formulações obtidas, teórica e computacionalmente, o que comprovou a superioridade e eficácia das formulações desenvolvidas nesta dissertação na resolução do problema estudado.

Data: 31/10/2014 Horário: 9h Local: Sala de Seminários Bloco 952

Banca:

• MANOEL BEZERRA CAMPELO NETO (UFC - Orientador)
• RICARDO CORDEIRO CORREA  (UFC)
• CARLOS DIEGO RODRIGUES  (UFC)
• LUCÍDIO DOS ANJOS FORMIGA CABRAL  (UFPB)