Skip to main content
SpringerLink
Log in

Scheduling on Unrelated Machines under Tree-Like Precedence Constraints

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We present polylogarithmic approximations for the R|prec|C max  and R|prec|∑ j w j C j problems, when the precedence constraints are “treelike”—i.e., when the undirected graph underlying the precedences is a forest. These are the first non-trivial generalizations of the job shop scheduling problem to scheduling with precedence constraints that are not just chains. These are also the first non-trivial results for the weighted completion time objective on unrelated machines with precedence constraints of any kind. We obtain improved bounds for the weighted completion time and flow time for the case of chains with restricted assignment—this generalizes the job shop problem to these objective functions. We use the same lower bound of “congestion + dilation”, as in other job shop scheduling approaches (e.g. Shmoys, Stein and Wein, SIAM J. Comput. 23, 617–632, 1994). The first step in our algorithm for the R|prec|C max  problem with treelike precedences involves using the algorithm of Lenstra, Shmoys and Tardos to obtain a processor assignment with the congestion + dilation value within a constant factor of the optimal. We then show how to generalize the random-delays technique of Leighton, Maggs and Rao to the case of trees. For the special case of chains, we show a dependent rounding technique which leads to a bicriteria approximation algorithm for minimizing the flow time, a notoriously hard objective function.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bertsimas, D., Teo, C.-P., Vohra, R.: On dependent randomized rounding algorithms. Oper. Res. Lett. 24(3), 105–114 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  2. Chekuri, C., Bender, M.: An efficient approximation algorithm for minimizing makespan on uniformly related machines. J. Algorithms 41, 212–224 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  3. Chekuri, C., Khanna, S.: Approximation algorithms for minimizing average weighted completion time. In: Leung, J. (ed.) Handbook of Scheduling: Algorithms, Models, and Performance Analysis, pp. 11-1–11-30. CRC Press (2004)

  4. Chekuri, C., Goel, A., Khanna, S., Kumar, A.: Multi-processor scheduling to minimize flow time with ε resource augmentation. In: STOC ’04: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, pp. 363–372 (2004)

  5. Chudak, F.A., Shmoys, D.B.: Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds. J. Algorithms 30(2), 323–343 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  6. Feige, U., Scheideler, C.: Improved bounds for acyclic job shop scheduling. Combinatorica 22, 361–399 (2002)

    Article  MathSciNet  Google Scholar 

  7. Goldberg, L.A., Paterson, M., Srinivasan, A., Sweedyk, E.: Better approximation guarantees for job-shop scheduling. SIAM J. Discret. Math. 14, 67–92 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  8. Hall, L.: Approximation algorithms for scheduling. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-Hard Problems. PWS Press (1997)

  9. Hall, L., Schulz, A., Shmoys, D.B., Wein, J.: Scheduling to minimize average completion time: offline and online algorithms. Math. Oper. Res. 22, 513–544 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  10. Jansen, K., Porkolab, L.: Improved approximation schemes for scheduling unrelated parallel machines. In: Proc. ACM Symposium on Theory of Computing (STOC), pp. 408–417 (1999)

  11. Jansen, K., Solis-Oba, R.: Scheduling jobs with chain precedence constraints. In: Parallel Processing and Applied Mathematics, PPAM. Lecture Notes in Computer Science, vol. 3019, pp. 105–112 (2003)

  12. Jansen, K., Solis-Oba, R., Sviridenko, M.: Makespan minimization in job shops: a polynomial time approximation scheme. In: Proc. ACM Symposium on Theory of Computing (STOC), pp. 394–399 (1999)

  13. Leighton, F.T., Maggs, B., Rao, S.: Packet routing and jobshop scheduling in O(congestion + dilation) steps. Combinatorica 14, 167–186 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  14. Leighton, F.T., Maggs, B., Richa, A.: Fast algorithms for finding O(congestion + dilation) packet routing schedules. Combinatorica 19, 375–401 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  15. Lenstra, J.K., Shmoys, D.B., Tardos, É.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46, 259–271 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  16. Leonardi, S., Raz, D.: Approximating total flow time on parallel machines. In: Proc. ACM Symposium on Theory of Computing, pp. 110–119 (1997)

  17. Lin, J.H., Vitter, J.S.: ε-approximations with minimum packing constraint violation. In: Proceedings of the ACM Symposium on Theory of Computing, pp. 771–782 (1992)

  18. Linial, N., Magen, A., Saks, M.E.: Trees and Euclidean metrics. In: Proceedings of the ACM Symposium on Theory of Computing, pp. 169–175 (1998)

  19. Panconesi, A., Srinivasan, A.: Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds. SIAM J. Comput. 26, 350–368 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  20. Queyranne, M., Sviridenko, M.: Approximation algorithms for shop scheduling problems with minsum objective. J. Sched. 5, 287–305 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  21. Schulz, A., Skutella, M.: The power of α-points in preemptive single machine scheduling. J. Sched. 5(2), 121–133 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  22. Shmoys, D.B., Stein, C., Wein, J.: Improved approximation algorithms for shop scheduling problems. SIAM J. Comput. 23, 617–632 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  23. Skutella, M.: Convex quadratic and semidefinite relaxations in scheduling. J. ACM 46(2), 206–242 (2001)

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Virginia Bioinformatics Institute and Department of Computer Science, Virginia Tech., Blacksburg, VT, 24061, USA

    V. S. Anil Kumar & Madhav V. Marathe

  2. IBM T.J. Watson Research Center, Yorktown Heights, NY, 10598, USA

    Srinivasan Parthasarathy

  3. Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, MD, 20742, USA

    Aravind Srinivasan

Authors
  1. V. S. Anil Kumar
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Madhav V. Marathe
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Srinivasan Parthasarathy
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Aravind Srinivasan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to V. S. Anil Kumar.

Additional information

A preliminary version of this paper appeared in the Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 146–157, 2005.

V.S. Anil Kumar supported in part by NSF Award CNS-0626964. Part of this work was done while at the Los Alamos National Laboratory, and supported in part by the Department of Energy under Contract W-7405-ENG-36.

M.V. Marathe supported in part by NSF Award CNS-0626964. Part of this work was done while at the Los Alamos National Laboratory, and supported in part by the Department of Energy under Contract W-7405-ENG-36.

Part of this work by S. Parthasarathy was done while at the Department of Computer Science, University of Maryland, College Park, MD 20742, and in part while visiting the Los Alamos National Laboratory. Research supported in part by NSF Award CCR-0208005 and NSF ITR Award CNS-0426683.

Research of A. Srinivasan supported in part by NSF Award CCR-0208005, NSF ITR Award CNS-0426683, and NSF Award CNS-0626636.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Anil Kumar, V.S., Marathe, M.V., Parthasarathy, S. et al. Scheduling on Unrelated Machines under Tree-Like Precedence Constraints. Algorithmica 55, 205–226 (2009). https://doi.org/10.1007/s00453-007-9004-y

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-007-9004-y

Keywords

Search

Navigation