Document Open Access Logo

Flow-time Optimization for Concurrent Open-Shop and Precedence Constrained Scheduling Models

Authors Janardhan Kulkarni, Shi Li

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.16.pdf
  • Filesize: 0.5 MB
  • 21 pages

Document Identifiers

Author Details

Janardhan Kulkarni
  • Microsoft Research, Redmond, WA, USA
Shi Li
  • Department of Computer Science and Engineering, University at Buffalo, Buffalo, NY, USA

Funding

  • Li, Shi: The work of the author is in part supported by NSF grants CCF-1566356 and CCF-1717134.

Cite AsGet BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.16

Abstract

Scheduling a set of jobs over a collection of machines is a fundamental problem that needs to be solved millions of times a day in various computing platforms: in operating systems, in large data clusters, and in data centers. Along with makespan, flow-time, which measures the length of time a job spends in a system before it completes, is arguably the most important metric to measure the performance of a scheduling algorithm. In recent years, there has been a remarkable progress in understanding flow-time based objective functions in diverse settings such as unrelated machines scheduling, broadcast scheduling, multi-dimensional scheduling, to name a few. Yet, our understanding of the flow-time objective is limited mostly to the scenarios where jobs have no dependencies. On the other hand, in almost all real world applications, think of MapReduce settings for example, jobs have dependencies that need to be respected while making scheduling decisions. In this paper, we take first steps towards understanding this complex problem. In particular, we consider two classical scheduling problems that capture dependencies across jobs: 1) concurrent open-shop scheduling (COSSP) and 2) precedence constrained scheduling. Our main motivation to study these problems specifically comes from their relevance to two scheduling problems that have gained importance in the context of data centers: co-flow scheduling and DAG scheduling. We design almost optimal approximation algorithms for COSSP and PCSP, and show hardness results.

Subject Classification

ACM Subject Classification
  • Theory of computation → Scheduling algorithms
Keywords
  • Approximation
  • Weighted Flow Time
  • Concurrent Open Shop
  • Precedence Constraints

Metrics

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

Related Versions

References

  1. Apache hadoop. Google Scholar
  2. 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.
  3. Reza Ahmadi, Uttarayan Bagchi, and Thomas A Roemer. Coordinated scheduling of customer orders for quick response. Naval Research Logistics (NRL), 52(6):493-512, 2005. Google Scholar
  4. Saba Ahmadi, Samir Khuller, Manish Purohit, and Sheng Yang. On scheduling coflows. In International Conference on Integer Programming and Combinatorial Optimization, pages 13-24. Springer, 2017. Google Scholar
  5. S. Anand, Naveen Garg, and Amit Kumar. Resource augmentation for weighted flow-time explained by dual fitting. In SODA, pages 1228-1241, 2012. URL: http://portal.acm.org/citation.cfm?id=2095213&CFID=63838676&CFTOKEN=79617016.
  6. Nikhil Bansal, Ho-Leung Chan, Rohit Khandekar, Kirk Pruhs, Cliff Stein, and Baruch Schieber. Non-preemptive min-sum scheduling with resource augmentation. In Foundations of Computer Science, 2007. FOCS'07. 48th Annual IEEE Symposium on, pages 614-624. IEEE, 2007. Google Scholar
  7. Nikhil Bansal, Moses Charikar, Ravishankar Krishnaswamy, and Shi Li. Better algorithms and hardness for broadcast scheduling via a discrepancy approach. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 55-71. Society for Industrial and Applied Mathematics, 2014. Google Scholar
  8. Nikhil Bansal and Subhash Khot. Inapproximability of hypergraph vertex cover and applications to scheduling problems. Automata, Languages and Programming, pages 250-261, 2010. Google Scholar
  9. Nikhil Bansal, Ravishankar Krishnaswamy, and Viswanath Nagarajan. Better scalable algorithms for broadcast scheduling. In ICALP (1), pages 324-335, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14165-2_28.
  10. Nikhil Bansal and Janardhan Kulkarni. Minimizing flow-time on unrelated machines. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 851-860, 2015. URL: http://dx.doi.org/10.1145/2746539.2746601.
  11. Nikhil Bansal and Kirk Pruhs. The geometry of scheduling. In IEEE Symposium on the Foundations of Computer Science, pages 407-414, 2010. Google Scholar
  12. Nikhil Bansal and Kirk Pruhs. Weighted geometric set multi-cover via quasi-uniform sampling. In European Symposium on Algorithms, pages 145-156. Springer, 2012. Google Scholar
  13. Jatin Batra, Naveen Garg, and Amit Kumar. Constant factor approximation algorithm for weighted flow time on a single machine in pseudo-polynomial time. CoRR, abs/1802.07439, 2018. Google Scholar
  14. Robert D Carr, Lisa Fleischer, Vitus J Leung, and Cynthia A Phillips. Strengthening integrality gaps for capacitated network design and covering problems. In SODA, pages 106-115, 2000. Google Scholar
  15. Timothy M Chan, Elyot Grant, Jochen Könemann, and Malcolm Sharpe. Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1576-1585. Society for Industrial and Applied Mathematics, 2012. Google Scholar
  16. Zhi-Long Chen and Nicholas G Hall. Supply chain scheduling: Conflict and cooperation in assembly systems. Operations Research, 55(6):1072-1089, 2007. Google Scholar
  17. Mosharaf Chowdhury and Ion Stoica. Coflow: A networking abstraction for cluster applications. In Proceedings of the 11th ACM Workshop on Hot Topics in Networks, pages 31-36. ACM, 2012. Google Scholar
  18. Mosharaf Chowdhury and Ion Stoica. Efficient coflow scheduling without prior knowledge. In ACM SIGCOMM Computer Communication Review, volume 45, pages 393-406. ACM, 2015. Google Scholar
  19. Mosharaf Chowdhury, Yuan Zhong, and Ion Stoica. Efficient coflow scheduling with varys. In ACM SIGCOMM Computer Communication Review, volume 44, pages 443-454. ACM, 2014. Google Scholar
  20. Nikhil Devanur and Janardhan Kulkarni. A unified rounding algorithm for unrelated machines scheduling. In Preprint, https://users.cs.duke.edu/ kulkarni/papers/tardines.pdf, 2017. Google Scholar
  21. Devdatta Gangal and Abhiram Ranade. Precedence constrained scheduling in (2-(7/3)p+1)⋅ optimal. Journal of Computer and System Sciences, 74(7):1139-1146, 2008. Google Scholar
  22. Naveen Garg and Amit Kumar. Minimizing average flow-time : Upper and lower bounds. In FOCS, pages 603-613, 2007. URL: http://dx.doi.org/10.1109/FOCS.2007.42.
  23. Naveen Garg, Amit Kumar, and Vinayaka Pandit. Order scheduling models: hardness and algorithms. FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, pages 96-107, 2007. Google Scholar
  24. Ronald L Graham. Bounds for certain multiprocessing anomalies. Bell Labs Technical Journal, 45(9):1563-1581, 1966. Google Scholar
  25. Robert Grandl, Mosharaf Chowdhury, Aditya Akella, and Ganesh Ananthanarayanan. Altruistic scheduling in multi-resource clusters. In OSDI, pages 65-80, 2016. Google Scholar
  26. 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.
  27. Sungjin Im, Janardhan Kulkarni, and Kamesh Munagala. Competitive algorithms from competitive equilibria: non-clairvoyant scheduling under polyhedral constraints. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 313-322, 2014. URL: http://dx.doi.org/10.1145/2591796.2591814.
  28. Sungjin Im, Janardhan Kulkarni, and Kamesh Munagala. Competitive flow time algorithms for polyhedral scheduling. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 506-524, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.38.
  29. 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. URL: http://dx.doi.org/10.1109/FOCS.2014.63.
  30. Sungjin Im, Shi Li, Benjamin Moseley, and Eric Torng. A dynamic programming framework for non-preemptive scheduling problems on multiple machines. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1070-1086. Society for Industrial and Applied Mathematics, 2015. Google Scholar
  31. Sungjin Im and Benjamin Moseley. Online scalable algorithm for minimizing ;k-norms of weighted flow time on unrelated machines. In SODA, pages 95-108, 2011. URL: http://www.siam.org/proceedings/soda/2011/SODA11_008_ims.pdf.
  32. Sungjin Im and Benjamin Moseley. An online scalable algorithm for average flow time in broadcast scheduling. ACM Transactions on Algorithms, 8(4):39, 2012. URL: http://dx.doi.org/10.1145/2344422.2344429.
  33. Sungjin Im and Benjamin Moseley. General profit scheduling and the power of migration on heterogeneous machines. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016, Asilomar State Beach/Pacific Grove, CA, USA, July 11-13, 2016, pages 165-173, 2016. Google Scholar
  34. Bala Kalyanasundaram and Kirk Pruhs. Speed is as powerful as clairvoyance. Journal of the ACM, 47(4):617-643, 2000. Google Scholar
  35. Bala Kalyanasundaram and Kirk R Pruhs. Eliminating migration in multi-processor scheduling. Journal of Algorithms, 38(1):2-24, 2001. Google Scholar
  36. Samir Khuller and Manish Purohit. Brief announcement: Improved approximation algorithms for scheduling co-flows. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, pages 239-240. ACM, 2016. Google Scholar
  37. Shui Lam and Ravi Sethi. Worst case analysis of two scheduling algorithms. SIAM Journal on Computing, 6(3):518-536, 1977. Google Scholar
  38. J. K. Lenstra and A. H. G. Rinnooy Kan. Complexity of scheduling under precedence constraints. Oper. Res., 26(1):22-35, 1978. URL: http://dx.doi.org/10.1287/opre.26.1.22.
  39. Joseph Y-T Leung, Haibing Li, and Michael Pinedo. Scheduling orders for multiple product types to minimize total weighted completion time. Discrete Applied Mathematics, 155(8):945-970, 2007. Google Scholar
  40. Elaine Levey and Thomas Rothvoss. A (1+ epsilon)-approximation for makespan scheduling with precedence constraints using lp hierarchies. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 168-177. ACM, 2016. Google Scholar
  41. Shi Li. Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations. In Proceedings of the 2017 IEEE 58rd Annual Symposium on Foundations of Computer Science, FOCS '17, 2017. Google Scholar
  42. Pasin Manurangsi. Almost-polynomial ratio eth-hardness of approximating densest k-subgraph. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 954-961, 2017. URL: http://dx.doi.org/10.1145/3055399.3055412.
  43. Monaldo Mastrolilli, Maurice Queyranne, Andreas S Schulz, Ola Svensson, and Nelson A Uhan. Minimizing the sum of weighted completion times in a concurrent open shop. Operations Research Letters, 38(5):390-395, 2010. Google Scholar
  44. Jiří Matoušek. Lectures on discrete geometry, volume 212. Springer Science &Business Media, 2002. Google Scholar
  45. Alix Munier, Maurice Queyranne, and Andreas S. Schulz. Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems, pages 367-382. Springer Berlin Heidelberg, Berlin, Heidelberg, 1998. URL: http://dx.doi.org/10.1007/3-540-69346-7_28.
  46. Zhen Qiu, Cliff Stein, and Yuan Zhong. Minimizing the total weighted completion time of coflows in datacenter networks. In Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures, pages 294-303. ACM, 2015. Google Scholar
  47. Maurice Queyranne and Andreas S. Schulz. Approximation bounds for a general class of precedence constrained parallel machine scheduling problems. SIAM J. Comput., 35(5):1241-1253, 2006. URL: http://dx.doi.org/10.1137/S0097539799358094.
  48. Mehrnoosh Shafiee and Javad Ghaderi. An improved bound for minimizing the total weighted completion time of coflows in datacenters. arXiv preprint arXiv:1704.08357, 2017. Google Scholar
  49. Ola Svensson. Conditional hardness of precedence constrained scheduling on identical machines. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 745-754. ACM, 2010. Google Scholar
  50. Kasturi Varadarajan. Epsilon nets and union complexity. In Proceedings of the twenty-fifth annual symposium on Computational geometry, pages 11-16. ACM, 2009. Google Scholar
  51. Edouard Wagneur and Chelliah Sriskandarajah. Openshops with jobs overlap. European Journal of Operational Research, 71(3):366-378, 1993. Google Scholar
  52. Guoqing Wang and TC Edwin Cheng. Customer order scheduling to minimize total weighted completion time. Omega, 35(5):623-626, 2007. Google Scholar
  53. Jaehwan Yang. Scheduling with batch objectives. PhD thesis, Ohio State University, 1998. 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 Imprint Privacy Contact