Scheduling to Minimize Average Completion Time Revisited: Deterministic On-line Algorithms
We consider the scheduling problem of minimizing the average weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios compared to the previously best-known deterministic on-line algorithms, which are (4+epsilon)-competitive in either case. Our preemptive algorithm is 2-competitive, which actually meets the competitive ratio of the currently best randomized on-line algorithm for this scenario. Our nonpreemptive algorithm has a competitive ratio of 3.28. Both results are characterized by a surprisingly simple analysis; moreover, the preemptive algorithm also works in the less clairvoyant environment in which only the ratio of weight to processing time of a job becomes known at its release date, but neither its actual weight nor its processing time. In the corresponding nonpreemptive situation, every on-line algorithm has an unbounded competitive ratio
|Date of creation:||06 Feb 2004|
|Date of revision:|
|Contact details of provider:|| Postal: MASSACHUSETTS INSTITUTE OF TECHNOLOGY (MIT), SLOAN SCHOOL OF MANAGEMENT, 50 MEMORIAL DRIVE CAMBRIDGE MASSACHUSETTS 02142 USA|
Web page: http://mitsloan.mit.edu/
More information through EDIRC
|Order Information:|| Postal: MASSACHUSETTS INSTITUTE OF TECHNOLOGY (MIT), SLOAN SCHOOL OF MANAGEMENT, 50 MEMORIAL DRIVE CAMBRIDGE MASSACHUSETTS 02142 USA|
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- W. L. Eastman & S. Even & I. M. Isaacs, 1964. "Bounds for the Optimal Scheduling of n Jobs on m Processors," Management Science, INFORMS, vol. 11(2), pages 268-279, November.
When requesting a correction, please mention this item's handle: RePEc:mit:sloanp:4048. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Christian Zimmermann)
If references are entirely missing, you can add them using this form.