Document Open Access Logo

Non-Clairvoyant Precedence Constrained Scheduling

Authors Naveen Garg, Anupam Gupta, Amit Kumar, Sahil Singla

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.63.pdf
  • Filesize: 464 kB
  • 14 pages

Document Identifiers

Author Details

Naveen Garg
  • Computer Science and Engineering Department, Indian Institute of Technology, Delhi, India
Anupam Gupta
  • Computer Science Department, Carnegie Mellon University, USA
Amit Kumar
  • Computer Science and Engineering Department, Indian Institute of Technology, Delhi, India
Sahil Singla
  • Princeton University and Institute for Advanced Study, USA

Funding

This research was supported in part by NSF awards CCF-1536002, CCF-1540541, and CCF-1617790, and the Indo-US Joint Center for Algorithms Under Uncertainty. Sahil Singla was supported in part by the Schmidt Foundation.

Cite AsGet BibTex

Naveen Garg, Anupam Gupta, Amit Kumar, and Sahil Singla. Non-Clairvoyant Precedence Constrained Scheduling. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 63:1-63:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.63

Abstract

We consider the online problem of scheduling jobs on identical machines, where jobs have precedence constraints. We are interested in the demanding setting where the jobs sizes are not known up-front, but are revealed only upon completion (the non-clairvoyant setting). Such precedence-constrained scheduling problems routinely arise in map-reduce and large-scale optimization. For minimizing the total weighted completion time, we give a constant-competitive algorithm. And for total weighted flow-time, we give an O(1/epsilon^2)-competitive algorithm under (1+epsilon)-speed augmentation and a natural "no-surprises" assumption on release dates of jobs (which we show is necessary in this context). Our algorithm proceeds by assigning virtual rates to all waiting jobs, including the ones which are dependent on other uncompleted jobs. We then use these virtual rates to decide on the actual rates of minimal jobs (i.e., jobs which do not have dependencies and hence are eligible to run). Interestingly, the virtual rates are obtained by allocating time in a fair manner, using a Eisenberg-Gale-type convex program (which we can solve optimally using a primal-dual scheme). The optimality condition of this convex program allows us to show dual-fitting proofs more easily, without having to guess and hand-craft the duals. This idea of using fair virtual rates may have broader applicability in scheduling problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
  • Theory of computation → Scheduling algorithms
Keywords
  • Online algorithms
  • Scheduling
  • Primal-Dual analysis
  • Nash welfare

Metrics

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

Related Versions

References

  1. Kunal Agrawal, Jing Li, Kefu Lu, and Benjamin Moseley. Scheduling Parallel DAG Jobs Online to Minimize Average Flow Time. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 176-189, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch14.
  2. S. Anand, Naveen Garg, and Amit Kumar. Resource augmentation for weighted flow-time explained by dual fitting. In SODA'12, pages 1228-1241. ACM, New York, 2012. Google Scholar
  3. Abbas Bazzi and Ashkan Norouzi-Fard. Towards Tight Lower Bounds for Scheduling Problems. In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pages 118-129, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_11.
  4. Fabián A. Chudak and David B. Shmoys. Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds. J. Algorithms, 30(2):323-343, 1999. URL: http://dx.doi.org/10.1006/jagm.1998.0987.
  5. Jeff Edmonds. Scheduling in the Dark. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, May 1-4, 1999, Atlanta, Georgia, USA, pages 179-188, 1999. URL: http://dx.doi.org/10.1145/301250.301299.
  6. Jeff Edmonds, Donald D. Chinn, Tim Brecht, and Xiaotie Deng. Non-clairvoyant Multiprocessor Scheduling of Jobs with Changing Execution Characteristics (Extended Abstract). In Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, pages 120-129, 1997. URL: http://dx.doi.org/10.1145/258533.258565.
  7. Jeff Edmonds and Kirk Pruhs. Scalably scheduling processes with arbitrary speedup curves. ACM Trans. Algorithms, 8(3):Art. 28, 10, 2012. URL: http://dx.doi.org/10.1145/2229163.2229172.
  8. R. L. Graham. Bounds for Certain Multiprocessing Anomalies. Bell System Technical Journal, 45(9):1563-1581, 1966. URL: http://dx.doi.org/10.1002/j.1538-7305.1966.tb01709.x.
  9. Robert Grandl, Srikanth Kandula, Sriram Rao, Aditya Akella, and Janardhan Kulkarni. GRAPHENE: packing and dependency-aware scheduling for data-parallel clusters. In 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016, Savannah, GA, USA, November 2-4, 2016., pages 81-97, 2016. URL: https://www.usenix.org/conference/osdi16/technical-sessions/presentation/grandl_graphene.
  10. Anupam Gupta, Ravishankar Krishnaswamy, and Kirk Pruhs. Online Primal-Dual for Non-linear Optimization with Applications to Speed Scaling. In Approximation and Online Algorithms - 10th International Workshop, WAOA 2012, Ljubljana, Slovenia, September 13-14, 2012, Revised Selected Papers, pages 173-186, 2012. URL: http://dx.doi.org/10.1007/978-3-642-38016-7_15.
  11. Leslie A. Hall, Andreas S. Schulz, David B. Shmoys, and Joel Wein. Scheduling to minimize average completion time: off-line and on-line approximation algorithms. Math. Oper. Res., 22(3):513-544, 1997. URL: http://dx.doi.org/10.1287/moor.22.3.513.
  12. Sungjin Im, Janardhan Kulkarni, and Kamesh Munagala. Competitive Algorithms from Competitive Equilibria: Non-Clairvoyant Scheduling under Polyhedral Constraints. J. ACM, 65(1):3:1-3:33, 2018. URL: http://dx.doi.org/10.1145/3136754.
  13. Sungjin Im, Janardhan Kulkarni, Kamesh Munagala, and Kirk Pruhs. SelfishMigrate: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 531-540, 2014. Google Scholar
  14. Bala Kalyanasundaram and Kirk Pruhs. Speed is as powerful as clairvoyance. J. ACM, 47(4):617-643, 2000. Google Scholar
  15. Janardhan Kulkarni and Shi Li. Flow-time Optimization for Concurrent Open-Shop and Precedence Constrained Scheduling Models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, August 20-22, 2018 - Princeton, NJ, USA, pages 16:1-16:21, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.16.
  16. Shi Li. Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations. In 58th Annual IEEE Symposium on Foundations of Computer Science - FOCS 2017, pages 283-294. IEEE Computer Soc., Los Alamitos, CA, 2017. Google Scholar
  17. Rajeev Motwani, Steven Phillips, and Eric Torng. Nonclairvoyant scheduling. Theorertical Computer Science, 130(1):17-47, 1994. Google Scholar
  18. Alix Munier, Maurice Queyranne, and Andreas S. Schulz. Approximation bounds for a general class of precedence constrained parallel machine scheduling problems. In Integer programming and combinatorial optimization (Houston, TX, 1998), volume 1412 of Lecture Notes in Comput. Sci., pages 367-382. Springer, Berlin, 1998. URL: http://dx.doi.org/10.1007/3-540-69346-7_28.
  19. John F. Nash. The Bargaining Problem. Econometrica, 18(2):155-162, 1950. URL: http://www.jstor.org/stable/1907266.
  20. Julien Robert and Nicolas Schabanel. Non-clairvoyant scheduling with precedence constraints. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, pages 491-500, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347136.
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 Imprint Privacy Contact