Improved approximations for multiprocessor scheduling under uncertainty

ABSTRACT

This paper presents improved approximation algorithms for the problem of multiprocessor scheduling under uncertainty (SUU), in which the execution of each job may fail probabilistically. This problem is motivated by the increasing use of distributed computing to handle large, computationally intensive tasks. In the SUU problem we are given n unit-length jobs and m machines, a directed acyclic graph G of precedence constraints among jobs, and unrelated failure probabilities q_ij for each job j when executed on machine i for a single timestep. Our goal is to find a schedule that minimizes the expected makespan.

Lin and Rajaraman gave the first approximations for this NP-hard problem for the special cases of independent jobs, precedence constraints forming disjoint chains, and precedence constraints forming trees. In this paper, we present asymptotically better approximation algorithms. In particular, we improve upon the previously best O(log n)-approximation, giving an O(log log(min {m,n}))-approximation in the case of independent jobs. We also give an O(log(n+m) log log(min{m,n}))-approximation algorithm for precedence constraints that form disjoint chains (improving on the previously best O(log(n)log(m) ^log(n+m) over _{log log(n+m)}-approximation by a (log n/log log n)² factor when n = m ^Θ(1)). Our algorithm for precedence constraints forming chains can also be used as a component for precedence constraints forming trees, yielding a similar improvement over the previously best algorithms for trees.

Our techniques include reducing SUU to a problem in stochastic scheduling, where machines must process a set of jobs with randomly distributed lengths. We show that our algorithms for (SUU) apply to a standard problem in this setting, giving the first approximation algorithms for preemptive stochastic scheduling on unrelated machines.

REFERENCES

• 1: David P. Anderson , Jeff Cobb , Eric Korpela , Matt Lebofsky , Dan Werthimer, SETI@home: an experiment in public-resource computing, Communications of the ACM, v.45 n.11, p.56-61, November 2002 [doi>10.1145/581571.581573]
• 2: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 3: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
• 4: L.R. Ford and D.R. Fulkerson. Flows in networks. Princeton University Press Princeton, NJ, 1962.
• 5: Simon French. Sequencing and Scheduling: An Introduction to the Mathematics of the Job-shop. Ellis Horwood, 1982.
• 6: David R. Karger, Clifford Stein, and Joel Wein. Scheduling algorithms. CRC Handbook of Computer Science, 1997.
• 7: V.S Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, and Aravind Srinivasan. Scheduling on Unrelated Machines Under Tree-Like Precedence Constraints. Proceedings of the eighth international workshop on approximation algorithms for combinatorial optimization problems, 2005.
• 8: E. L. Lawler , J. Labetoulle, On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming, Journal of the ACM (JACM), v.25 n.4, p.612-619, Oct. 1978 [doi>10.1145/322092.322101]
• 9: F. T. Leighton, Bruce M. Maggs, and Satish B. Rao. Packet routing and job-shop scheduling in o (Congestion + Dilation) steps. Combinatorica, 14(2):167--186, 1994.
• 10: Guolong Lin , Rajmohan Rajaraman, Approximation algorithms for multiprocessor scheduling under uncertainty, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248383]
• 11: Grzegorz Malewicz, Parallel scheduling of complex dags under uncertainty, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073981]
• 12: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 13: Michael L. Pinedo. Scheduling: Theory, Algorithms, and Systems. Prentice Hall Englewood Cliffs, NJ, 2002.
• 14: Paolo Serafini. Scheduling Jobs on Several Machines with the Job Splitting Property. Operations Research, 44(4):617--628, 1996.
• 15: David B. Shmoys , Clifford Stein , Joel Wein, Improved approximation algorithms for shop scheduling problems, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.148-157, January 28-30, 1991, San Francisco, California, United States
• 16: David B. Shmoys , Clifford Stein , Joel Wein, Improved Approximation Algorithms for Shop Scheduling Problems, SIAM Journal on Computing, v.23 n.3, p.617-632, June 1994 [doi>10.1137/S009753979222676X]
• 17: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 18: Gideon Weiss and Michael Pinedo. Scheduling Tasks with Exponential Service Times on Non-Identical Processors to Minimize Various Cost Functions. Journal of Applied Probability, 17(1):187--202, 1980.

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

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, multiprocessor scheduling, scheduling under uncertainty, stochastic scheduling