Escalonamento de Tarefas em Máquinas Não Relacionadas 
através de métodos probabilísticos. 

                  Eduardo C. Xavier 

    Sexta-feira, 12 de abril, sala IC2-96, 18:00hs 

Nesta palestra apresentaremos um resultado obtido por Schulz e 
Skutella [``Scheduling Unrelated Machines by Randomized Rounding'' 
A.S. Schulz e M. Skutella'99] para o problema de escalonamento de 
tarefas em máquinas paralelas não-relacionadas. Cada tarefa possui 
valores p_j, r_{ij} e w_j onde p_j é o tempo de processamento da 
tarefa, r_{ij} é o tempo antes do qual a tarefa j nao pode executar na 
máquina i e w_j é o peso da tarefa.  Neste problema devemos escalonar 
de forma não preemptiva as tarefas de forma a minimizar a soma 
ponderada com pesos dos tempos de términos das tarefas.  Na palestra 
mostraremos como obter um fator de aproximação (2 + \epsilon) usando 
métodos probabilísticos.