Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Scheduling independent tasks on uniform processors
Dobson G. SIAM Journal on Computing13 (4):705-716,1984.Type:Article
Date Reviewed: Apr 1 1986

This paper addresses the worst-case behavior of the LPT (Longest Processing Time first) scheduling heuristic when applied to processors of different speeds. It is shown that, for this model, LPT’s worst-case performance bound lies in the range [1.512, 1.583]. From this we can conclude that LPT is inferior to the MULTIFIT algorithm, which is known to possess a comparable time complexity and has been shown [1] to yield a worst-case bound of less than 1.4. Additionally, for processors of identical speeds, “parameterized” results are obtained which depend on the ratio of the longest task to the overall finish time, in a fashion which is similar in spirit to parameterized results dependent on the number of tasks assigned to a latest-finishing processor [2].

Reviewer:  M. A. Langston Review #: CR109010
1) Friesen, D. K.; and Langston, M. A.Bounds for multifit scheduling on uniform processors, SIAM J. Comput. 12 (1983), 60–70.
2) Coffman, E. G., Jr; and Sethi, R.A generalized bound on LPT sequencing, RAIRO-Informatique 10, 5 (1976), 17–25.
Bookmark and Share
 
Scheduling (D.4.1 ... )
 
 
Sequencing And Scheduling (F.2.2 ... )
 
 
Miscellaneous (G.2.m )
 
Would you recommend this review?
yes
no
Other reviews under "Scheduling": Date
The gradient model load balancing method
Lin F., Keller R. (ed) IEEE Transactions on Software Engineering 13(1): 32-38, 1987. Type: Article
Sep 1 1987
Preemptive scheduling of a multiprocessor system with memories to minimize maximum lateness
Lai T., Sahni S. SIAM Journal on Computing 13(4): 690-704, 1984. Type: Article
Jul 1 1985
Synthesizing code for resource controllers
Ramamritham K. IEEE Transactions on Software Engineering SE-11(9): 774-783, 1985. Type: Article
Feb 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy