Algorithms for Scheduling Tasks on Unrelated Processors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Algorithms for Scheduling Tasks on Unrelated Processors

Full text

Pdf (987 KB)

Source

Journal of the ACM (JACM) archive
Volume 28 , Issue 4 (October 1981) table of contents

Pages: 721 - 736

Year of Publication: 1981

ISSN:0004-5411

Authors

Ernest Davis	Computer Science Department, Yale University, Box 2158, Yale Station, New Haven, CT
Jeffrey M. Jaffe	IBM Thomas J Watson Research Laboratory, Box 218, Yorktown Heights, NY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 68, Citation Count: 8

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	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/322276.322284 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	BRUNO, J, COFFMAN, E G JR., AND SETHI, R Algorithms for mlmmlzmg mean flow time IFIP 74, North-Holland, Amsterdam, 1974, pp 504-510
	3	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	4	GRAHAM, R L Bounds on multlprocessmg timing anomalies SIAM J. Appl Math 17 (1969), 263-269
	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	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 [doi>10.1145/322003.322011]
	7	JAFFE, J M Bounds on the schedulmg of typed task systems SIAM J Comput 9, 3 (Aug 1980), 541-551
	8	JAFFE, J.M Efficient scheduhng of tasks without full use of processor resources Theor Comput Scz 12 (1980), 1-17.
	9	KAFURA, D G., AND SHEN, V Y Task scheduhng on a muluprocessor system with independent memories SIAM J. Comput 6 (March 1977), 167-187
	10	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 [doi>10.1145/322092.322101]
	11	LIu, J.W.S., AND LIU, C L Performance analysts of multiprocessor systems containing functionally dedicated processors Acta lnf 10, 1 (1978) 95-104
	12	Sartaj K. Sahni, Algorithms for Scheduling Independent Tasks, Journal of the ACM (JACM), v.23 n.1, p.116-127, Jan. 1976 [doi>10.1145/321921.321934]
	13	SAHNI, S, AND GONZALEZ, T Preemptive scheduling of two unrelated machines Tech Rep 76-16, Computer Science Dep, Unlv of Minnesota, Minneapolis, Mmn, Nov 1976

CITED BY 8

	Francis Sourd, Scheduling Tasks on Unrelated Machines: Large Neighborhood Improvement Procedures, Journal of Heuristics, v.7 n.6, p.519-531, November 2001
	Anja Feldmann , Ming-Yang Kao , Jiří Sgall , Shang-Hua Teng, Optimal online scheduling of parallel jobs with dependencies, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.642-651, May 16-18, 1993, San Diego, California, United States
	James Aspnes , Yossi Azar , Amos Fiat , Serge Plotkin , Orli Waarts, On-line load balancing with applications to machine scheduling and virtual circuit routing, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.623-631, May 16-18, 1993, San Diego, California, United States
	Jeffrey M. Jaffe, Distributed multi-destination routing: The constraints of local information, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.49-54, August 18-20, 1982, Ottawa, Canada
	Yossi Azar , Kamal Jain , Vahab Mirrokni, (Almost) optimal coordination mechanisms for unrelated machine scheduling, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.323-332, January 20-22, 2008, San Francisco, California
	Michael A. Bender , Raphaël Clifford , Kostas Tsichlas, Scheduling algorithms for procrastinators, Journal of Scheduling, v.11 n.2, p.95-104, April 2008
	Miklos Ajtai , James Aspnes , Moni Naor , Yuval Rabani , Leonard J. Schulman , Orli Waarts, Fairness in scheduling, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.477-485, January 22-24, 1995, San Francisco, California, United States
	Michael P. McGarry , Martin Reisslein , Violet R. Syrotiuk, Access control in heterogeneous multichannel wireless networks, Proceedings of the first international conference on Integrated internet ad hoc and sensor networks, May 30-31, 2006, Nice, France