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.

90B35 Deterministic scheduling theory in operations research
Full Text: DOI