zbMATH — the first resource for mathematics

A probabilistic analysis of multiprocessor list scheduling: The Erlang case. (English) Zbl 0605.68023
Let \(\bar T\equiv (T_ 1,...,T_ n)\) denote an ordered list of n taks, which have to be served on \(m\geq 2\) parallel processors. \(X_ i\) denotes the service time of \(T_ i\); \(\bar X\equiv (X_ 1,..,X_ n)\) is a set of independent, identically distributed stochastic variables. Service of the tasks on each processor is non-preemptive. The tasks are served according to a list schedule: Serve the tasks in their order \(T_ 1,...,T_ n\); start serving \(T_ 1,...,T_ m\), and whenever a processor completes a service, let it take as its next task the one which is at the head of the remainder of the list. L(\=X) denotes the makespan of the list schedule for \(\bar X,\) i.e., the time required to complete the service of all tasks. If the exact values of \(X_ 1,...,X_ n\) where known in advance, the makespan might be reduced by reordering the tasks in advance in an optimal way. Let OPT\((\bar X)\) denote the minimal makespan which can thus be obtained.
The present study is devoted to a probabilistic analysis of the ratio \(R(\bar X)=L(\bar X)/OPT(\bar X)\) for the case that the \(X_ i\) have an Erlang distribution. In particular, bounds for the mean and distribution of \(R(\bar X)\) are obtained. The results also apply to the heuristic Lowest-Fit rule in bin-packing.

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
Full Text: DOI