Analysis of Several Task-Scheduling Algorithms for a Model of Multiprogramming Computer Systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Analysis of Several Task-Scheduling Algorithms for a Model of Multiprogramming Computer Systems

Full text

Pdf (1.76 MB)

Source

Journal of the ACM (JACM) archive
Volume 22 , Issue 4 (October 1975) table of contents

Pages: 522 - 550

Year of Publication: 1975

ISSN:0004-5411

Authors

K. L. Krause	Air Force Weapons Laboratory, Kirtland AFB, Albuquerque, NM and Purdue University, West Lafayette, Indiana
V. Y. Shen	Computer Sciences Department, Mathematical Sciences Building, Purdue University, West Lafayette, IN
H. D. Schwetman	Computer Sciences Department, Mathematical Sciences Building, Purdue University, West Lafayette, IN

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 33, Citation Count: 10

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/321906.321917 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	J. Bruno , E. G. Coffman, Jr. , R. Sethi, Scheduling independent tasks to reduce mean finishing time, Communications of the ACM, v.17 n.7, p.382-387, July 1974 [doi>10.1145/361011.361064]
	2	Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
	3	COFFMAN, E. G. JR., AND GRAHAM, R. L. Optimal scheduhng for two-processor systems Acta Informatca I, 3 (1972), 200-213
	4	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	5	M. R. Garey , R. L. Graham , J. D. Ullman, Worst-case analysis of memory allocation algorithms, Proceedings of the fourth annual ACM symposium on Theory of computing, p.143-150, May 01-03, 1972, Denver, Colorado, United States [doi>10.1145/800152.804907]
	6	GRAHAM, R L. Bounds on multlprocesslng anomalies and related packing algorithms Proc. AFIPS 1972 SJCC, Vol 40, AFIPS Press, Montvale, N J , pp 205-217.
	7	GRAHAM, R. L. Bounds on multlprocessing timing anomalies SIAM J Appl. Math 17, 2 (March 1969), 416---429.
	8	M. R. Garey , R. L. Grehem, Bounds on scheduling with limited resources, Proceedings of the fourth ACM symposium on Operating system principles, p.104-111, January 1973
	9	Hu, T.C. Parallel sequencing and assembly line problems Op Res 9, 6 (Nov 1961), 841-848
	10	JOHNSON, D. S., DEMERS, A., ULLMAN, J D , GAREY, M. R., AND GRAHAM, R. L Worst-case performance bounds for rumple one-dimensional packing algorithms SIAM J. Comput. 8, 4 (1974), 299-325.
	11	KARF, R.M. Reduclbihty among combmatomal problems In Complexity of Computer Computations, R. E. Miller and J W. Thatcher, Eds , Plenum Press, New York, 1972, pp. 85-104
	12	Kenneth Leroy Krause, Analysis of computer scheduling with memory constraints., 1973
	13	K. L. Krause , V. Y. Shen , H. D. Schwetman, A task-scheduling algorithm for a multiprogramming computer system, Proceedings of the fourth ACM symposium on Operating system principles, p.112-118, January 1973
	14	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]
	15	MUNTZ, R. R , AND COFFMAN, E. G. JR. Optimal pre-emptive scheduhng on two-processor systems lEEK Trans. Comput. C-18, 11 (Nov 1969), 1014-1020
	16	J. D. Ullman, Polynomial complete scheduling problems, Proceedings of the fourth ACM symposium on Operating system principles, p.96-101, January 1973

CITED BY 10

	D. G. Kafura , V. Y. Shen, An Algorithm to Design the Memory Configuration of a Computer Network, Journal of the ACM (JACM), v.25 n.3, p.365-377, July 1978
	K. L. Krause , V. Y. Shen , H. D. Schwetman, Errata: `` Analysis of Several Task-Scheduling Algorithms for a Model of Multiprogramming Computer Systems'', Journal of the ACM (JACM), v.24 n.3, p.527, July 1977
	Klaus Jansen, Approximate strong separation with application in fractional graph coloring and preemptive scheduling, Theoretical Computer Science, v.302 n.1-3, p.239-256, 13 June 2003
	Ken Fuchs , Dennis Kafura, Memory-constrained task scheduling on a network of dual processors, Journal of the ACM (JACM), v.32 n.1, p.102-129, Jan. 1985
	Luitpold Babel , Bo Chen , Hans Kellerer , Vladimir Kotov, Algorithms for on-line bin-packing problems with cardinality constraints, Discrete Applied Mathematics, v.143 n.1-3, p.238-251, 30 September 2004
	C. Mohan, Survey of recent operating systems research, designs and implementations, ACM SIGOPS Operating Systems Review, v.12 n.1, p.53-89, January 1978
	Maurizio Bruglieri , Matthias Ehrgott , Horst W. Hamacher , Francesco Maffioli, An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints, Discrete Applied Mathematics, v.154 n.9, p.1344-1357, 1 June 2006
	Edward G. Coffman, Jr. , János Csirik, A classification scheme for bin packing theory, Acta Cybernetica, v.18 n.1, p.47-60, January 2007
	Dennis Kafura, Scheduling tasks with critical sections, Proceedings of the 1977 annual conference, p.381-385, January 1977
	Leah Epstein , Meital Levy, Online interval coloring with packing constraints, Theoretical Computer Science, v.407 n.1-3, p.203-212, November, 2008