Online scheduling to minimize the maximum delay factor

ABSTRACT

In this paper two scheduling models are addressed. First is the standard model (unicast) where requests (or jobs) are independent. The other is the broadcast model where broadcasting a page can satisfy multiple outstanding requests for that page. We consider online scheduling of requests when they have deadlines. Unlike previous models, which mainly consider the objective of maximizing throughput while respecting deadlines, here we focus on scheduling all the given requests with the goal of minimizing the maximum delay factor. The delay factor of a schedule is defined to be the minimum α ≥ 1 such that each request i is completed by time a_i + α(d_i - a_i) where a_i is the arrival time of request i and d_i is its deadline. Delay factor generalizes the previously defined measure of maximum stretch which is based only the processing times of requests [9, 11].

We prove strong lower bounds on the achievable competitive ratios for delay factor scheduling even with unit-time requests. Motivated by this, we consider resource augmentation analysis [24] and prove the following positive results. For the unicast model we give algorithms that are (1 + ε)-speed O(1/ε)-competitive in both the single machine and multiple machine settings. In the broadcast model we give an algorithm for same-sized pages that is (2 + ε)-speed O(1/ε²)-competitive. For arbitrary page sizes we give an algorithm that is (4 + ε)-speed O(1/ε²)-competitive.

REFERENCES

• 1: S. Acharya, M. Franklin, and S. Zdonik. Dissemination-based data delivery using broadcast disks. Personal Communications, IEEE {see also IEEE Wireless Communications}, 2(6):50--60, Dec 1995.
• 2: Demet Aksoy , Michael Franklin, R × W: a scheduling approach for large-scale on-demand data broadcast, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.846-860, Dec. 1999 [doi>10.1109/90.811450]
• 3: 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]
• 4: Nikhil Bansal , Moses Charikar , Sanjeev Khanna , Joseph (Seffi) Naor, Approximating the average response time in broadcast scheduling, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 5: Nikhil Bansal , Don Coppersmith , Maxim Sviridenko, Improved approximation algorithms for broadcast scheduling, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.344-353, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109596]
• 6: 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]
• 7: Amotz Bar-Noy , Randeep Bhatia , Joseph (Seffi) Naor , Baruch Schieber, Minimizing Service and Operation Costs of Periodic Scheduling, Mathematics of Operations Research, v.27 n.3, p.518-544, August 2002 [doi>10.1287/moor.27.3.518.314]
• 8: Yair Bartal , S. Muthukrishnan, Minimizing maximum response time in scheduling broadcasts, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.558-559, January 09-11, 2000, San Francisco, California, United States
• 9: 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
• 10: Michael A. Bender , Raphaël Clifford , Kostas Tsichlas, Scheduling algorithms for procrastinators, Journal of Scheduling, v.11 n.2, p.95-104, April 2008 [doi>10.1007/s10951-007-0038-4]
• 11: Michael A. Bender , S. Muthukrishnan , Rajmohan Rajaraman, Improved algorithms for stretch scheduling, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.762-771, January 06-08, 2002, San Francisco, California
• 12: A. Burns and S. Baruah. Sustainability in real-time scheduling. Journal of Computing Science and Engineering, 2(1):74--97, 2008.
• 13: Wun-Tat Chan, Tak Wah Lam, Hing-Fung Ting, and Prudence W. H. Wong. New results on on-demand broadcasting with deadline via job scheduling with cancellation. In Kyung-Yong Chwa and J. Ian Munro, editors, COCOON, volume 3106 of Lecture Notes in Computer Science, pages 210--218, 2004.
• 14: Jessica Chang , Thomas Erlebach , Renars Gailis , Samir Khuller, Broadcast scheduling: algorithms and complexity, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.473-482, January 20-22, 2008, San Francisco, California
• 15: Moses Charikar , Samir Khuller, A robust maximum completion time measure for scheduling, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.324-333, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109594]
• 16: 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 [doi>10.1145/1007352.1007411]
• 17: Marek Chrobak , Christoph Dürr , Wojciech Jawor , Łukasz Kowalik , Maciej Kurowski, A Note on Scheduling Equal-Length Jobs to Maximize Throughput, Journal of Scheduling, v.9 n.1, p.71-73, February 2006 [doi>10.1007/s10951-006-5595-4]
• 18: 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]
• 19: Jeff Edmonds and Kirk Pruhs. Multicast pull scheduling: When fairness is fine. Algorithmica, 36(3):315--330, 2003.
• 20: 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 [doi>10.1145/1077464.1077467]
• 21: 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
• 22: Rajiv Gandhi , Samir Khuller , Yoo-Ah Kim , Yung-Chun (Justin) Wan, Algorithms for Minimizing Response Time in Broadcast Scheduling, Algorithmica, v.38 n.4, p.597-608, January 2004 [doi>10.1007/s00453-003-1058-x]
• 23: Rajiv Gandhi , Samir Khuller , Srinivasan Parthasarathy , Aravind Srinivasan, Dependent rounding and its applications to approximation algorithms, Journal of the ACM (JACM), v.53 n.3, p.324-360, May 2006 [doi>10.1145/1147954.1147956]
• 24: 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]
• 25: Bala Kalyanasundaram, Kirk Pruhs, and Mahendran Velauthapillai. Scheduling broadcasts in wireless networks. Journal of Scheduling, 4(6):339--354, 2000.
• 26: David Karger, C. Stein, and Joel Wein. Scheduling algorithms. In M. J. Atallah, editor, Handbook on Algorithms and Theory of Computation, chapter 34. 1999.
• 27: Samir Khuller and Yoo Ah Kim. Equivalence of two linear programming relaxations for broadcast scheduling. Oper. Res. Lett., 32(5):473--478, 2004.
• 28: Jae-Hoon Kim , Kyung-Yong Chwa, Scheduling broadcasts with deadlines, Theoretical Computer Science, v.325 n.3, p.479-488, 6 October 2004 [doi>10.1016/j.tcs.2004.02.047]
• 29: Insup Lee, Joseph Y-T. Leung, and Sang Son, editors. Handbook of Real-Time and Embedded Systems. CRC Press, 2007.
• 30: Kirk Pruhs, Competitive online scheduling for server systems, ACM SIGMETRICS Performance Evaluation Review, v.34 n.4, March 2007 [doi>10.1145/1243401.1243411]
• 31: Kirk Pruhs, Jiri Sgall, and Eric Torng. Handbook of Scheduling: Algorithms, Models, and Performance Analysis, chapter Online Scheduling. 2004.
• 32: Jiri Sgall, On-line Scheduling, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.196-231, January 1998
• 33: Feifeng Zheng, Stanley P. Y. Fung, Wun-Tat Chan, Francis Y. L. Chin, Chung Keung Poon, and Prudence W. H. Wong. Improved on-line broadcast scheduling with deadlines. In Danny Z. Chen and D. T. Lee, editors, COCOON, volume 4112 of Lecture Notes in Computer Science, pages 320--329, 2006.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms