A probabilistic analysis of multiprocessor list scheduling: The Erlang case.

*(English)*Zbl 0605.68023Let \(\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.

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 |