Escalonamento de  tarefas em  processadores heterogêneos
e sujeitas a restrições de precedência.

                     Cid C. de Souza

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

Resumo:
=======

Neste seminário será discutido um problema de escalonamento de tarefas
em   processadores   heterogêneos   e   sujeitas   a   restrições   de
precedência.  O objetivo é  conseguir escalonar  todas as  tarefas nos
processadores de modo a minimizar  o tempo total de conclusão de todas
as tarefas (mínimo makespan). 

Uma alternativa para resolver este problema de forma exata é formulá-lo
como um programa linear inteiro (PLI) e usar um resolvedor de Programação
Linear para computar o modelo.  Assim, serão  apresentadas  diferentes
formulações do problema de escalonamento acima como um PLI.

Ocorre  que  usualmente  os  modelos lineares  para  estes  problemas,
especialmente quando o objetivo é  a minimização do makespan, tendem a
ser muito difíceis mesmo  para os melhores resolvedores de Programação
Linear. Isso se deve à baixa qualidade das suas relaxações lineares as
quais  geram limitantes  duais  que  são incapazes  de  guiar de  modo
conveniente os  algoritmos de  branch-and-bound  implementados  nestes
resolvedores.

A alternativa é tornar as relaxações lineares mais ``apertadas''. Isso
é feito mediante a obtenção de desigualdades lineares fortes usando-se
técnicas  de  combinatória  poliédrica.  Neste  seminário  pretende-se
indicar uma  direção possível  de investigação usando  estas técnicas.
Em um segundo seminário que será feito mais adiante, mostrar-se-á como
foram  obtidas tais  desigualdades  a  partir do  estudo  de um  outro
problema combinatório referente a relações binárias de ordem.