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

      Identifiers