Scheduling in the dark

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Scheduling in the dark

Full text

Pdf (994 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-first annual ACM symposium on Theory of computing table of contents

Atlanta, Georgia, United States

Pages: 179 - 188

Year of Publication: 1999

ISBN:1-58113-067-8

Author

Jeff Edmonds

York University, Canada

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 30, Citation Count: 23

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/301250.301299 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	Piotr Berman , Chris Coulston, Speed is More Powerful than Claivoyance, Proceedings of the 6th Scandinavian Workshop on Algorithm Theory, p.255-263, July 08-10, 1998
	2	Timothy B. Brecht , Kaushik Guha, Using parallel program characteristics in dynamic processor allocation policies, Performance Evaluation, 27-28, p.519-539, Oct. 1996 [doi>10.1016/0166-5316(96)00030-2 ]
	3	Xiaotie Deng , Patrick Dymond, On multiprocessor system scheduling, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.82-88, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237510]
	4	Xiaotie Deng , Nian Gu , Tim Brecht , KaiCheng Lu, Preemptive scheduling of parallel jobs on multiprocessors, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.159-167, January 28-30, 1996, Atlanta, Georgia, United States
	5	Xiaotie Deng , Elias Koutsoupias, Competitive implementation of parallel programs, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.455-461, January 25-27, 1993, Austin, Texas, United States
	6	Jeff Edmonds , Donald D. Chinn , Tim Brecht , Xiaotie Deng, Non-clairvoyant multiprocessor scheduling of jobs with changing execution characteristics (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.120-129, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258565]
	7	Jeff Edmonds, Scheduling in the dark, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.179-188, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301299]
	8	B. Kalyanasundaram , K. R. Pruhs, Minimizing flow time nonclairvoyantly, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.345, October 19-22, 1997
	9	B. Kalyanasundaram , Kirk Pruhs, Speed is as powerful as clairvoyance [scheduling problems], Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.214, October 23-25, 1995
	10	M. Kumar, Measuring Parallelism in Computation-Intensive Scientific/Engineering Applications, IEEE Transactions on Computers, v.37 n.9, p.1088-1098, September 1988 [doi>10.1109/12.2259 ]
	11	Stefano Leonardi , Danny Raz, Approximating total flow time on parallel machines, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.110-119, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258562]
	12	Tsuyoshi Matsumoto, Competitive Analysis of the Round Robin Algorithm, Proceedings of the Third International Symposium on Algorithms and Computation, p.71-77, December 16-18, 1992
	13	Rajeev Motwani , Steven Phillips , Eric Torng, Nonclairvoyant scheduling, Theoretical Computer Science, v.130 n.1, p.17-47, Aug. 1, 1994 [doi>10.1016/0304-3975(94)90151-1 ]
	14	Cynthia A. Phillips , Cliff Stein , Eric Torng , Joel Wein, Optimal time-critical scheduling via resource augmentation (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.140-149, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258570]
	15	Uwe Schwiegelshohn , Walter Ludwig , Joel L. Wolf , John Turek , Philip S. Yu, Smart SMART Bounds for Weighted Response Time Scheduling, SIAM Journal on Computing, v.28 n.1, p.237-253, Feb. 1999 [doi>10.1137/S0097539795286831]
	16	A. Tucker , A. Gupta, Process control and scheduling issues for multiprogrammed shared-memory multiprocessors, Proceedings of the twelfth ACM symposium on Operating systems principles, p.159-166, November 1989
	17	John Turek , Walter Ludwig , Joel L. Wolf , Lisa Fleischer , Prasoon Tiwari , Jason Glasgow , Uwe Schwiegelshohn , Philip S. Yu, Scheduling parallelizable tasks to minimize average response time, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.200-209, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181331]
	18	John Turek , Uwe Schwiegelshohn , Joel L. Wolf , Philip S. Yu, Scheduling parallel tasks to minimize average response time, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.112-121, January 23-25, 1994, Arlington, Virginia, United States
	19	A. Yao, Probablistic Computations: Towards a Unified Measure of Complexity. In Proc. o/18th IEEE Syrup. on Foundations of Computer Schience (1977) 222-227.

CITED BY 23

	Piotr Berman , Chris Coulston, Speed is more powerful than clairvoyance, Nordic Journal of Computing, v.6 n.2, p.181-193, Summer 1999
	Julien Robert , Nicolas Schabanel, Non-clairvoyant scheduling with precedence constraints, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.491-500, January 20-22, 2008, San Francisco, California
	Mark Brehob , Eric Torng , Patchrawat Uthaisombut, Applying extra-resource analysis to load balancing, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.560-561, January 09-11, 2000, San Francisco, California, United States
	Jeff Edmonds , Suprakash Datta , Patrick Dymond, TCP is competitive against a limited adversary, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	János Csirik , Gerhard J. Woeginger, Resource augmentation for online bounded space bin packing, Journal of Algorithms, v.44 n.2, p.308-320, August 2002
	Ho-Leung Chan , Tak-Wah Lam , Kar-Keung To, Non-migratory online deadline scheduling on multiprocessors, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Jeff Edmonds, Scheduling in the dark, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.179-188, May 01-04, 1999, Atlanta, Georgia, United States
	Jeff Edmonds , Donald D. Chinn , Tim Brecht , Xiaotie Deng, Non-clair voy ant multiprocessor scheduling of jobs with changing execution characteristics, Journal of Scheduling, v.6 n.3, p.231-250, May/June 2003
	Jeff Edmonds , Kirk Pruhs, Broadcast scheduling: when fairness is fine, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.421-430, January 06-08, 2002, San Francisco, California
	Julien Robert , Nicolas Schabanel, Pull-based data broadcast with dependencies: be fair to users, not to items, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.238-247, January 07-09, 2007, New Orleans, Louisiana
	Chiu-Yuen Koo , Tak-Wah Lam , Tsuen-Wan Ngan , Kunihiko Sadakane , Kar-Keung To, On-line scheduling with tight deadlines, Theoretical Computer Science, v.295 n.1-3, p.251-261, 24 February 2003
	Chiu-Yuen Koo , Tak-Wah Lam , Tsuen-Wan Ngan , Kar-Keung To, Competitive deadline scheduling via additional or faster processors, Journal of Scheduling, v.6 n.2, p.213-223, March/April 2003
	Chiu-Yuen Koo , Tak-Wah Lam , Tsuen-Wan Ngan , Kar-Keung To, Extra processors versus future information in optimal deadline scheduling, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	Jeff Edmonds , Donald D. Chinn , Tim Brecht , Xiaotie Deng, Non-clair voy ant multiprocessor scheduling of jobs with changing execution characteristics, Journal of Scheduling, v.6 n.3, p.231-250, May/June 2003
	Tak-Wah Lam , Kar-Keung To, Performance guarantee for online deadline scheduling in the presence of overload, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.755-764, January 07-09, 2001, Washington, D.C., United States
	Jeff Edmonds , Kirk Pruhs, A maiden analysis of longest wait first, ACM Transactions on Algorithms (TALG), v.1 n.1, p.14-32, July 2005
	Tak-Wah Lam , Tsuen-Wan Johnny Ngan , Kar-Keung To, Performance guarantee for EDF under overload, Journal of Algorithms, v.52 n.2, p.193-206, August 2004
	Bala Kalyanasundaram , Kirk Pruhs, Speed is as powerful as clairvoyance, Journal of the ACM (JACM), v.47 n.4, p.617-643, July 2000
	Wun-Tat Chan , Tak-Wah Lam , Hing-Fung Ting , Wai-Ha Wong, A unified analysis of hot video schedulers, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Wun-Tat Chan , Tak-Wah Lam , Kin-Shing Liu , Prudence W. H. Wong, New resource augmentation analysis of the total stretch of SRPT and SJF in multiprocessor scheduling, Theoretical Computer Science, v.359 n.1, p.430-439, 14 August 2006
	Ho-Leung Chan , Tak-Wah Lam , Kin-Shing Liu, Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.334-343, January 22-26, 2006, Miami, Florida
	Kunal Agrawal , Yuxiong He , Wen Jing Hsu , Charles E. Leiserson, Adaptive scheduling with parallelism feedback, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA
	Kunal Agrawal , Yuxiong He , Charles E. Leiserson, Adaptive work stealing with parallelism feedback, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA