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

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

Título:      Stochastic Scheduling on Unrelated Machines
            
Palestrante: Maxim Sviridenko
             University of Warwick

Hora e Data: 14h, sexta-feira, 16 de agosto de 2013

Local:       Sala Multi-usos do Numec

Resumo:

Two important characteristics encountered in many real-world
scheduling  problems  are heterogeneous  machines/processors
and a  certain degree of uncertainty about  the actual sizes
of jobs.  The first characteristic entails machine dependent
processing times  of jobs and  is captured by  the classical
unrelated    machine    scheduling    model.   The    second
characteristic   is  adequately   addressed   by  stochastic
processing times  of jobs as  they are studied  in classical
stochastic scheduling  models.  While there  is an extensive
but separate  literature for  the two scheduling  models, we
study for  the first time  a combined model that  takes both
characteristics  into  account  simultaneously.   Here,  the
processing time of job j  on machine i is governed by random
variable P_{ij}  , and its actual  realization becomes known
only upon job completion. With w_j being the given weight of
job  j, we  study the  classical objective  to  minimize the
expected total weighted completion time. By means of a novel
time-indexed  linear programming  relaxation, we  compute in
polynomial  time   a  scheduling  policy   with  performance
guarantee 3/2+D.  Here, D is  an upper bound on  the squared
coefficient of  variation of the processing  times.  We show
that  the dependence of  the performance  guarantee on  D is
tight,  as we  obtain  a D/2  lower  bound for  the type  of
policies that we use. When jobs also have individual release
dates, our  bound is 2 +  D.  Via D=0,  currently best known
bounds  for  deterministic  scheduling  are contained  as  a
special case.


Joint work with Martin Skutella (TU Berlin) and Marc Uetz
(University of Twente)