On the Expected Relative Performance of List Scheduling

E. G. Coffman and E. N. Gilbert
Additional contact information
E. G. Coffman: AT&T Bell Laboratories, Murray Hill, New Jersey
E. N. Gilbert: AT&T Bell Laboratories, Murray Hill, New Jersey

Operations Research, 1985, vol. 33, issue 3, 548-561

Abstract: 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.

Keywords: 570 probabilistic analysis of scheduling algorithms; 585 parallel machine scheduling (search for similar items in EconPapers)
Date: 1985
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.33.3.548 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:33:y:1985:i:3:p:548-561

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().