On the Expected Relative Performance of List Scheduling

Publisher Website
Google Scholar
Abstract
Let X̄ = (X1, …, Xn) denote an ordered list of service times required by n tasks. The service will be performed by m ≥ 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 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(X̄) of a list schedule is usually longer than necessary. Reordering the tasks in an optimal way can reduce the makespan to OPT(X̄), the smallest possible makespan, but requires knowing the Xi in advance and solving an NP-complete problem. The ratio R(X̄) = L(X̄)/OPT(X̄) measures the penalty paid for serving the tasks in a predetermined order. Here, the service times Xi are treated as independent identically distributed random variables. Two distributions for Xi, uniform and exponential, are considered. Bounds on the mean ER(X̄) and on the distribution function P[R(X̄) > x] are obtained.

This publication has 0 references indexed in Scilit: