# 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

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