{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T14:09:27Z","timestamp":1766066967785,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,1,25]],"date-time":"2019-01-25T00:00:00Z","timestamp":1548374400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMETRICS Perform. Eval. Rev."],"published-print":{"date-parts":[[2019,1,25]]},"abstract":"<jats:p>Many modern schedulers can dynamically adjust their service capacity to match the incoming workload. At the same time, however, variability in service capacity often incurs operational and infrastructure costs. In this paper, we propose distributed algorithms that minimize service capacity variability when scheduling jobs with deadlines. Specifically, we show that Exact Scheduling minimizes service capacity variance subject to strict demand and deadline requirements under stationary Poisson arrivals. We also characterize the optimal distributed policies for more general settings with soft demand requirements, soft deadline requirements, or both. Additionally, we show how close the performance of the optimal distributed policy is to that of the optimal centralized policy by deriving a competitive-ratio-like bound.<\/jats:p>","DOI":"10.1145\/3308897.3308925","type":"journal-article","created":{"date-parts":[[2019,1,28]],"date-time":"2019-01-28T14:01:39Z","timestamp":1548684099000},"page":"56-61","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Minimal-Variance Distributed Deadline Scheduling in a Stationary Environment"],"prefix":"10.1145","volume":"46","author":[{"given":"Yorie","family":"Nakahira","sequence":"first","affiliation":[{"name":"Caltech"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andres","family":"Ferragut","sequence":"additional","affiliation":[{"name":"Universidad ORT Uruguay, Uruguay"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam","family":"Wierman","sequence":"additional","affiliation":[{"name":"Caltech"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,1,25]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"B laszczyszyn. Stochastic Geometry and Wireless Networks","author":"Baccelli F.","year":"2009","unstructured":"F. Baccelli and B. B laszczyszyn. Stochastic Geometry and Wireless Networks , Volume I - Theory. Now Publishers , 2009 . F. Baccelli and B. B laszczyszyn. Stochastic Geometry and Wireless Networks, Volume I - Theory. Now Publishers, 2009."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206038"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.rser.2015.03.033"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/9.29398"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSG.2015.2396772"},{"key":"e_1_2_1_6_1","first-page":"300","volume-title":"OSDI","volume":"14","author":"Boutin E.","year":"2014","unstructured":"E. Boutin , J. Ekanayake , W. Lin , B. Shi , J. Zhou , Z. Qian , M. Wu , and L. Zhou . Apollo: Scalable and coordinated scheduling for cloud-scale computing . In OSDI , volume 14 , pages 285{ 300 , 2014 . E. Boutin, J. Ekanayake, W. Lin, B. Shi, J. Zhou, Z. Qian, M. Wu, and L. Zhou. Apollo: Scalable and coordinated scheduling for cloud-scale computing. In OSDI, volume 14, pages 285{300, 2014."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2051749"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.1070.0836"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2014.7040398"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071690.1064253"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2408776.2408794"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3086506"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPWRS.2012.2210288"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1496091.1496103"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1214\/105051607000000014"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.40851"},{"key":"e_1_2_1_18_1","first-page":"895","volume-title":"Signal and Information Processing (GlobalSIP), 2016 IEEE Global Conference on","author":"Lee G.","unstructured":"G. Lee , T. Lee , Z. Low , S. H. Low , and C. Ortega . Adaptive charging network for electric vehicles . In Signal and Information Processing (GlobalSIP), 2016 IEEE Global Conference on , pages 891{ 895 . IEEE, 2016. G. Lee, T. Lee, Z. Low, S. H. Low, and C. Ortega. Adaptive charging network for electric vehicles. In Signal and Information Processing (GlobalSIP), 2016 IEEE Global Conference on, pages 891{895. IEEE, 2016."},{"key":"e_1_2_1_19_1","first-page":"171","volume-title":"Real Time Systems Symposium, 1989., Proceedings.","author":"Lehoczky J.","unstructured":"J. Lehoczky , L. Sha , and Y. Ding . The rate monotonic scheduling algorithm: Exact characterization and average case behavior . In Real Time Systems Symposium, 1989., Proceedings. , pages 166{ 171 . IEEE, 1989. J. Lehoczky, L. Sha, and Y. Ding. The rate monotonic scheduling algorithm: Exact characterization and average case behavior. In Real Time Systems Symposium, 1989., Proceedings., pages 166{171. IEEE, 1989."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/258623.258685"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/321738.321743"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993744.1993767"},{"key":"e_1_2_1_23_1","volume-title":"Queueing systems with leadtime constraints: A uid-model approach for admission and sequencing control. European journal of operational research, 167(1):179{207","author":"Maglaras C.","year":"2005","unstructured":"C. Maglaras and J. A. V. Mieghem . Queueing systems with leadtime constraints: A uid-model approach for admission and sequencing control. European journal of operational research, 167(1):179{207 , 2005 . C. Maglaras and J. A. V. Mieghem. Queueing systems with leadtime constraints: A uid-model approach for admission and sequencing control. European journal of operational research, 167(1):179{207, 2005."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920886"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-013-9342-1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3077839.3077864"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2013.6760772"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.48019"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1017983532376"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tej.2007.01.006"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01995673"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSG.2013.2262508"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1925861.1925869"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308897.3308927"}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3308897.3308925","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3308897.3308925","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:58:03Z","timestamp":1750208283000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3308897.3308925"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,25]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,1,25]]}},"alternative-id":["10.1145\/3308897.3308925"],"URL":"https:\/\/doi.org\/10.1145\/3308897.3308925","relation":{},"ISSN":["0163-5999"],"issn-type":[{"type":"print","value":"0163-5999"}],"subject":[],"published":{"date-parts":[[2019,1,25]]},"assertion":[{"value":"2019-01-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}