A robust maximum completion time measure for scheduling

ABSTRACT

One popular measure for evaluating the performance of scheduling algorithms, is the maximum response time of any job (makespan). Typically the objective is to find a schedule that minimizes the maximum response time over all jobs. One drawback of this measure is that a relatively small number of jobs in the request set could cause the maximum response time to be very high. Thus, this measure reflects local rather than global properties of the request set. In this paper we consider a robust generalization of this measure. Our goal is to minimize T, such that a given fraction of jobs can be scheduled with a response time of at most T. We demonstrate the applicability of this measure in the context of broadcast scheduling. We show that in the online setting no constant factor online approximation is possible for the problem of minimizing the maximum response time for a given fraction of jobs in the context of broadcast scheduling. We give a factor 5, polynomial time offline approximation algorithm for the problem of minimizing the maximum response time for a given fraction of jobs in the context of broadcast scheduling.

REFERENCES

• 1: Swarup Acharya , Stanley Zdonik, Broadcast disks: dissemination-based data management for asymmetric communication environments, 1998
• 2: S. Acharya, M. Franklin, and S. Zdonik. Dissemination-based data delivery using broadcast disks. In IEEE Personal Communications, 2(6), 1995.
• 3: Swarup Acharya , Rafael Alonso , Michael Franklin , Stanley Zdonik, Broadcast disks: data management for asymmetric communication environments, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.199-210, May 22-25, 1995, San Jose, California, United States
• 4: Demet Aksoy , Michael J. Franklin, On-demand data broadcast for large-scale and dynamic applications, 2000
• 5: 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]
• 6: M. H. Ammar and J. W. Wong. The design of teletext broadcast cycles. In Performance Evaluation, Vol. 5(4), 235--242, 1985.
• 7: 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
• 8: 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]
• 9: Amotz Bar-Noy , Randeep Bhatia , Joseph Naor , Baruch Schieber, Minimizing service and operation costs of periodic scheduling, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.11-20, January 25-27, 1998, San Francisco, California, United States
• 10: Amotz Bar-Noy , Sudipto Guha , Yoav Katz , Joseph (Seffi) Naor , Baruch Schieber , Hadas Shachnai, Throughput maximization of real-time scheduling with batching, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.742-751, January 06-08, 2002, San Francisco, California
• 11: 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
• 12: Randeep Singh Bhatia , Samir Khuller, Approximation algorithms for scheduling problems, 1998
• 13: Moses Charikar , Samir Khuller , David M. Mount , Giri Narasimhan, Algorithms for facility location problems with outliers, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.642-651, January 07-09, 2001, Washington, D.C., United States
• 14: 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
• 15: 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
• 16: 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
• 17: Rajiv Gandhi , Samir Khuller , Yoo Ah Kim , Yung-Chun Wan, Algorithms for Minimizing Response Time in Broadcast Scheduling, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.425-438, May 27-29, 2002
• 18: Rajiv Gandhi , Samir Khuller , Srinivasan Parthasarathy , Aravind Srinivasan, Dependent Rounding in Bipartite Graphs, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.323-332, November 16-19, 2002
• 19: Claire Kenyon , Nicolas Schabanel , Neal Young, Polynomial-time approximation scheme for data broadcast, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.659-666, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335398]
• 20: Bala Kalyanasundaram , Kirk Pruhs , Mahendran Velauthapillai, Scheduling Broadcasts in Wireless Networks, Proceedings of the 8th Annual European Symposium on Algorithms, p.290-301, September 05-08, 2000
• 21: E. Lawler. Combinatorial Optimization. Holt, Rinehart and Winston (1976).
• 22: J. K. Lenstra , D. B. Shmoys , É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming: Series A and B, v.46 n.3, p.259-271, Apr. 1990 [doi>10.1007/BF01585745]
• 23: J. Wong. Broadcast Delivery. In Proc. of the IEEE, 76(12), 1988.

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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Minimax approximation and algorithms

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

General Terms:
Algorithms, Design, Theory