# zbMATH — the first resource for mathematics

On the expected relative performance of list scheduling. (English) Zbl 0569.90044
Let $$\bar X=(X_ 1,...,X_ n)$$ denote an ordered list of service times required by n tasks. The service will be performed by $$m\geq 2$$ processors working in parallel. Each processor serves one task at a time and, having once started a task, finishes it before starting another. A schedule determines how the tasks are to be served. A list schedule keeps the tasks not yet serviced listed in the order prescribed by $$\bar X.$$ Whenever a processor completes a service, it then takes its next task from the head of the list. The makespan of a schedule is the time required for all service to be completed. The makespan $$L(\bar X)$$ of a list schedule is usually longer than necessary. Reordering the tasks in an optimal way can reduce the makespan to $$OPT(\bar X)$$, the smallest possible makespan, but requires knowing the $$X_ i$$ in advance and solving an NP-complete problem. The ratio $$R(\bar X)=L(\bar X)/OPT(\bar X)$$ measures the penalty paid for serving the tasks in a predetermined order. Here, the service times $$X_ i$$ are treated as independent identically distributed random variables. Two distributions for $$X_ i$$, uniform and exponential, are considered. Bounds on the mean $$ER(\bar X)$$ and on the distribution function $$P[R(\bar X)>x]$$ are obtained.

##### MSC:
 90B35 Deterministic scheduling theory in operations research
##### Keywords:
expected relative performance; list schedule; makespan
Full Text: