A generalized bound on LPT sequencing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A generalized bound on LPT sequencing

Full text

Pdf (246 KB)

Source

Joint International Conference on Measurement and Modeling of Computer Systems archive
Proceedings of the 1976 ACM SIGMETRICS conference on Computer performance modeling measurement and evaluation table of contents

Cambridge, Massachusetts, United States

Pages: 306 - 310

Year of Publication: 1976

Authors

E. G. Coffman, Jr.
Ravi Sethi

Sponsors

IFIP WG 7.3 : IFIP WG 7.3
SIGMETRICS: ACM Special Interest Group on Measurement and Evaluation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 26, Citation Count: 2

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/800200.806205 What is a DOI?

ABSTRACT

In this paper we shall generalize Graham's result so as to include a parameter characterizing the number of tasks assigned to processors by the LPT rule. The new result will show that the worst-case performance bound for LPT sequencing approaches unity approximately as 1+1/k, where k is the least number of tasks on any processor, or where k is the number of tasks on a processor whose last task terminates the schedule. Thus, we shall have a result very similar to the parameterized bounds for bin-packing heuristics [JDUGG]. We shall also obtain out of the analysis an alternate proof of Graham's result.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Coffman, E. G., Jr., Computer and Job-Shop Scheduling Theory, John Wiley and Sons, 1975.
	2	Graham, R. L., "Bounds on Multiprocessor Timing Anomalies," SIAM Journal on Applied Math, 17 (1969), 416-429.
	3	Johnson, D. S., A. Demers, J. D. Ullman, M. R. Garey and R. L. Graham, "Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms," SIAM Journal on Computing, 3 (1974), 299-326.

CITED BY 2

	Bruce Weide, A Survey of Analysis Techniques for Discrete Algorithms, ACM Computing Surveys (CSUR), v.9 n.4, p.291-313, Dec. 1977
	Oscar H. Ibarra , Chul E. Kim, Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors, Journal of the ACM (JACM), v.24 n.2, p.280-289, April 1977