Competitive online scheduling for server systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Competitive online scheduling for server systems

Full text

Pdf (838 KB)

Source

ACM SIGMETRICS Performance Evaluation Review archive
Volume 34 , Issue 4 (March 2007) table of contents

SPECIAL ISSUE: Special issue on new perspectives in scheduling table of contents

Pages: 52 - 58

Year of Publication: 2007

ISSN:0163-5999

Author

Kirk Pruhs

University of Pittsburgh, Pittsburgh, PA

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

abstract references cited by index terms collaborative colleagues

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

ABSTRACT

Our goal here is to illustrate the competitive online scheduling research community's approach to online server scheduling problems by enumerating some of the results obtained for problems related to response and slowdown, and by explaining some of the standard analysis techniques.

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	S. Albers and H. Fujiwara. Energy-efficient algorithms for flow time minimization. In Symposium on Theoretical Aspects of Computer Science, pages 621--633, 2006.
	2	Nir Avrahami , Yossi Azar, Minimizing total flow time and total completion time with immediate dispatching, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777415]
	3	N. Bansal. On the average sojourn time under m---m---1---srpt. Opererations Research Letters, 33(2): 195--200, 2005.
	4	N. Bansal , K. Dhamdhere, Minimizing weighted flow time, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	5	Nikhil Bansal , Kirk Pruhs, Server scheduling in the L_p norm: a rising tide lifts all boat, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780580]
	6	N. Bansal and K. Pruhs. Server scheduling in the weighted l<inf>p</inf> norm. Manuscript, 2003.
	7	N. Bansal, K. Pruhs, and C. Stein. Speed scaling for weighted flow time. In ACM-SIAM Symposium on Discrete Algorithms, 2007.
	8	Luca Becchetti , Stefano Leonardi, Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.94-103, July 2001, Hersonissos, Greece [doi>10.1145/380752.380782]
	9	Luca Becchetti , Stefano Leonardi , Alberto Marchetti-Spaccamela , Kirk Pruhs, Online Weighted Flow Time and Deadline Scheduling, Proceedings of the 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 5th International Workshop on Randomization and Approximation Techniques in Computer Science: Approximation, Randomization and Combinatorial Optimization, p.36-47, August 18-20, 2001
	10	C. Chekuri, S. Khanna, and A. Kumar. Multi-processor scheduling to minimize l<inf>p</inf> norms of flow and stretch. Manuscript, 2003.
	11	Chandra Chekuri , Sanjeev Khanna , An Zhu, Algorithms for minimizing weighted flow time, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.84-93, July 2001, Hersonissos, Greece [doi>10.1145/380752.380778]
	12	Jeff Edmonds, Scheduling in the dark, Theoretical Computer Science, v.235 n.1, p.109-141, March 17, 2000 [doi>10.1016/S0304-3975(99)00186-3]
	13	J. Edmonds and K. Pruhs. Multicast pull scheduling: when fairness is fine. Algorithmica, 36:315--330, 2003.
	14	Jeff Edmonds , Kirk Pruhs, A maiden analysis of Longest Wait First, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	15	Bala Kalyanasundaram , Kirk Pruhs, Speed is as powerful as clairvoyance, Journal of the ACM (JACM), v.47 n.4, p.617-643, July 2000 [doi>10.1145/347476.347479]
	16	Bala Kalyanasundaram , Kirk R. Pruhs, Minimizing flow time nonclairvoyantly, Journal of the ACM (JACM), v.50 n.4, p.551-567, July 2003 [doi>10.1145/792538.792545]
	17	B. Kalyanasundaram, K. R. Pruhs, and M. Velauthapillai. Scheduling broadcasts in wireless networks. Journal of Scheduling, 4:339--354, 2001.
	18	S. Leonardi. A simpler proof of preemptive flow-time approximation. In Approximation and On-line Algorithms, Lecture Notes in Computer Science. Springer, 2003.
	19	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]
	20	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]
	21	S. Muthukrishnan , Rajmohan Rajaraman , Anthony Shaheen , Johannes E. Gehrke, Online Scheduling to Minimize Average Stretch, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.433, October 17-18, 1999
	22	C. Phillips, C. Stein, E. Torng, and J. Wein. Optimal time-critical scheduling via resource augmentation. Algorithmica, pages 163--200, 2002.
	23	K. Pruhs, J. Sgall, and E. Torng. Online scheduling. In Handbook on Scheduling. CRC Press, 2004.

CITED BY 6

	Nikhil Bansal , Ho-Leung Chan, Weighted flow time does not admit O(1)-competitive algorithms, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1238-1244, January 04-06, 2009, New York, New York
	Jeff Edmonds , Kirk Pruhs, Scalably scheduling processes with arbitrary speedup curves, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.685-692, January 04-06, 2009, New York, New York
	Nikhil Bansal , Ho-Leung Chan , Kirk Pruhs, Speed scaling with an arbitrary power function, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.693-701, January 04-06, 2009, New York, New York
	Chandra Chekuri , Benjamin Moseley, Online scheduling to minimize the maximum delay factor, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1116-1125, January 04-06, 2009, New York, New York
	Hongyang Sun , Yangjie Cao , Wen-Jing Hsu, Non-clairvoyant speed scaling for batched parallel jobs on multiprocessors, Proceedings of the 6th ACM conference on Computing frontiers, May 18-20, 2009, Ischia, Italy
	Ho Leung Chan , Jeff Edmonds , Kirk Pruhs, Speed scaling of processes with arbitrary speedup curves on a multiprocessor, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, August 11-13, 2009, Calgary, AB, Canada