Preemptive Scheduling of Uniform Processor Systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Preemptive Scheduling of Uniform Processor Systems

Full text

Pdf (561 KB)

Source

Journal of the ACM (JACM) archive
Volume 25 , Issue 1 (January 1978) table of contents

Pages: 92 - 101

Year of Publication: 1978

ISSN:0004-5411

Authors

Teofilo Gonzalez	Department of Computer Science, The Pennsylvania State University, University Park, PA
Sartaj Sahni	Department of Computer Science, University of Minnesota, Minneapolis, MN

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 66, Citation Count: 14

Additional Information:

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/322047.322055 What is a DOI?

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	BLUM, M , FLOYD, R W, PgATT, V R, RIVEST, R L, AND TARJAN, R E. T~me bounds for selection J Comptr Syst Sct 7, 4 (1972), 448-461
	2	COFFMAN, E G JR Computer and Job Shop Scheduhng Theory Wdey, New York, 1976
	3	GONZALEZ, T, IBARRA, O.H , AND SAHNI, S Bounds for LPT schedules on uniform processors SIAM J Comptng 5, 1 (1977), 155-166
	4	HoRowxTz, E.. AND SAI~N~, S Fundamentals of Data Structures Computer Science Press. Woodland Hills, Cahf, 1976
	5	Ellis Horowitz , Sartaj Sahni, Exact and Approximate Algorithms for Scheduling Nonidentical Processors, Journal of the ACM (JACM), v.23 n.2, p.317-327, April 1976 [doi>10.1145/321941.321951]
	6	Edward C. Horvath , Shui Lam , Ravi Sethi, A Level Algorithm for Preemptive Scheduling, Journal of the ACM (JACM), v.24 n.1, p.32-43, Jan. 1977 [doi>10.1145/321992.321995]
	7	KARP, R M Reduclbdlty among combinatorial problems In Complextty of Computer Computations, R E Mdler and J W Thatcher, Eds, Plenum Press, New York, 1972, pp 85-103.
	8	LIu, J W S, AND LIu, C L Bounds on scheduhng algorithms for heterogeneous computing systems Information Processing 74, North-Holland Pub Co, Amsterdam, 1974, pp 349-353.
	9	Jane W. S. Liu , Ai-Tsung Yang, Optimal scheduling of independent tasks on heterogeneous computing systems, Proceedings of the 1974 annual conference, p.38-45, January 1974 [doi>10.1145/800182.810377]
	10	McNAUGHTON, R Scheduhng w,th deadhnes and loss functions Manage Scl 6 (1959), 1-12
	11	R. R. Muntz , E. G. Coffman, Jr., Preemptive Scheduling of Real-Time Tasks on Multiprocessor Systems, Journal of the ACM (JACM), v.17 n.2, p.324-338, April 1970 [doi>10.1145/321574.321586]

CITED BY 14

	E. L. Lawler , J. Labetoulle, On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming, Journal of the ACM (JACM), v.25 n.4, p.612-619, Oct. 1978
	Jia Xu , David Lorge Parnas, On satisfying timing constraints in hard-real-time systems, ACM SIGSOFT Software Engineering Notes, v.16 n.5, p.132-146, Dec. 1991
	Sartaj Sahni , Yookun Cho, Scheduling Independent Tasks with Due Times on a Uniform Processor System, Journal of the ACM (JACM), v.27 n.3, p.550-563, July 1980
	Teofilo F. Gonzalez , Donald B. Johnson, A New Algorithm for Preemptive Scheduling of Trees, Journal of the ACM (JACM), v.27 n.2, p.287-312, April 1980
	Alfredo Goldman , Gregory Mounie , Denis Trystram, 1-Optimality of static BSP computations: scheduling independent chains as a case study, Theoretical Computer Science, v.290 n.3, p.1331-1359, 3 January 2003
	J. Xu , D. L. Parnas, On Satisfying Timing Constraints in Hard-Real-Time Systems, IEEE Transactions on Software Engineering, v.19 n.1, p.70-84, January 1993
	Yu-Kwong Kwok , Ishfaq Ahmad, Static scheduling algorithms for allocating directed task graphs to multiprocessors, ACM Computing Surveys (CSUR), v.31 n.4, p.406-471, Dec. 1999
	Charles Martel, Preemptive Scheduling with Release Times, Deadlines, and Due Times, Journal of the ACM (JACM), v.29 n.3, p.812-829, July 1982
	Kwang S. Hong , Joseph Y.-T. Leung, On-Line Scheduling of Real-Time Tasks, IEEE Transactions on Computers, v.41 n.10, p.1326-1331, October 1992
	Donglei Du, Optimal preemptive semi-online scheduling on two uniform processors, Information Processing Letters, v.92 n.5, p.219-223, 16 December 2004
	Teofilo F. Gonzalez , Joseph Y.-T. Leung , Michael Pinedo, Minimizing total completion time on uniform machines with deadline constraints, ACM Transactions on Algorithms (TALG), v.2 n.1, p.95-115, January 2006
	Young He , Yiwei Jiang, Optimal semi-online preemptive algorithms for machine covering on two uniform machines, Theoretical Computer Science, v.339 n.2, p.293-314, 12 June 2005
	B. V. Grechuk , M. G. Furugyan, Optimal Preemptive Scheduling in Multiprocessor Systems with Incomplete Communication Graph, Cybernetics and Systems Analysis, v.41 n.3, p.397-402, May 2005
	Dvir Shabtay , George Steiner, A survey of scheduling with controllable processing times, Discrete Applied Mathematics, v.155 n.13, p.1643-1666, August, 2007