Approximation algorithms for multiprocessor scheduling under uncertainty

ABSTRACT

Motivated by applications in grid computing and project management, we study multiprocessor scheduling in scenarios where there is uncertainty in the successful execution of jobs when assigned to processors. We consider the problem of multiprocessor scheduling under uncertainty, in which we are given n unit-time jobs and m machines, a directed acyclic graph C giving the dependencies among the jobs, and for every job j and machine i, the probability p_ij of the successful completion of job j when scheduled on machine i in any given particular step. The goal of the problem is to find a schedule that minimizes the expected makespan, that is, the expected completion time of all the jobs.

The problem of multiprocessor scheduling under uncertainty was introduced by Malewicz and was shown to be NP-hard even when all the jobs are independent. In this paper, we present polynomial-time approximation algorithms for the problem, for special cases of the dag C. We obtain an O(log n)-approximation for the case of independent jobs, an O(log m log n log(n + m)/ log log(n + m))-approximation when C is a collection of disjoint chains, an O(log m log² n)-approximation when C is a collection of directed out- or in-trees, and an O(log m log² n log(n + m)/ log log(n + m))-approximation when C is a directed forest.

REFERENCES

• 1: D. Applegate and B. Cook. A computational study of the job-shop scheduling problem. ORSA Journal of Computing, 3(2):149--156, 1991.
• 2: Dimitris Bertsimas , John Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997
• 3: H. Chernoff. A measure of the asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics, 23:493--509, 1952.
• 4: Fabián A. Chudak , David B. Shmoys, Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds, Journal of Algorithms, v.30 n.2, p.323-343, Feb. 1999 [doi>10.1006/jagm.1998.0987]
• 5: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 6: A. Fernandez, R. Armacost, and J. Pet-Edwards. A model for the resource constrained project scheduling problem with stochastic task durations. In 7th Industrial Engineering Research Conference Proceedings, 1998.
• 7: A. Fernandez, R. Armacost, and J. Pet-Edwards. Understanding simulation solutions to resource constrained project scheduling problems with stochastic task durations. Engineering Management Journal, 10(4):5--13, 1998.
• 8: L. R. Ford, Jr. and D. R. Fulkerson. Flows in Networks. Princeton University Press, Princeton, 1962.
• 9: Ian Foster , Carl Kesselman, The Grid 2: Blueprint for a New Computing Infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 10: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 11: Ashish Goel , Piotr Indyk, Stochastic Load Balancing and Related Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.579, October 17-18, 1999
• 12: R. L. Graham. Bounds for certain multiprocessing anomalies. Bell System Technical Journal (BSTJ), 45:1563--1581, 1966.
• 13: Leslie A. Hall, Approximation algorithms for scheduling, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 14: W. Herroelen and R. Leus. Project scheduling under uncertainty: Survey and research potentials. European Journal of Operational Research, 165(2):289--306, 2005.
• 15: W. Hoeffding. On the distribution of the number of successes in independent trials. Annals of Mathematical Statistics, 27:713--721, 1956.
• 16: Jon Kleinberg , Yuval Rabani , Éva Tardos, Allocating Bandwidth for Bursty Connections, SIAM Journal on Computing, v.30 n.1, p.191-217, 2000 [doi>10.1137/S0097539797329142]
• 17: V. Kumar, M. Marathe, S. Parthasarathy, and A. Srinivasan. Scheduling on unrelated machines under tree-like precedence constraints. In International Workshop on Approximation Algorithms for Combinatorial Optimization, 2005.
• 18: E. L. Lawler, J. K. Lenstra, A. R. Kan, and D. B. Shmoys. Sequencing and scheduling: Algorithms and complexity. Technical Report BS-R8909, Centre for Mathematics and Computer Science., Amsterdam, 1991.
• 19: F. T. Leighton, B. M. Maggs, and S. Rao. Packet routing and job-shop scheduling in O (congestion + dilation) steps. Combinatorica, 14(2):167--186, 1994.
• 20: 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]
• 21: G. Lin and R. Rajaraman. Approximation algorithms for multiprocessor scheduling under uncertainty. Technical report, arXiv, March 2007. http://arxiv.org/abs/cs/0703100.
• 22: 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]
• 23: Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988 [doi>10.1016/0022-0000(88)90003-7]
• 24: P Raghavan , C D Thompson, Provably good routing in graphs: regular arrays, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.79-87, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22154]
• 25: Prabhakar Raghavan , Clark D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, v.7 n.4, p.365-374, Dec, 1987 [doi>10.1007/BF02579324]
• 26: Jeanette P. Schmidt , Alan Siegel , Aravind Srinivasan, Chernoff-Hoeffding Bounds for Applications with Limited Independence, SIAM Journal on Discrete Mathematics, v.8 n.2, p.223-250, May 1995 [doi>10.1137/S089548019223872X]
• 27: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 28: 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]
• 29: Martin Skutella, Convex quadratic and semidefinite programming relaxations in scheduling, Journal of the ACM (JACM), v.48 n.2, p.206-242, March 2001 [doi>10.1145/375827.375840]
• 30: Martin Skutella , Marc Uetz, Scheduling precedence-constrained jobs with stochastic processing times on parallel machines, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.589-590, January 07-09, 2001, Washington, D.C., United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, multiprocessor scheduling