Generalized Exact Scheduling: A Minimal-Variance Distributed Deadline Scheduler

References

• Baccelli F, Błaszczyszyn B (2009) Stochastic Geometry and Wireless Networks, Volume I, Theory (Now Publishers).Crossref, Google Scholar
• Baccelli F, Brémaud P (2013) Elements of Queueing Theory: Palm Martingale Calculus and Stochastic Recurrences, vol. 26 (Springer Science & Business Media, New York).Google Scholar
• Baker KR, Scudder GD (1990) Sequencing with earliness and tardiness penalties: A review. Oper. Res. 38(1):22–36.Link, Google Scholar
• Bansal N, Kimbrel T, Pruhs K (2007) Speed scaling to manage energy and temperature. J. ACM 54(1):3.Crossref, Google Scholar
• Behrangrad M (2015) A review of demand side management business models in the electricity market. Renewable Sustainable Energy Rev. 47:270–283.Crossref, Google Scholar
• Bertsekas DP (1995) Dynamic Programming and Optimal Control, vol. 2 (Athena Scientific, Belmont, MA).Google Scholar
• Bhattacharya PP, Ephremides A (1989) Optimal scheduling with strict deadlines. IEEE Trans. Automated Control 34(7):721–728.Crossref, Google Scholar
• Boutin E, Ekanayake J, Lin W, Shi B, Zhou J, Qian Z, Wu M, Zhou L (2014) Apollo: Scalable and coordinated scheduling for cloud-scale computing. 11th USENIX Sympos. Oper. Systems Design and Implementation (OSDI 14), vol. 14 (USENIX Association), 285?300. https://www.usenix.org/conference/osdi14/technical-sessions/presentation/boutin. 285–300.Google Scholar
• Brucker P, Brucker P (2007) Scheduling Algorithms, vol. 3 (Springer, Berlin).Google Scholar
• Brumelle SL (1971) On the relation between customer and time averages in queues. J. Appl. Probability 8(3):508–520.Crossref, Google Scholar
• Buttazzo GC (2011) Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications, vol. 24 (Springer Science & Business Media, New York).Crossref, Google Scholar
• Chen N, Gan L, Low SH, Wierman A (2014) Distributional analysis for model predictive deferrable load control. 53rd IEEE Conf. Decision Control (IEEE, New York), 6433–6438.Google Scholar
• Cover TM, Thomas JA (2006) Elements of Information Theory, 2nd ed. (Wiley-Interscience, New York).Google Scholar
• DanielsRL, Hoopes BJ, Mazzola JB (1996) Scheduling parallel manufacturing cells with resource flexibility. Management Sci. 42(9):1260–1276.Link, Google Scholar
• Das HS, Rahman MM, Li S, Tan CW (2020) Electric vehicles standards, charging infrastructure, and impact on grid integration: A technological review. Renewable Sustainable Energy Rev. 120:109618.Crossref, Google Scholar
• Dean J, Barroso LA (2013) The tail at scale. Comm. ACM 56(2):74–80.Crossref, Google Scholar
• Du J, Leung JYT (1990) Minimizing total tardiness on one machine is NP-hard. Math. Oper. Res. 15(3):483–495.Link, Google Scholar
• Ferragut A, Paganini F, Wierman A (2017) Controlling the variability of capacity allocations using service deferrals. ACM Trans. Modeling Performance Evaluation Comput. Systems 2(3):15.Crossref, Google Scholar
• Gan L, Topcu U, Low SH (2013a) Optimal decentralized protocol for electric vehicle charging. IEEE Trans. Power Systems 28(2):940–951.Crossref, Google Scholar
• Gan L, Wierman A, Topcu U, Chen N, Low SH (2013b) Real-time deferrable load control: Handling the uncertainties of renewable generation. Proc. 4th Internat. Conf. Future Energy Systems (Association for Computing Machinery, New York), 113–124.Google Scholar
• Gandhi A (2013) Dynamic server provisioning for data center power management. PhD thesis, Carnegie Mellon University, Pittsburgh, PA.Google Scholar
• Gandhi A, Harchol-Balter M, Das R, Lefurgy C (2009) Optimal power allocation in server farms. ACM SIGMETRICS Performance Evaluation Review, vol. 37(1) (ACM, New York), 157–168.Crossref, Google Scholar
• Greenberg A, Hamilton J, Maltz DA, Patel P (2008) The cost of a cloud: Research problems in data center networks. Comput. Comm. Rev. 39(1):68–73.Crossref, Google Scholar
• Gromoll HC, Kruk L (2007) Heavy traffic limit for a processor sharing queue with soft deadlines. Annals Appl. Probability 17(3):1049–1101.Crossref, Google Scholar
• Hong J, Tan X, Towsley D (1989) A performance analysis of minimum laxity and earliest deadline scheduling in a real-time system. IEEE Trans. Comput. 38(12):1736–1744.Crossref, Google Scholar
• Kusic D, Kephart JO, Hanson JE, Kandasamy N, Jiang G (2009) Power and performance management of virtualized computing environments via lookahead control. Cluster Comput. 12(1):1–15.Crossref, Google Scholar
• Lee C-Y, Jorge Leon V (2001) Machine scheduling with a rate-modifying activity. Eur. J. Oper. Res. 128(1):119–128.Crossref, Google Scholar
• Lee G, Lee T, Low Z, Low SH, Ortega C (2016) Adaptive charging network for electric vehicles. Proc. IEEE Global Conf. on Signal and Inform. Processing (IEEE, New York), 891–895.Google Scholar
• Lehoczky JP (1997a) Real-time queueing network theory. Proc. 18th IEEE Real-Time Systems Sympos. (IEEE, New York), 58–67.Google Scholar
• Lehoczky JP (1997b) Using real-time queueing theory to control lateness in real-time systems. Performance Evaluation Rev. 25(1): 158–168.Crossref, Google Scholar
• Lehoczky JP, Sha L, Ding Y (1989) The rate monotonic scheduling algorithm: Exact characterization and average case behavior. Proc. Real Time Systems Sympos. (IEEE, New York), 166–171.Google Scholar
• Lin M, Wierman A, Lachlan LHA, Thereska E (2013) Dynamic right-sizing for power-proportional data centers. IEEE/ACM Trans. Networks 21(5):1378–1391.Crossref, Google Scholar
• Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM 20(1):46–61.Crossref, Google Scholar
• Liu Z, Lin M, Wierman A, Low SH, Andrew LHL (2011) Greening geographical load balancing. Proc. ACM SIGMETRICS Joint Internat. Conf. on Measurement and Modeling of Comput. Systems (ACM, New York), 233–244.Google Scholar
• Lucier B, Menache I, Naor J, Yaniv J (2013) Efficient online scheduling for deadline-sensitive jobs. Proc. 25th Annual ACM Sympos. on Parallelism in Algorithms and Architectures (ACM, New York), 305–314.Google Scholar
• Melnik S, Gubarev A, Jing JL, Romer G, Shivakumar S, Tolton M, Vassilakis T (2010) Dremel: Interactive analysis of web-scale datasets. Proc. VLDB Endowment 3(1-2):330–339.Crossref, Google Scholar
• Nayyar A, Taylor J, Subramanian A, Poolla K, Varaiya P (2013) Aggregate flexibility of a collection of loads π. Proc. IEEE 52nd Annual Conf. on Decision and Control (IEEE, New York), 5600–5607.Google Scholar
• Panwar SS, Towsley D (1988) On the optimality of the ste rule for multiple server queues that serve customers with deadlines. Technical report, University of Massachusetts, Amhearst.Google Scholar
• Panwar SS, Towsley D, Wolf JK (1988) Optimal scheduling policies for a class of queues with customer deadlines to the beginning of service. J. ACM 35(4):832–844.Crossref, Google Scholar
• Pedlosky J (2013) Geophysical Fluid Dynamics (Springer Science & Business Media, New York).Google Scholar
• Pinedo M (1983) Stochastic scheduling with release dates and due dates. Oper. Res. 31(3):559–572.Link, Google Scholar
• Spees K, Lave LB (2007) Demand response and electricity market efficiency. Electrical J. 20(3):69–85.Crossref, Google Scholar
• Stankovic JA, Ramamritham K (1990) What is predictability for real-time systems? Real-Time Systems 2(4):247–254.Crossref, Google Scholar
• Stankovic JA, Spuri M, Ramamritham K, Buttazzo GC (2012) Deadline Scheduling for Real-Time Systems: EDF and Related Algorithms, vol. 460 (Springer Science & Business Media, New York).Google Scholar
• Subramanian A, Garcia MJ, Callaway DS, Poolla K, Varaiya P (2013) Real-time scheduling of distributed resources. IEEE Trans. Smart Grid 4(4):2122–2130.Crossref, Google Scholar
• Tang W, Ying JZ (2016) A model predictive control approach for low-complexity electric vehicle charging scheduling: Optimality and scalability. IEEE Trans. Power Systems 32(2):1050–1063.Crossref, Google Scholar
• Wang X, Chen M (2008) Cluster-level feedback power control for performance optimization. Proc. IEEE 14th Internat. Sympos. on High Performance Comput. Architecture (IEEE, New York), 101–110.Google Scholar
• Yang J, Ulukus S (2012) Optimal packet scheduling in a multiple access channel with energy harvesting transmitters. J. Comm. Networks (Seoul) 14(2):140–150.Crossref, Google Scholar
• Yao F, Demers A, Shenker S (1995) A scheduling model for reduced cpu energy. Proc. 36th Annual Sympos. on Foundations of Comput. Sci. (IEEE, New York), 374–382.Google Scholar
• Zeballos M, Ferragut A, Paganini F (2019) Proportional fairness for EV charging in overload. IEEE Trans. Smart Grid 10(6): 6792–6801.Crossref, Google Scholar