zbMATH — the first resource for mathematics

Probabilistic bounds on the performance of list scheduling. (English) Zbl 0595.68037
A probabilistic analysis of list scheduling heuristics for minimizing the makespan on parallel machines is given. The makespan scheduling problem is to schedule n tasks on m identical machines so as to minimize the finishing time of the last task (i.e., the makespan). A well-known class of heuristics for this problem are the list scheduling heuristics in which whenever a machines becomes available a task is assigned to it, and where tasks are assigned in the order induced by some predetermined list. The authors prove that, given task processing times \(X_ 1,...,X_ n\) sampled from a uniform distribution on any interval \([A,B]\) with \(A\geq 0\), the following result holds for any list scheduling heuristic: \[ P(L(\bar X)/OPT(\bar X)<1+((2m-1)/n)(1/(1-2d_{n,e}))\geq 1-e\quad \forall e>0, \] where \(L(\bar X)\) and \(OPT(\bar X)\) are the value of the makespan in the list scheduling heuristic and the optimal schedule respectively for the problem instance given by \(\bar X=(X_ 1,...,X_ n)\), and where \(d_{n,e}\) is related to the Smirnov statistics (or the one-sided Kolmogorov-Smirnov statistics) \(D^+_ n\) through \(P_ n(d_{n,e})=1-e\) with \(P_ n(X)=P(D^+_ n\leq X)\). Note that a closed form expression for \(P_ n(X)\) was given by Birnbaum and Tingey. As a corollary to this result the authors obtain their main result: Given a desired degree of confidence 1-e one can find a minimum sample size N such that if \(n\geq N\) and the n task processing times \(\bar X=(X_ 1,...,X_ n)\) are chosen from any uniform distribution, then \[ P(L(\bar X)/OPT(\bar X)<1+4(m-1)/n)\geq 1-e. \] Note that N does only depend on e and not on the chosen distribution.
Reviewer: A.Kolen

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI