Document Open Access Logo

An Improved Approximation Algorithm for Scheduling Under Arborescence Precedence Constraints

Author Nguyễn Kim Thắng

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.84.pdf
  • Filesize: 484 kB
  • 12 pages

Document Identifiers

Author Details

Nguyễn Kim Thắng
  • IBISC, Univ Evry, University Paris Saclay, Evry, France

Funding

Research supported by the ANR project OATA nsuperscript{o} ANR-15-CE40-0015-01.

Cite As Get BibTex

Nguyễn Kim Thắng. An Improved Approximation Algorithm for Scheduling Under Arborescence Precedence Constraints. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 84:1-84:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.MFCS.2020.84

Abstract

We consider a scheduling problem on unrelated machines with precedence constraints. There are m unrelated machines and n jobs and every job has to be processed non-preemptively in some machine. Moreover, jobs have precedence constraints; specifically, a precedence constraint j ≺ j' requires that job j' can only be started whenever job j has been completed. The objective is to minimize the total completion time. 
The problem has been widely studied in more restricted machine environments such as identical or related machines. However, for unrelated machines, much less is known. In the paper, we study the problem where the precedence constraints form a forest of arborescences. We present a O((log n)² / (log log n)³)-approximation algorithm - that improves the best-known guarantee of O((log n)² / log log n) due to Kumar et al. a decade ago. The analysis relies on a dual-fitting method in analyzing the Lagrangian function of non-convex programs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Scheduling
  • Precedence Constraints
  • Lagrangian Duality

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Anand, Naveen Garg, and Amit Kumar. Resource augmentation for weighted flow-time explained by dual fitting. In Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms, pages 1228-1241, 2012. Google Scholar
  2. Nikhil Bansal and Subhash Khot. Optimal long code test with one free bit. In Proc. 50th Symposium on Foundations of Computer Science, pages 453-462, 2009. Google Scholar
  3. Abbas Bazzi and Ashkan Norouzi-Fard. Towards tight lower bounds for scheduling problems. In Proc. 23rd European Symposium on Algorithms, pages 118-129, 2015. Google Scholar
  4. Soumen Chakrabarti, Cynthia A Phillips, Andreas S Schulz, David B Shmoys, Cliff Stein, and Joel Wein. Improved scheduling algorithms for minsum criteria. In Proc. Colloquium on Automata, Languages, and Programming, pages 646-657, 1996. Google Scholar
  5. Chandra Chekuri and Sanjeev Khanna. Approximation algorithms for minimizing average weighted completion time. In Handbook of Scheduling, pages 220-249. Chapman and Hall/CRC, 2004. Google Scholar
  6. Fabián A Chudak and David B Shmoys. Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds. Journal of Algorithms, 30(2):323-343, 1999. Google Scholar
  7. Shashwat Garg. Quasi-ptas for scheduling with precedences using lp hierarchies. In Proc. 45th Colloquium on Automata, Languages, and Programming, 2018. Google Scholar
  8. Shashwat Garg, Janardhan Kulkarni, and Shi Li. Lift and project algorithms for precedence constrained scheduling to minimize completion time. In Proc. 30th Symposium on Discrete Algorithms, pages 1570-1584, 2019. Google Scholar
  9. Ronald L Graham, Eugene L Lawler, Jan Karel Lenstra, and AHG Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5:287-326, 1979. Google Scholar
  10. Han Hoogeveen, Petra Schuurman, and Gerhard J Woeginger. Non-approximability results for scheduling problems with minsum criteria. INFORMS Journal on Computing, 13(2):157-168, 2001. Google Scholar
  11. Klaus Jansen, Roberto Solis-Oba, and Maxim Sviridenko. Makespan minimization in job shops: a polynomial time approximation scheme. In Proc. Symposium on Theory of Computing, volume 99, pages 394-399, 1999. Google Scholar
  12. Anil Kumar, Madhav Marathe, Srinivasan Parthasarathy, and Aravind Srinivasan. Scheduling on unrelated machines under tree-like precedence constraints. Algorithmica, 55(1):205-226, 2009. Google Scholar
  13. Jan Karel Lenstra and AHG Rinnooy Kan. Complexity of scheduling under precedence constraints. Operations Research, 26(1):22-35, 1978. Google Scholar
  14. Elaine Levey and Thomas Rothvoss. A (1+ epsilon)-approximation for makespan scheduling with precedence constraints using lp hierarchies. In Proc. 48th Symposium on Theory of Computing, pages 168-177, 2016. Google Scholar
  15. Shi Li. Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations. In Proc. 58th Symposium on Foundations of Computer Science (FOCS), pages 283-294, 2017. Google Scholar
  16. Alix Munier, Maurice Queyranne, and Andreas S Schulz. Approximation bounds for a general class of precedence constrained parallel machine scheduling problems. In Proc. Conference on Integer Programming and Combinatorial Optimization, pages 367-382, 1998. Google Scholar
  17. David B Shmoys, Clifford Stein, and Joel Wein. Improved approximation algorithms for shop scheduling problems. SIAM Journal on Computing, 23(3):617-632, 1994. Google Scholar
  18. Martin Skutella. A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective. Operations Research Letters, 44(5):676-679, 2016. Google Scholar
  19. Ola Svensson. Hardness of precedence constrained scheduling on identical machines. SIAM Journal on Computing, 40(5):1258-1274, 2011. Google Scholar
  20. Nguyen Kim Thang. Lagrangian duality in online scheduling with resource augmentation and speed scaling. In Proc. 21st European Symposium on Algorithms, pages 755-766, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact