{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T12:14:10Z","timestamp":1767183250290,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":50,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T00:00:00Z","timestamp":1593993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["NSF-CMMI-1938909,NSF-XPS-1629444,NSF-CSR-1763701,CCF-1824303,CCF-1845146,CCF-1733873,CMMI-1938909,DGE-1745016"],"award-info":[{"award-number":["NSF-CMMI-1938909,NSF-XPS-1629444,NSF-CSR-1763701,CCF-1824303,CCF-1845146,CCF-1733873,CMMI-1938909,DGE-1745016"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","award":["Research Award"],"award-info":[{"award-number":["Research Award"]}],"id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Carnegie Bosch","award":["Junior Faculty Chair"],"award-info":[{"award-number":["Junior Faculty Chair"]}]},{"DOI":"10.13039\/100005801","name":"Facebook","doi-asserted-by":"publisher","award":["Graduate Fellowship"],"award-info":[{"award-number":["Graduate Fellowship"]}],"id":[{"id":"10.13039\/100005801","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Infor","award":["Research Award"],"award-info":[{"award-number":["Research Award"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,7,6]]},"DOI":"10.1145\/3350755.3400265","type":"proceedings-article","created":{"date-parts":[[2020,7,9]],"date-time":"2020-07-09T15:56:12Z","timestamp":1594310172000},"page":"75-87","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Optimal Resource Allocation for Elastic and Inelastic Jobs"],"prefix":"10.1145","author":[{"given":"Benjamin","family":"Berg","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mor","family":"Harchol-Balter","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Moseley","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weina","family":"Wang","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Justin","family":"Whitehouse","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,7,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02024665"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2019.00024"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884449"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.97"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00583-8"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1453175.1453199"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3154499"},{"key":"e_1_3_2_1_8_1","unstructured":"Benjamin Berg Mor Harchol-Balter Benjamin Moseley Weina Wang and Justin Whitehouse. Optimal resource allocation for elastic and inelastic jobs. https:\/\/arxiv.org\/abs\/2005.09745.  Benjamin Berg Mor Harchol-Balter Benjamin Moseley Weina Wang and Justin Whitehouse. Optimal resource allocation for elastic and inelastic jobs. https:\/\/arxiv.org\/abs\/2005.09745."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2005.07.005"},{"key":"e_1_3_2_1_10_1","first-page":"679","volume-title":"A competitive algorithm for minimizing weighted flow time on unrelated machines with speed augmentation","author":"Chadha Jivitej S.","year":"2009","unstructured":"Jivitej S. Chadha , Naveen Garg , Amit Kumar , and V. N. Muralidhara . A competitive algorithm for minimizing weighted flow time on unrelated machines with speed augmentation . In Michael Mitzenmacher, editor,Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009 , Bethesda, MD, USA, May31 - June 2, 2009, pages 679 -- 684 . ACM , 2009. Jivitej S. Chadha, Naveen Garg, Amit Kumar, and V. N. Muralidhara. A competitive algorithm for minimizing weighted flow time on unrelated machines with speed augmentation. In Michael Mitzenmacher, editor,Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May31 - June 2, 2009, pages 679--684. ACM, 2009."},{"key":"e_1_3_2_1_11_1","volume-title":"Theory of scheduling","author":"Conway Richard W","year":"2003","unstructured":"Richard W Conway , Louis W Miller , and William L Maxwell . Theory of scheduling . Dover , 2003 . Richard W Conway, Louis W Miller, and William L Maxwell. Theory of scheduling.Dover, 2003."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2644865.2541941"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00186-3"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133045"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496845"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133046"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/Allerton.2011.6120299"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2018.10.001"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2014.7116905"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.98"},{"key":"e_1_3_2_1_22_1","first-page":"228","volume-title":"IPCO 2017, Waterloo, ON, Canada, June 26--28, 2017","author":"Gupta Varun","year":"2017","unstructured":"Varun Gupta , Benjamin Moseley , Marc Uetz , and Qiaomin Xie . Stochastic online scheduling on unrelated machines. In Integer Programming and Combinatorial Optimization - 19th International Conference , IPCO 2017, Waterloo, ON, Canada, June 26--28, 2017 , Proceedings , pages 228 -- 240 , 2017 . Varun Gupta, Benjamin Moseley, Marc Uetz, and Qiaomin Xie. Stochastic online scheduling on unrelated machines. In Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26--28, 2017, Proceedings, pages 228--240, 2017."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1330555.1330566"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/506147.506154"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/2462638"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/777412.777462"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2003.1203514"},{"key":"e_1_3_2_1_28_1","volume-title":"Multi-server queueing systems with multiple priority classes. Queueing Systems: Theory and Applications, 51(3--4):331--360","author":"Harchol-Balter Mor","year":"2005","unstructured":"Mor Harchol-Balter , Takayuki Osogami , Alan Scheller-Wolf , and Adam Wierman . Multi-server queueing systems with multiple priority classes. Queueing Systems: Theory and Applications, 51(3--4):331--360 , 2005 . Mor Harchol-Balter, Takayuki Osogami, Alan Scheller-Wolf, and Adam Wierman. Multi-server queueing systems with multiple priority classes. Queueing Systems: Theory and Applications, 51(3--4):331--360, 2005."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1555349.1555383"},{"key":"e_1_3_2_1_30_1","first-page":"22","volume-title":"NSDI","volume":"11","author":"Hindman Benjamin","year":"2011","unstructured":"Benjamin Hindman , Andy Konwinski , Matei Zaharia , Ali Ghodsi , Anthony D Joseph , Randy H Katz , Scott Shenker , and Ion Stoica . Mesos : A platform for fine-grained resource sharing in the data center . In NSDI , volume 11 , pages 22 -- 22 , 2011 . Benjamin Hindman, Andy Konwinski, Matei Zaharia, Ali Ghodsi, Anthony D Joseph, Randy H Katz, Scott Shenker, and Ion Stoica. Mesos: A platform for fine-grained resource sharing in the data center. In NSDI, volume 11, pages 22--22,2011."},{"key":"e_1_3_2_1_31_1","volume-title":"Competitively scheduling tasks with intermediate parallelizability. ACM Transactions on Parallel Computing (TOPC), 3(1):1--19","author":"Im Sungjin","year":"2016","unstructured":"Sungjin Im , Benjamin Moseley , Kirk Pruhs , and Eric Torng . Competitively scheduling tasks with intermediate parallelizability. ACM Transactions on Parallel Computing (TOPC), 3(1):1--19 , 2016 . Sungjin Im, Benjamin Moseley, Kirk Pruhs, and Eric Torng. Competitively scheduling tasks with intermediate parallelizability. ACM Transactions on Parallel Computing (TOPC), 3(1):1--19, 2016."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.16501"},{"key":"e_1_3_2_1_33_1","volume-title":"Computer applications","author":"Kleinrock Leonard","year":"1976","unstructured":"Leonard Kleinrock . Queueing systems , volume 2 : Computer applications , volume 66. Wiley New York , 1976 . Leonard Kleinrock. Queueing systems, volume 2: Computer applications, volume 66. Wiley New York, 1976."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719734"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.018"},{"key":"e_1_3_2_1_36_1","first-page":"5330","volume-title":"Advances in Neural Information Processing Systems","author":"Lian Xiangru","year":"2017","unstructured":"Xiangru Lian , Ce Zhang , Huan Zhang , Cho-Jui Hsieh , Wei Zhang , and Ji Liu . Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent . In Advances in Neural Information Processing Systems , pages 5330 -- 5340 , 2017 . Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems, pages 5330--5340, 2017."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357223.3362719"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2749469.2749475"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2155620.2155650"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.6.1.1"},{"key":"e_1_3_2_1_41_1","first-page":"561","volume-title":"13th USENIX Symposium on Operating Systems Design and Implementation (OSDI18)","author":"Moritz Philipp","year":"2018","unstructured":"Philipp Moritz , Robert Nishihara , Stephanie Wang , Alexey Tumanov , Richard Liaw , Eric Liang , Melih Elibol , Zongheng Yang , William Paul , Michael I Jordan , : A distributed framework for emerging AI applications . In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI18) , pages 561 -- 577 , 2018 . Philipp Moritz, Robert Nishihara, Stephanie Wang, Alexey Tumanov, Richard Liaw, Eric Liang, Melih Elibol, Zongheng Yang, William Paul, Michael I Jordan, et al. Ray: A distributed framework for emerging AI applications. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI18), pages 561--577, 2018."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.2213"},{"key":"e_1_3_2_1_43_1","volume-title":"Matrix-Geometric Solutions in Stochastic Models","author":"Neuts Marcel F.","year":"1981","unstructured":"Marcel F. Neuts . Matrix-Geometric Solutions in Stochastic Models . Johns Hopkins University Press , 1981 . Marcel F. Neuts. Matrix-Geometric Solutions in Stochastic Models. Johns Hopkins University Press, 1981."},{"key":"e_1_3_2_1_44_1","volume-title":"Structured Stochastic Matrices of M\/G\/1 Type and Their Applications","author":"Neuts Marcel F.","year":"1989","unstructured":"Marcel F. Neuts . Structured Stochastic Matrices of M\/G\/1 Type and Their Applications . Marcel Dekker , 1989 . Marcel F. Neuts. Structured Stochastic Matrices of M\/G\/1 Type and Their Applications. Marcel Dekker, 1989."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2005.06.002"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1145\/781027.781050","volume-title":"Proceedings of ACM Sigmetrics","author":"Osogami Takayuki","year":"2003","unstructured":"Takayuki Osogami , Mor Harchol-Balter , and Alan Scheller-Wolf . Analysis of cycle stealing with switching times and thresholds . In Proceedings of ACM Sigmetrics , pages 184 -- 195 , San Diego, CA , June 2003 . Takayuki Osogami, Mor Harchol-Balter, and Alan Scheller-Wolf. Analysis of cycle stealing with switching times and thresholds. In Proceedings of ACM Sigmetrics, pages 184--195, San Diego, CA, June 2003."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3190508.3190517"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.26.1.197"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741964"},{"key":"e_1_3_2_1_50_1","volume-title":"Delay asymptotics and bounds for multitask parallel jobs. Queueing Systems, 91(3--4):207--239","author":"Wang Weina","year":"2019","unstructured":"Weina Wang , Mor Harchol-Balter , Haotian Jiang , Alan Scheller-Wolf , and Rayadurgam Srikant . Delay asymptotics and bounds for multitask parallel jobs. Queueing Systems, 91(3--4):207--239 , 2019 . Weina Wang, Mor Harchol-Balter, Haotian Jiang, Alan Scheller-Wolf, and Rayadurgam Srikant. Delay asymptotics and bounds for multitask parallel jobs. Queueing Systems, 91(3--4):207--239, 2019."}],"event":{"name":"SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"],"location":"Virtual Event USA","acronym":"SPAA '20"},"container-title":["Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3350755.3400265","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3350755.3400265","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3350755.3400265","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:21Z","timestamp":1750200081000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3350755.3400265"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,6]]},"references-count":50,"alternative-id":["10.1145\/3350755.3400265","10.1145\/3350755"],"URL":"https:\/\/doi.org\/10.1145\/3350755.3400265","relation":{},"subject":[],"published":{"date-parts":[[2020,7,6]]},"assertion":[{"value":"2020-07-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}