Throughput-Optimal Multiresource-Job Scheduling with Continuous Requirement Distribution

Heyuan Yao \orcidlogo, Willow Kowalik, Izzy Grosof \orcidlogo · 2026

Read Throughput-Optimal Multiresource-Job Scheduling with Continuous Requirement Distribution by Heyuan Yao \orcidlogo, Willow Kowalik, Izzy Grosof \orcidlogo (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-21715.txt.

Introduction

Heyuan Yao, Willow Kowalik, and Izzy Grosof develop the first throughput-optimal scheduling policies for computing jobs. Their resource needs vary continuously, as CPU and memory demands do in practice. Earlier theory assumed a small set of job classes, a poor fit when almost no two jobs share the same requirements. Their policies come in preemptive and nonpreemptive forms, gain efficiency through load-aware discretization, and beat existing index policies on parametrized distributions and Google Borg datacenter traces.

Catalog record

CREATORHeyuan Yao \orcidlogo, Willow Kowalik, Izzy Grosof \orcidlogo
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE145358
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.21715

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Throughput-Optimal Multiresource-Job Scheduling with Continuous Requirement Distribution Heyuan Yao \orcidlogo, Willow Kowalik, Izzy Grosof \orcidlogo Abstract Modern computing systems process jobs with resource requirements such as CPU and memory, which are described by multiresource jobs (MRJ) queueing models. In practice, job resource requirements are spread out over so many values, that it is rare to see the same value twice. This pattern is best modeled by a continuous distribution of requirement values. However, the existing theoretical work on stability or throughput-optimality focuses on queueing models with class-based resource requirements. In class-based models, the number of distinct resource requirements must be small to demonstrate strong empirical performance, making them a poor match for these practical systems. We introduce the first throughput-optimal family of scheduling policies for the continuous MRJ model, with both preemptive and nonpreemptive variants. We further introduce several efficient policy families, which remain throughput-optimal while considerably improving computational efficiency, under some distributional assumptions. We use a discretization approach, where we choose the discretization granularity based on the system load and the distribution of resource requirements. We validate the real-world applicability of our policies by comparing them against existing index-based policies on parametrized distributions and on datacenter trace data from the Google Borg scheduler, demonstrating state-of-the-art performance. MSC Classification]60K25, 68M20, 90B36 keywords Multiresource-Job, Scheduling, Queueing, Continuous Resource Requirement, Discretization-Based Policies, Throughput-Optimality pacs [ 1 Introduction Modern computing systems, such as cloud platforms, datacenters, and personal machines, typically possess multiple kinds of computational resources (e.g., CPU, GPU, memory). These systems can be modeled as queues where jobs require certain amounts of these resources, in order to be served. We refer to these jobs as multiresource jobs. 1 1 1 When the system is equipped with only one resource type, we refer to these jobs as multiserver jobs. The system is able to serve any set of multiresource jobs simultaneously, provided that the total requirement of each resource does not exceed the corresponding resource capacity. A scheduling policy specifies which set of multiresource jobs should be served at any time. Since the 1980s, many policies have been extensively studied Green 1980 ; Brill and Green 1984 ; Tassiulas and Ephremides 1993 ; Coffman and Stolyar 2001 ; Stolyar 2004 ; Maguluri et al. 2012 ; Rumyantsev and Morozov 2017 ; Psychas and Ghaderi 2018 ; Grosof et al. 2022a ; Grosof et al. 2022b ; Grosof et al. 2023 ; Hong and Wang 2022 ; Chen et al. 2026 , and their analyses include strong results such as system stability and throughput-optimality in their respective settings. However, existing policies, such as MaxWeight Stolyar 2004 ; Maguluri et al. 2012 , Randomized Multi-Resource Scheduling (RMS) Psychas and Ghaderi 2017 , Markovian Service Rate (MSR) Chen et al. 2025 , are restricted to settings with a finite set of possible resource requirements, which are known as “job classes”. For instance, MaxWeight weights jobs by how many jobs of identical resource requirements are present. The larger the number of job classes, the less the empirical performance corresponds to the theoretical results. In particular, the number of jobs present must be of at least the order of the number of job classes for empirical performance to correspond to the theoretical results. These queue lengths are too large for practical purposes. In datacenter scheduling traces, hundreds of thousands of unique resource requirements are commonly seen Tirmazi et al. 2020 . Theoretical results, which only kick in above hundreds of thousands jobs, are not useful. In real-world scheduling environments, for example, the first million jobs of the Borg trace Tirmazi et al. 2020 have 3,668 unique memory requirements, 536,229 unique CPU requirements, and 949,217 unique (CPU, memory) pairs. As a result, the existing class-based policies used in the literature are not suitable for such practical settings. Seeing this mismatch, we introduce the continuous MRJ model , in which the distribution of the resource requirement is continuous. While real systems do not literally have continuous resource requirements, the continuous MRJ model captures the behavior of rarely repeating resource requirements. In this model, we ask a question: Does there exist a throughput-optimal family of scheduling policies in the continuous MRJ setting? We resolve this question by developing the first throughput-optimal family of scheduling policies, the {\vec{K}} -discretized MaxWeight ( {\vec{K}} -MW) family. {\vec{K}} -MW uses discretization intentionally, rather than assuming that the resource requirements are inherently well-discretized. Our proof builds off the existing class-based MaxWeight proof, with additional techniques to handle the overhead of discretization, which must be controlled and mitigated. Many applications involve nonpreemptible jobs or require substantial preemption overhead. We therefore introduce the first nonpreemptive throughput-optimal family of scheduling policies: {\vec{K}} -discretized nonpreemptive Markovian Service Rate ( {\vec{K}} -nMSR). For {\vec{K}} -nMSR, we use the same discretization approach as {\vec{K}} -MW and construct the policy using the offline precomputation method for the MSR policies introduced in Chen et al. 2025 . In addition, computational efficiency is essential for both the online optimization in MaxWeight-type policies and the offline precomputation in nMSR-type policies. For instance, when using standard class-based MaxWeight in systems with numerous classes and small expected service durations, the exponentially large number of possible service options may cause the system to spend more time updating service options than actually serving jobs. To achieve computational efficiency, we must avoid handling an extremely large candidate set. We introduce a new group of policies that restrict attention to smaller candidate sets, where we only consider a small fraction of the possible service options, during MaxWeight and nMSR’s optimization steps. We call these smaller candidate sets “efficient sets”. We start by considering only the service options that form extreme vertices of the convex hull of the set of all service options. By doing so, for example, we reduce the candidate set by around 200\times when K=60 in the single-resource setting. Next, in the settings with symmetrical resource requirement distribution, our 2-Job efficient set reduces the number of service options to a quantity proportional to the number of discretization classes. In the single-resource setting with decreasing requirement density, our 2-Bucket efficient set likewise considers a number of service options proportional to the number of discretization classes. Our policies built on these three efficient sets are each throughput-optimal under corresponding distributional assumptions on the resource requirements. We use stimulation to extensively verify the performance, both throughput and mean response time, in both parameterized settings and a public Borg trace. Our simulation results verify the throughput optimality of the K -MW family and the Efficient K -MW families on a variety of requirement distributions. Moreover, both on these distributions and in experiments based on job requirements extracted from the Google Borg trace, our theoretically-motivated policies outperform in mean response time existing index-based policies: FCFS, First-Fit, Best-Fit, and Least-Server-First (LSF). Note that LSF is equivalent to naive MaxWeight in the continuous MSJ setting, because every job in its own class has equal weight. Naive MaxWeight then always serves most jobs, and packs the jobs in increasing order of their resource requirement. This paper is organized as follows: • Section 2 reviews related prior work on multiserver and multiresource scheduling. • Section 3 introduces the multiresource model under the continuous resource requirement setting, the {\vec{K}} -discretization

Read the complete text