A probabilistic analysis of multiprocessor list scheduling: the erlang case (Q3742709)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3978372
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A probabilistic analysis of multiprocessor list scheduling: the erlang case |
scientific article; zbMATH DE number 3978372 |
Statements
A probabilistic analysis of multiprocessor list scheduling: the erlang case (English)
0 references
1985
0 references
ordered list
0 references
parallel processors
0 references
0.89877146
0 references
0.8572247
0 references
0.8557701
0 references
0.8513873
0 references
0.84812266
0 references
0.8427556
0 references
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.
0 references