Generalizing the Kawaguchi-Kyan Bound to Stochastic Parallel Machine Scheduling

Abstract

Minimizing the sum of weighted completion times on m identical
parallel machines is one of the most important and classical
scheduling problems. For the stochastic variant where processing
times of jobs are random variables, Möhring, Schulz, and Uetz (1999) presented the first and still best known approximation result,
achieving, for arbitrarily many machines, performance
ratio 1+1/2(1+Delta), where Delta is an upper bound on the
squared coefficient of variation of the processing times. We prove
performance ratio 1+1/2(sqrt(2)-1)(1+Delta)
for the same
underlying algorithm---the Weighted Shortest Expected Processing
Time (WSEPT) rule. For the special case of deterministic scheduling
(i.e., Delta=0), our bound matches the tight performance
ratio 1/2(1+sqrt(2)) of this algorithm (WSPT rule), derived by
Kawaguchi and Kyan in a 1986 landmark paper. We present several
further improvements for WSEPT's performance ratio, one of them
relying on a carefully refined analysis of WSPT yielding, for every
fixed number of machines m, WSPT's exact performance ratio of
order 1/2(1+sqrt(2))-O(1/m^2).