============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

============================================================

Título:      Minimizing Maximum Flowtime of Jobs with 
             Arbitrary Parallelizability

Palestrante: Nicolas Schabanel
             CNRS
             École Normale Supérieure de Lyon
             and Université Paris Diderot - Paris 7

Hora e Data: 14h, sexta-feira, 12 de novembro de 2010

Local:       auditório do NUMEC

Resumo:

This talk will start with an introduction to non-clairvoyant
scheduling. I'll  propose a little  crash course on  some of
the technics  that allow  to obtain competitive  analysis in
this very  general framework and  show some of  the numerous
applications  of this  field  to the  wider field of  online
scheduling.  The second  part of the talk will  focus on our
latest  result on  the non-clairvoyant  minimization  of the
maximal  response  time.  More  precisely, we  consider  the
problem  of nonclairvoyantly  scheduling jobs,  which arrive
over   time  and   have   varying  sizes   and  degrees   of
parallelizability,  with  the  objective of  minimizing  the
maximum  flow.   We give  essentially  tight  bounds on  the
achievable competitiveness.  More  specifically we show that
the competitive ratio  of every deterministic nonclairvoyant
algorithm  is high,  namely Omega(sqrt{n}).  But there  is a
simple  batching algorithm that  

   (1+epsilon)-processor O(log n)-competitive algorithm. 

And this simple  batching algorithm is optimally competitive
as   no  deterministic   nonclairvoyant  algorithm   can  be
s-processor o(log n)-competitive for any constant s.


Join work with Kirk Pruhs (Pittsburgh U., USA) and Julien
Robert (IUT Orléans, FRANCE).