An Optimal Control Framework for Online Job Scheduling with General Cost Functions

References

• Anand S, Garg N, Kumar A (2012) Resource augmentation for weighted flow-time explained by dual fitting. Proc. 23rd Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1228–1241. https://epubs.siam.org/doi/abs/10.1137/1.9781611973099.97.Google Scholar
• Angelopoulos S, Lucarelli G, Kim TN (2019) Primal–dual and dual-fitting analysis of online scheduling algorithms for generalized flow-time problems. Algorithmica 81(9):3391–3421.Crossref, Google Scholar
• Antoniadis A, Hoeksma R, Meißner J, Verschae J, Wiese A (2017) A QPTAS for the general scheduling problem with identical release dates. Chatzigiannakis I, Indyk P, Kuhn F, Muscholl A, eds. Proc. 44th Internat. Colloquium Automata, Languages Programming (Schloss Dagstuhl-Leibniz-Zentrum Fuer Informatik, Dagstuhl, Germany), 31:1–31:14.Google Scholar
• Azar Y, Epstein A (2005) Convex programming for scheduling unrelated parallel machines. Proc. 37th Annual ACM Sympos. Theory Comput. (ACM, New York), 331–337. https://dl.acm.org/doi/abs/10.1145/1060590.1060639?casa_token=nobh1uzPwrAAAAAA:fuQC2hgBjHU-XHWokd2bkYGTxyvRK8df7Xa5Hmd8X2kPO_Tnsy4ejq_2CgzAOk2vDZv9yYTw7eHb.Google Scholar
• Başar T, Meyn S, Perkins WR (2020) Lecture notes on control system theory and design. Preprint, submitted July 2, https://arxiv.org/abs/2007.01367.Google Scholar
• Bansal N, Chan HL (2009) Weighted flow time does not admit o(1)-competitive algorithms. Proc. 20th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1238–1244. https://epubs.siam.org/doi/abs/10.1137/1.9781611973068.134.Google Scholar
• Bansal N, Pruhs K (2014) The geometry of scheduling. SIAM J. Comput. 43(5):1684–1698.Crossref, Google Scholar
• Becchetti L, Leonardi S, Marchetti-Spaccamela A, Pruhs K (2006) Online weighted flow time and deadline scheduling. J. Discrete Algorithms 4(3):339–352.Crossref, Google Scholar
• Bertsekas DP (1999) Nonlinear Programming, 2nd ed. (Athena Scientific, Belmont, MA).Google Scholar
• Borodin A, Nielsen MN, Rackoff C (2003) (Incremental) priority algorithms. Algorithmica 37(4):295–326.Crossref, Google Scholar
• Chadha JS, Garg N, Kumar A, Muralidhara V (2009) A competitive algorithm for minimizing weighted flow time on unrelated machines with speed augmentation. Proc. 41st Annual ACM Sympos. Theory Comput. (ACM, New York), 679–684. https://dl.acm.org/doi/abs/10.1145/1536414.1536506?casa_token=X_zlwzw9O8IAAAAA:w_bPmWlPHNkBfklgZEipTRZsrfEGqNvv3N_sLZ3b-6Xg4u8GNnYz49Ur-rK9yKLos_nHMO7pXn9Y.Google Scholar
• Chekuri C, Khanna S, Zhu A (2001) Algorithms for minimizing weighted flow time. Proc. 33rd Annual ACM Sympos. Theory Comput. (ACM, New York), 84–93. https://dl.acm.org/doi/10.1145/380752.380778.Google Scholar
• Cheung M, Mestre J, Shmoys DB, Verschae J (2017) A primal-dual approximation algorithm for min-sum single-machine scheduling problems. SIAM J. Discrete Math. 31(2):825–838.Crossref, Google Scholar
• Devanur NR, Huang Z (2018) Primal dual gives almost optimal energy-efficient online algorithms. ACM Trans. Algorithms 14(1):1–30.Crossref, Google Scholar
• Etesami SR (2019) A unifying optimal control framework for online job scheduling with general cost functions. Preprint, submitted June 6, https://arxiv.org/abs/1906.02644v1.Google Scholar
• Etesami SR (2021) Online job scheduling on a single machine with general cost functions. Proc. 60th IEEE Conf. Decision Control (IEEE, New York), 6690–6695. https://ieeexplore.ieee.org/document/9682957.Google Scholar
• Fox K, Im S, Kulkarni J, Moseley B (2013) Online non-clairvoyant scheduling to simultaneously minimize all convex functions. Approximation, Randomization, Combinatorial Optimization. Algorithms Techniques (Springer, Berlin), 142–157. https://link.springer.com/chapter/10.1007/978-3-642-40328-6_11.Crossref, Google Scholar
• Garg N, Kumar A (2007) Minimizing average flow-time: Upper and lower bounds. Proc. 48th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, New York), 603–613. https://ieeexplore.ieee.org/abstract/document/4389529?casa_token=X7PIlHO5YAQAAAAA:sTtgJ7TTwx_wuKY10iU9T9ixM-AGFRCaKht8Wn4uUjGpbe3GG3Mx54ohg9IYC5z5nHlrsvcQhA.Google Scholar
• Graham RL, Lawler EL, Lenstra JK, Kan AR (1979) Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals Discrete Math. 5:287–326.Crossref, Google Scholar
• Gupta V, Moseley B, Uetz M, Xie Q (2020) Greed works: Online algorithms for unrelated machine stochastic scheduling. Math. Oper. Res. 45(2):497–516.Link, Google Scholar
• Höhn W, Jacobs T (2015) On the performance of Smith’s rule in single-machine scheduling with nonlinear cost. ACM Trans. Algorithms 11(4):1–30.Crossref, Google Scholar
• Im S, Kulkarni J (2016) Fair online scheduling for selfish jobs on heterogeneous machines. Proc. 28th ACM Sympos. Parallelism Algorithms Architectures (ACM, New York), 185–194. https://dl.acm.org/doi/abs/10.1145/2935764.2935773.Google Scholar
• Im S, Moseley B (2011) An online scalable algorithm for minimizing ℓk-norms of weighted flow time on unrelated machines. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 95–108. https://dl.acm.org/doi/10.5555/2133036.2133044.Google Scholar
• Im S, Kulkarni J, Munagala K (2015) Competitive flow time algorithms for polyhedral scheduling. Proc. 56th Annual Sympos. Foundations Comput. Sci. (IEEE, New York), 506–524. https://ieeexplore.ieee.org/document/7354412.Google Scholar
• Im S, Kulkarni J, Munagala K (2018) Competitive algorithms from competitive equilibria: Non-clairvoyant scheduling under polyhedral constraints. J. ACM 65(1):1–33.Crossref, Google Scholar
• Im S, Moseley B, Pruhs K (2011) A tutorial on amortized local competitiveness in online scheduling. SIGACT News 42(2):83–97.Crossref, Google Scholar
• Im S, Moseley B, Pruhs K (2014b) Online scheduling with general cost functions. SIAM J. Comput. 43(1):126–143.Crossref, Google Scholar
• Im S, Kulkarni J, Munagala K, Pruhs K (2014a) Selfishmigrate: A scalable algorithm for non-clairvoyantly scheduling heterogeneous processors. Proc. 55th Annual Sympos. Foundations Comput. Sci. (IEEE, New York), 531–540. https://ieeexplore.ieee.org/abstract/document/6979038?casa_token=5KTO7i2aUiUAAAAA:a3J_rNyuS2gPGHGlKL2mgThKVl7rFOEFsdPGSs2J9R0sSQCtky-5PbfPprSNI_Zi8P656UaTug.Google Scholar
• Kalyanasundaram B, Pruhs K (2000) Speed is as powerful as clairvoyance. J. ACM 47(4):617–643.Crossref, Google Scholar
• Leonardi S, Raz D (2007) Approximating total flow time on parallel machines. J. Comput. System Sci. 73(6):875–891.Crossref, Google Scholar
• Leung JY (2004) Handbook of Scheduling: Algorithms, Models, and Performance Analysis (CRC Press, Boca Raton, FL).Crossref, Google Scholar
• Liberzon D (2011) Calculus of Variations and Optimal Control Theory: A Concise Introduction (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Lucarelli G, Thang NK, Srivastav A, Trystram D (2016) Online non-preemptive scheduling in a resource augmentation model based on duality. Sankowski P, Zaroliagis C, eds., Leibniz Internat. Proc. Inform. (LIPIcs), vol. 57 (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 63:1–63:17.Google Scholar
• Megow N, Verschae J (2018) Dual techniques for scheduling on a machine with varying speed. SIAM J. Discrete Math. 32(3):1541–1571.Crossref, Google Scholar
• Moseley B (2019) Scheduling to approximate minimization objectives on identical machines. Baier C, Chatzigiannakis I, Flocchini P, Leonardi S, eds. Leibniz Internat. Proc. Inform. (LIPIcs), vol. 132 (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 86:1–86:14.Google Scholar
• Nguyen KT (2013) Lagrangian duality in online scheduling with resource augmentation and speed scaling. Proc. Eur. Sympos. Algorithms (Springer, Berlin), 755–766. https://link.springer.com/chapter/10.1007/978-3-642-40450-4_64.Google Scholar
• Williamson DP, Shmoys DB (2011) The Design of Approximation Algorithms (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar