Optimal time-critical scheduling via resource augmentation (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal time-critical scheduling via resource augmentation (extended abstract)

Full text

Pdf (1.43 MB)

Source

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

El Paso, Texas, United States

Pages: 140 - 149

Year of Publication: 1997

ISBN:0-89791-888-6

Authors

Cynthia A. Phillips	Sandia National Labs, Albuquerque, NM
Cliff Stein	Department of Computer Science, Sudikoff Laboratory, Dartmouth College, Hanover, NH
Eric Torng	Department of Computer Science, A-714, Wells Hall, Michigan State University, East Lansing, MI
Joel Wein	Department of Computer Science, Polytechnic University, Brooklyn, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 62, Citation Count: 49

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/258533.258570 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	Soumen Chakrabarti , Cynthia A. Phillips , Andreas S. Schulz , David B. Shmoys , Clifford Stein , Joel Wein, Improved Scheduling Algorithms for Minsum Criteria, Proceedings of the 23rd International Colloquium on Automata, Languages and Programming, p.646-657, July 08-12, 1996
	2	M. Dertouzos. Control robotics: the procedural control of physical processes. In Proc. IFIF Congress, pages 807-813, 1974.
	3	M. L. Dertouzos , A. K. Mok, Multiprocessor Online Scheduling of Hard-Real-Time Tasks, IEEE Transactions on Software Engineering, v.15 n.12, p.1497-1506, December 1989 [doi>10.1109/32.58762]
	4	Michel X. Goemans, A Supermodular Relaxation for Scheduling with Release Dates, Proceedings of the 5th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.288-300, June 03-05, 1996
	5	Michel X. Goemans, Improved approximation algorthims for scheduling with release dates, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.591-598, January 05-07, 1997, New Orleans, Louisiana, United States
	6	M. Goemans, J. Wein, and D. P. Williamson. Randomized algorithms for improved preemptive scheduling. Working paper, 1996.
	7	R.L. Graham. Bounds for certain multiprocessor anomalies. Bell System Technical Journal, 45:1563- 1581, 1966.
	8	D. Gusfield. Bounds for naive multiple machine scheduling with release times and deadlines. Journal of Algorithms, 5:1-6, 1984.
	9	Leslie A. Hall , Andreas S. Schulz , David B. Shmoys , Joel Wein, Scheduling to minimize average completion time: off-line and on-line approximation algorithms, Mathematics of Operations Research, v.22 n.3, p.513-544, Aug. 1997 [doi>10.1287/moor.22.3.513]
	10	Han Hoogeveen , Arjen P. A. Vestjens, Optimal On-Line Algorithms for Single-Machine Scheduling, Proceedings of the 5th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.404-414, June 03-05, 1996
	11	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
	12	Bala Kalyanasundaram and K. Pruhs, 1996. Personal Communication.
	13	Hans Kellerer , Thomas Tautenhahn , Gerhard J. Woeginger, Approximability and nonapproximability results for minimizing total flow time on a single machine, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.418-426, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237989]
	14	G. Koren, D. Shasha, and S.-C. Huang. Moca: A multiprocessor on-line competitive algorithm for real-time system scheduling. In Proc. l~th Reab Time Systems Symposium, pages 172-181, 1993.
	15	J. Labetoulle, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinooy Kan. Preemptive scheduling of uniform machines subject to release dates. In W.R. Pulleyblank, editor, Progress in Combinatorial Optimization, pages 245-261. Academic Press, 1984.
	16	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]
	17	J. Leung. A new algorithm for scheduling periodic, realtime tasks. Algorithmica, 4:209-219, 1989.
	18	A. Mok. Task scheduling in the control robotics environment. Technical Report TM-77, Laboratory of Computer Science, Massachusetts Institute of Technology, 1976.
	19	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]
	20	C. Phillips, C. Stein, and J. Wein. Minimizing average completion time in the presence of release dates. To appear in Math Programming, 1995.
	21	M. Queyranne and A.S. Schulz. Polyhedral approaches to machine scheduling. Technical Report Technical Report 474/1995, Technical University of Berlin, 1994.
	22	S. Sahni and Y. Cho. Nearly on line scheduling of a uniform processor system with release times. SIAM Journal on Computing, 8:275-285, 1979.
	23	David B. Shmoys , Joel Wein , David P. Williamson, Scheduling Parallel Machines On-line, SIAM Journal on Computing, v.24 n.6, p.1313-1331, Dec. 1995 [doi>10.1137/S0097539793248317]

CITED BY 49

	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
	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
	Thomas Erlebach , Alexander Hall, NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.194-202, January 06-08, 2002, 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
	Bala Kalyanasundaram , Kirk Pruhs, Speed is as powerful as clairvoyance, Journal of the ACM (JACM), v.47 n.4, p.617-643, July 2000
	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
	Ashish Goel , Monika R. Henzinger , Serge Plotkin , Eva Tardos, Scheduling data transfers in a network and the set scheduling problem, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.189-197, May 01-04, 1999, Atlanta, Georgia, United States
	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
	Cynthia A. Phillips , R. N. Uma , Joel Wein, Off-line admission control for general scheduling problems, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.879-888, January 09-11, 2000, San Francisco, California, United States
	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
	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
	Bala Kalyanasundaram , Kirk R. Pruhs, Eliminating migration in multi-processor scheduling, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.499-506, January 17-19, 1999, Baltimore, Maryland, United States
	Michael A. Bender , Soumen Chakrabarti , S. Muthukrishnan, Flow and stretch metrics for scheduling continuous job streams, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.270-279, January 25-27, 1998, San Francisco, California, United States
	Wojciech Jawor, Three dozen papers on online algorithms, ACM SIGACT News, v.36 n.1, March 2005
	Tak Wah Lam , Kar Keung To, Trade-offs between speed and processor in hard-deadline scheduling, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.623-632, January 17-19, 1999, Baltimore, Maryland, United States
	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
	Anand Srinivasan , Sanjoy Baruah, Deadline-based scheduling of periodic task systems on multiprocessors, Information Processing Letters, v.84 n.2, p.93-98, 31 October 2002
	Jae-Hoon Kim , Kyung-Yong Chwa, Online deadline scheduling on faster machines, Information Processing Letters, v.85 n.1, p.31-37, 16 January 2003
	Joël Goossens , Shelby Funk , Sanjoy Baruah, Priority-Driven Scheduling of Periodic Task Systems on Multiprocessors, Real-Time Systems, v.25 n.2-3, p.187-205, September-October 2003
	Francis Y. L. Chin , Stanley P. Y. Fung, Improved competitive algorithms for online scheduling with partial job values, Theoretical Computer Science, v.325 n.3, p.467-478, 6 October 2004
	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
	Piotr Berman , Chris Coulston, Speed is more powerful than clairvoyance, Nordic Journal of Computing, v.6 n.2, p.181-193, Summer 1999
	Sanjoy Baruah , Shelby Funk , Joël Goossens, Robustness Results Concerning EDF Scheduling upon Uniform Multiprocessors, IEEE Transactions on Computers, v.52 n.9, p.1185-1195, September 2003
	Thomas Erlebach , Alexander Hall, NP-Hardness of Broadcast Scheduling and Inapproximability of Single-Source Unsplittable Min-Cost Flow, Journal of Scheduling, v.7 n.3, p.223-241, May-June 2004
	Chandra Chekuri , Ashish Goel , Sanjeev Khanna , Amit Kumar, Multi-processor scheduling to minimize flow time with ε resource augmentation, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	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
	Lui Sha , Tarek Abdelzaher , Karl-Erik Årzén , Anton Cervin , Theodore Baker , Alan Burns , Giorgio Buttazzo , Marco Caccamo , John Lehoczky , Aloysius K. Mok, Real Time Scheduling Theory: A Historical Perspective, Real-Time Systems, v.28 n.2-3, p.101-155, November-December 2004
	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
	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
	Theodore P. Baker, An Analysis of EDF Schedulability on a Multiprocessor, IEEE Transactions on Parallel and Distributed Systems, v.16 n.8, p.760-768, August 2005
	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
	Michael A. Palis, The Granularity Metric for Fine-Grain Real-Time Scheduling, IEEE Transactions on Computers, v.54 n.12, p.1572-1583, December 2005
	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
	Sanjoy K. Baruah, The Non-preemptive Scheduling of Periodic Tasks upon Multiprocessors, Real-Time Systems, v.32 n.1-2, p.9-20, February 2006
	Theodore P. Baker, An Analysis of Fixed-Priority Schedulability on a Multiprocessor, Real-Time Systems, v.32 n.1-2, p.49-71, February 2006
	Sanjoy Baruah , Theodore Baker, Schedulability analysis of global EDF, Real-Time Systems, v.38 n.3, p.223-235, April 2008
	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
	Naveen Garg , Amit Kumar, Minimizing average flow time on related machines, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Klaus Danne , Marco Platzner, An EDF schedulability test for periodic tasks on reconfigurable hardware devices, ACM SIGPLAN Notices, v.41 n.7, July 2006
	Sanjoy K. Baruah , Nathan Wayne Fisher, The partitioned dynamic-priority scheduling of sporadic task systems, Real-Time Systems, v.36 n.3, p.199-226, August 2007
	Nedialko B. Dimitrov , Indrajit Roy, A primal-dual resource augmentation analysis of a constant approximate algorithm for stable coalitions in a cluster, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Nathan Fisher , Sanjoy Baruah, The feasibility of general task systems with precedence constraints on multiprocessor platforms, Real-Time Systems, v.41 n.1, p.1-26, January 2009
	F. Ridouard , P. Richard , F. Cottet , K. Traoré, Some results on scheduling tasks with self-suspensions, Journal of Embedded Computing, v.2 n.3,4, p.301-312, December 2006
	Nikhil Bansal , Kedar Dhamdhere, Minimizing weighted flow time, ACM Transactions on Algorithms (TALG), v.3 n.4, p.39-es, November 2007
	Nan Guan , Qingxu Deng , Zonghua Gu , Wenyao Xu , Ge Yu, Schedulability analysis of preemptive and nonpreemptive EDF on partial runtime-reconfigurable FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.13 n.4, p.1-43, September 2008
	Sanjoy Baruah , Nathan Fisher, Non-migratory feasibility and migratory schedulability analysis of multiprocessor real-time systems, Real-Time Systems, v.39 n.1-3, p.97-122, August 2008
	Tak-Wah Lam , Lap-Kei Lee , Isaac K. K. To , Prudence W. H. Wong, Competitive non-migratory scheduling for flow time and energy, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Mark Cieliebak , Alexander Hall , Riko Jacob , Marc Nunkesser, Sequential vector packing, Theoretical Computer Science, v.409 n.3, p.351-363, December, 2008
	Theodore P. Baker , Sanjoy K. Baruah, An analysis of global edf schedulability for arbitrary-deadline sporadic task systems, Real-Time Systems, v.43 n.1, p.3-24, September 2009