{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T15:34:12Z","timestamp":1772206452134,"version":"3.50.1"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T00:00:00Z","timestamp":1748304000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-24-1-0002"],"award-info":[{"award-number":["FA9550-24-1-0002"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"NSF","doi-asserted-by":"publisher","award":["CCF-2403195,IIS-2322974"],"award-info":[{"award-number":["CCF-2403195,IIS-2322974"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2025,5,27]]},"abstract":"<jats:p>Modern cloud computing workloads are composed of multiresource jobs that require a variety of computational resources in order to run, such as CPU cores, memory, disk space, or hardware accelerators. A single cloud server can typically run many multiresource jobs in parallel, but only if the server has sufficient resources to satisfy the demands of every job. A scheduling policy must therefore select sets of multiresource jobs to run in parallel in order to minimize the mean response time across jobs --- the average time from when a job arrives to the system until it is completed. Unfortunately, achieving low response times by selecting sets of jobs that fully utilize the available server resources has proven to be a difficult problem.<\/jats:p>\n          <jats:p>In this paper, we develop and analyze a new class of policies for scheduling multiresource jobs, called Markovian Service Rate (MSR) policies. While prior scheduling policies for multiresource jobs are either highly complex to analyze or hard to implement, our MSR policies are simple to implement and are amenable to response time analysis. We show that the class of MSR policies is throughput-optimal in that we can use an MSR policy to stabilize the system whenever it is possible to do so. We also derive bounds on the mean response time under an MSR algorithm that are tight up to an additive constant. These bounds can be applied to systems with different preemption behaviors, such as fully preemptive systems, non-preemptive systems, and systems that allow preemption with setup times. We show how our theoretical results can be used to select a good MSR policy as a function of the system arrival rates, job service requirements, the server's resource capacities, and the resource demands of the jobs.<\/jats:p>","DOI":"10.1145\/3727117","type":"journal-article","created":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T09:43:35Z","timestamp":1749030215000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Improving Multiresource Job Scheduling with Markovian Service Rate Policies"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-8694-4404","authenticated-orcid":false,"given":"Zhongrui","family":"Chen","sequence":"first","affiliation":[{"name":"University of North Carolina at Chapel Hill, Chapel Hill, North Carolina, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6205-8652","authenticated-orcid":false,"given":"Isaac","family":"Grosof","sequence":"additional","affiliation":[{"name":"Northwestern University, Evanston, Illinois, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4147-6860","authenticated-orcid":false,"given":"Benjamin","family":"Berg","sequence":"additional","affiliation":[{"name":"University of North Carolina at Chapel Hill, Chapel Hill, North Carolina, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,3]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Towards Optimality in Parallel Scheduling. ACM POMACS","volume":"1","author":"Berg B.","year":"2018","unstructured":"B. Berg, J.P. Dorsman, and M. Harchol-Balter. 2018. Towards Optimality in Parallel Scheduling. ACM POMACS, Vol. 1, 2 (2018)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2777647.2777658"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3695411.3695422"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3287322"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2644865.2541941"},{"key":"e_1_2_1_6_1","first-page":"53","article-title":"Single-server queueing system with Markov-modulated arrivals and service times","volume":"20","author":"Dimitrov Mitko","year":"2011","unstructured":"Mitko Dimitrov. 2011. Single-server queueing system with Markov-modulated arrivals and service times. Pliska Stud. Math. Bulg, Vol. 20 (2011), 53--62.","journal-title":"Pliska Stud. Math. Bulg"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-012-9305-y"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9893-8"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02564727"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465529.2465760"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2016.7524536"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2015.7447025"},{"key":"e_1_2_1_13_1","volume-title":"Stability for Two-class Multiserver-job Systems. (10","author":"Grosof Isaac","year":"2020","unstructured":"Isaac Grosof, Mor Harchol-Balter, and Alan Scheller-Wolf. 2020. Stability for Two-class Multiserver-job Systems. (10 2020). https:\/\/arxiv.org\/abs\/2010.00631v1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/S11134-022-09848--6\/METRICS"},{"key":"e_1_2_1_15_1","volume-title":"Analysis of Markovian Arrivals and Service with Applications to Intermittent Overload. arXiv preprint arXiv:2405.04102","author":"Grosof Isaac","year":"2024","unstructured":"Isaac Grosof, Yige Hong, and Mor Harchol-Balter. 2024. Analysis of Markovian Arrivals and Service with Applications to Intermittent Overload. arXiv preprint arXiv:2405.04102 (2024)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2023.102378"},{"key":"e_1_2_1_17_1","volume-title":"Performance Modeling and Design of Computer Systems: Queueing Theory in Action","author":"Harchol-Balter M.","unstructured":"M. Harchol-Balter. 2013. Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Cambridge University Press."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-022-09762-x"},{"key":"e_1_2_1_19_1","first-page":"22","article-title":"Mesos: A platform for fine-grained resource sharing in the data center","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. 2011. Mesos: A platform for fine-grained resource sharing in the data center.. In NSDI, Vol. 11. 22--22.","journal-title":"NSDI"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.39"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3379485"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.018"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/icc.2011.5962782"},{"key":"e_1_2_1_24_1","volume-title":"The SLURM Scheduler Design","author":"Lipari Don","year":"2012","unstructured":"Don Lipari. 2012. The SLURM Scheduler Design. SLURM User Group. http:\/\/slurm. schedmd. com\/slurm_ug_2012\/SUG-2012-Scheduling. pdf (2012)."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2013.2288973"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2014.08.002"},{"key":"e_1_2_1_27_1","volume-title":"Max-weight scheduling in queueing networks with heavy-tailed traffic","author":"Markakis Mihalis G","year":"2013","unstructured":"Mihalis G Markakis, Eytan Modiano, and John N Tsitsiklis. 2013. Max-weight scheduling in queueing networks with heavy-tailed traffic. IEEE\/ACM Transactions on networking, Vol. 22, 1 (2013), 257--270."},{"key":"e_1_2_1_28_1","first-page":"139","article-title":"The M\/M\/1 queue with randomly varying arrival and service rates","volume":"15","author":"Neuts Marcel F","year":"1978","unstructured":"Marcel F Neuts. 1978. The M\/M\/1 queue with randomly varying arrival and service rates. Opsearch, Vol. 15 (1978), 139--157.","journal-title":"Opsearch"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2011.2177101"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2005.07.030"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2018.2863647"},{"key":"e_1_2_1_32_1","volume-title":"The queue M\/\/G\/1 with Markov modulated arrivals and services. Mathematics of operations research","author":"Regterschot GJK","year":"1986","unstructured":"GJK Regterschot and JHA De Smit. 1986. The queue M\/\/G\/1 with Markov modulated arrivals and services. Mathematics of operations research, Vol. 11, 3 (1986), 465--483."},{"key":"e_1_2_1_33_1","unstructured":"SchedMD. 2021. SLURM Workload Manager. (2021). https:\/\/slurm.schedmd.com\/heterogeneous_jobs.html."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1075828046"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.1990.204000"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3342195.3387517"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741964"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3410220.3453924"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/781027.781057"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3727117","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3727117","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:31:21Z","timestamp":1755898281000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3727117"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,27]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,5,27]]}},"alternative-id":["10.1145\/3727117"],"URL":"https:\/\/doi.org\/10.1145\/3727117","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,27]]},"assertion":[{"value":"2025-06-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}