# 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.

##### MSC:
 68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
##### Keywords:
ordered list; parallel processors
Full Text: