Stochastic Scheduling on Unrelated Machines

Speaker: Maxim Sviridenko - University of Warwick
Date: 16/08/2013
Time: 14h00
Local: Numec´s multipurpose room

Abstract: 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.



Núcleo de Apoio à Pesquisa em Modelagem Estocástica e Complexidade.



Rua do Matão, 1010.
Cidade Universitária.
São Paulo - SP - Brasil.
CEP 05508-090.



(11) 3091-1717