×

Approximation algorithms for multiprocessor scheduling under uncertainty. (English) Zbl 1213.68151

Summary: 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 time at which all of the jobs are completed.
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 ^{2} n)\)-approximation when \(C\) is a collection of directed out- or in-trees, and an \(O(\log m \log^{2} n \log (n+m)/\log \log (n+m))\)-approximation when \(C\) is a directed forest.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68W25 Approximation algorithms

Software:

JOBSHOP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Applegate, D., Cook, B.: A computational study of the job-shop scheduling problem. ORSA J. Comput. 3(2), 149–156 (1991) · Zbl 0755.90039
[2] Bertsimas, D., Tsitsiklis, J.: Introduction to Linear Optimization. Athena Scientific, Nashua (1997)
[3] Chernoff, H.: A measure of the asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Stat. 23, 493–509 (1952) · Zbl 0048.11804 · doi:10.1214/aoms/1177729330
[4] Chudak, F., Shmoys, D.: Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds. J. Algorithms 30 (1999) · Zbl 0923.68012
[5] Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press and McGraw-Hill, Cambridge (2001) · Zbl 1047.68161
[6] Crutchfield, C., Dzunic, Z., Fineman, J., Karger, D., Scott, J.: Improved approximations for multiprocessor scheduling under uncertainty. In: Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Munich, Germany, pp. 246–255 (2008)
[7] Fernandez, A., Armacost, R., Pet-Edwards, J.: A model for the resource constrained project scheduling problem with stochastic task durations. In: 7th Industrial Engineering Research Conference Proceedings (1998)
[8] Fernandez, A., Armacost, R., Pet-Edwards, J.: Understanding simulation solutions to resource constrained project scheduling problems with stochastic task durations. Eng. Manag. J. 10(4), 5–13 (1998)
[9] Ford Jr., L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962) · Zbl 0106.34802
[10] Foster, I., Kesselman, C. (eds.): The Grid: Blueprint for a New Computing Infrastructure, 2nd edn. Morgan Kaufmann, San Francisco (2004)
[11] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman, San Francisco (1979) · Zbl 0411.68039
[12] Goel, A., Indyk, P.: Stochastic load balancing and related problems. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS) (1999)
[13] Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. (BSTJ) 45, 1563–1581 (1966) · Zbl 0168.40703
[14] Hall, L.: Approximation algorithms for scheduling. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-hard Problems. PWS, Boston (1997)
[15] Herroelen, W., Leus, R.: Project scheduling under uncertainty: Survey and research potentials. Eur. J. Oper. Res. 165(2), 289–306 (2005) · Zbl 1066.90050 · doi:10.1016/j.ejor.2004.04.002
[16] Hoeffding, W.: On the distribution of the number of successes in independent trials. Ann. Math. Stat. 27, 713–721 (1956) · Zbl 0073.13902 · doi:10.1214/aoms/1177728178
[17] Kleinberg, J., Rabani, Y., Tardos, E.: Allocating bandwidth for bursty connections. SIAM J. Comput. 30 (2000) · Zbl 0979.05098
[18] Kumar, V., Marathe, M., Parthasarathy, S., Srinivasan, A.: Scheduling on unrelated machines under tree-like precedence constraints. In: International Workshop on Approximation Algorithms for Combinatorial Optimization (2005) · Zbl 1142.90403
[19] Lawler, E.L., Lenstra, J.K., Kan, A.R., Shmoys, D.B.: Sequencing and scheduling: Algorithms and complexity. Technical Report BS-R8909, Centre for Mathematics and Computer Science, Amsterdam (1991)
[20] Leighton, F.T., Maggs, B.M., Rao, S.: Packet routing and job-shop scheduling in O (congestion + dilation) steps. Combinatorica 14(2), 167–186 (1994) · Zbl 0811.68062 · doi:10.1007/BF01215349
[21] Lenstra, J., Shmoys, D., Tardos, E.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46 (1990) · Zbl 0715.90063
[22] Lin, G., Rajaraman, R.: Approximation algorithms for multiprocessor scheduling under uncertainty. In: Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 25–34, San Diego, CA, USA (2007)
[23] Lin, G., Rajaraman, R.: Approximation algorithms for multiprocessor scheduling under uncertainty. Technical report, March 2007. arXiv:cs/0703100v1 · Zbl 1213.68151
[24] Malewicz, G.: Parallel scheduling of complex dags under uncertainty. In: Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 66–75, Las Vegas, Nevada, USA (2005)
[25] Pinedo, M.: Scheduling: Theory, Algorithms, and Systems. Prentice Hall, Englewood Cliffs (2002) · Zbl 1145.90394
[26] Raghavan, P.: Probabilistic construction of deterministic algorithms: Approximating packing integer programs. J. Comput. Syst. Sci. 37 (1988) · Zbl 0659.90066
[27] Raghavan, P., Thompson, C.: Provably good routing in graphs: Regular arrays. In: ACM Symposium on Theory of Computing (STOC) (1985)
[28] Raghavan, P., Thompson, C.: Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica 7 (1987) · Zbl 0651.90052
[29] Schmidt, J., Siegel, A., Srinivasan, A.: Chernoff-Hoeffding bounds for applications with limited independence. SIAM J. Discrete Math. 8 (1995) · Zbl 0819.60032
[30] Schrijver, A.: Theory of Linear and Integer Programming. Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1986) · Zbl 0665.90063
[31] Shmoys, D., Stein, C., Wein, J.: Improved approximation algorithms for shop scheduling problems. SIAM J. Comput. 23 (1994) · Zbl 0814.68026
[32] Skutella, M.: Convex quadratic and semidefinite programming relaxations in scheduling. J. Assoc. Comput. Mach. (JACM) 48(2), 206–242 (2001) · Zbl 1323.90024 · doi:10.1145/375827.375840
[33] Skutella, M., Uetz, M.: Scheduling precedence-constrained jobs with stochastic processing times on parallel machines. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 589–590, Washington, DC, USA (2001) · Zbl 1018.90016
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.