On the Expected Relative Performance of List Scheduling

Let X̄ = ( X 1 , …, X n ) 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 X i 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 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 ( X̄ ) and on the distribution function P [ R ( X̄ ) > x ] are obtained.