Asymptotically Optimal Scheduling of Multiple Parallelizable Job Classes

1. Introduction

The vast majority of modern computer systems are designed to exploit parallelism. Whether considering a single multicore server, a compute cluster of many servers, or even an entire data center, achieving good system performance requires carefully choosing how to parallelize jobs across the underlying cores or servers in the system. For example, database queries for an in-memory database must be parallelized across the cores of a multicore server to achieve low query latency (Leis et al. 2014, Wagner et al. 2021), machine learning training jobs must be parallelized across the many GPUs of a compute cluster to reduce job completion time (Qiao et al. 2021, Jayaram Subramanya et al. 2023), and datacenter computing workloads must be parallelized across the many servers of a data center (Tumanov et al. 2016, Delgado et al. 2018). In each of these cases, the system operator is presented with a fixed set of cores or servers and asked to devise a strategy to allocate these resources across a stream of parallelizable jobs. However, devising optimal scheduling policies for parallelizable jobs in multiserver systems remains an open problem.

This paper develops asymptotically optimal scheduling policies for parallelizable jobs. Specifically, given a limited number of servers, k, we ask how to allocate these servers to a stream of parallelizable jobs arriving over time to minimize the mean response time across jobs.

If a workload consists solely of perfectly parallelizable jobs that can each fully utilize all k cores, the problem is easy because each job effectively sees one fast server that runs k times faster than a single server. Unfortunately, in practice, parallelizable jobs typically have limits to their level of parallelizability. For example, a database query is compiled to run with a certain number of threads, t, where $t\ll k$ (recall k is the total number of servers; Chen et al. 2016). Allocating more than t cores to this query will not reduce its processing time. Similarly, a job’s level of parallelism may be limited by overhead from communication between its threads. For example, machine learning training jobs can be parallelized across many servers, but these servers must synchronize at the end of each training iteration (Lin et al. 2018, Qiao et al. 2021). Additionally, some jobs consist of a mixture of parallelizable work and nonparallelizable work. This leads to the well-known phenomenon described as Amdahl’s law, which says that the speedup a job can receive from parallelism is bounded in terms of the fraction of the job that is parallelizable (Hill and Marty 2008).

Each of these factors will affect the parallelizability of different jobs to different degrees. Some jobs in a workload may be highly parallelizable, whereas others may benefit only slightly from running on additional servers. This mixture of jobs with different levels of parallelizability is commonly seen in databases (Leis et al. 2014), machine learning workloads (Qiao et al. 2021), and datacenter scheduling (Tumanov et al. 2016). This paper develops new theoretical analyses of systems with parallelizable jobs of varying parallelizability levels.

1.1. High-Level Problem Statement

To capture the limited parallelism in today’s parallel computing workloads, we approximate the behavior of different parallelizable jobs by assuming that jobs are perfectly parallelizable up to some parallelizability limit. This limit represents aspects of how the job was compiled, the communication overhead the job incurs, and what fraction of the job is parallelizable. Formally, we characterize each job by a pair $(S,c)$ where S is a random variable denoting the job’s inherent size and c is its parallelizability level. The time required to complete a parallelizable job is a function of both its inherent size and the servers allocated to it over time. When a job runs on $m\le c$ servers, its remaining size decreases at a rate of m units of work per second until the remaining size reaches zero and the job is considered complete. The job cannot utilize more than c servers.

To capture the varying levels of parallelizability seen within a single workload, we allow jobs to belong to one of $\mathcal{\ell }$ job classes. Each job class, i, has an associated job size distribution, $S_i$, and parallelism limit, $c_i$, that applies to every class i job. We assume that a job’s exact size is unknown to the system, but its class is known; that is, the system knows $(S_i,c_i)$, for all i. Furthermore, we assume that jobs are malleable, meaning that a job can change the number of servers it runs on over time (Gupta et al. 2014).

Given a stream of malleable jobs that arrive to the system over time, a scheduling policy must determine how many servers to allocate to each job at every moment in time. Given a system with k homogeneous servers, our goal is to develop scheduling policies that minimize the mean response time across jobs—the average time from when a job arrives to the system until it is completed.

1.2. Prior Work

Scheduling in multiserver systems is known to be a difficult problem. There is a variety of work from the systems community on scheduling parallelizable jobs, including work on scheduling in databases (Leis et al. 2014, Wagner et al. 2021), machine learning clusters (Qiao et al. 2021, Jayaram Subramanya et al. 2023), data analytics clusters (Vernica et al. 2010, Zhu et al. 2014), and data centers (Tumanov et al. 2016, Delgado et al. 2018). This work uses simple policies with no formal guarantees. Additionally, many systems optimize for metrics such as fairness in addition to trying to minimize response times.

In the theoretical scheduling community, even when jobs are not parallelizable and each job occupies a single server, the optimal scheduling policy is not known. Recent results (Grosof et al. 2018) derived the first bounds on the mean response time of shortest-remaining-processing-time (SRPT) in multiserver systems, showing that SRPT is optimal in conventional heavy traffic (see Section 2). These heavy-traffic results were extended to a Gittins index policy (Scully et al. 2020a) in the case where job sizes are not fully known. Unfortunately, none of these results deal with parallelizable jobs.

Another related area of active research is scheduling for multiserver jobs (Grosof et al. 2020, Harchol-Balter 2022, Hong and Wang 2022). Multiserver jobs each have a hard, fixed resource requirement on the number of servers they need. Different jobs have different fixed server requirements. In general, it is not known how to minimize the mean response time for multiserver jobs, even in heavy traffic. Under some constraints on the server requirements of each job, an SRPT variant called ServerFilling-SRPT was recently shown to be optimal in conventional heavy traffic (Grosof et al. 2022a, b). Because jobs have hard resource requirements in the multiserver job model, one of the main concerns of a scheduling policy is to ensure that jobs are efficiently packed onto the available servers so that the system utilization remains high. Failing to pack the jobs efficiently can cause the system to be unstable. By contrast, the malleable jobs we consider do not have this stability concern, because they can adapt their levels of parallelism to ensure that the servers remain fully utilized. Hence, the policies developed for scheduling multiserver jobs tend to prioritize packing in a way that has no benefit when scheduling malleable jobs.

The work closest to our model considers scheduling parallelizable jobs with speedup functions (Edmonds 1999; Berg et al. 2018, 2020a, b, 2022). Here, each job has an associated speedup function that determines the job’s service rate on different numbers of servers. Of these papers, Berg et al. (2018, 2020a) focus on the case where there is only one class of jobs that all follow the same speedup function. The case of two classes of jobs is considered in Berg et al. (2020b, 2022), but jobs are assumed to be either nonparallelizable or fully parallelizable, and the results require highly restrictive assumptions about the job size distributions. Little is known in the case where jobs have more than two levels of parallelizability.

Some further-afield work on parallel scheduling has used different models and objectives to design scheduling policies. Work on directed acyclic graph (DAG) scheduling has considered the problem of scheduling parallelizable tasks with precedence constraints that are specified by the edges of a DAG (Blumofe and Leiserson 1999, Agrawal et al. 2008, 2016). Much of this work considers the problem of scheduling a single DAG (Blumofe and Leiserson 1999, Agrawal et al. 2008). For scheduling a stream of DAGs, only pessimistic worst-case bounds are known (Agrawal et al. 2016).

1.3. Tradeoff

As we saw in Section 1.2, SRPT-like policies that prioritize short jobs are optimal in conventional heavy traffic for a variety of multiserver scheduling models. However, when the system is not so heavily loaded, it is not obvious that favoring short jobs suffices for optimality. In particular, when scheduling malleable jobs, there is another consideration that is at least as important: deferring parallelizable work. Here, a scheduling policy can raise the long-run average utilization of the system by prioritizing less parallelizable jobs ahead of more parallelizable jobs. The benefits of deferring parallelizable work were first described in Berg et al. (2018), which considers a less complex model with just two classes of jobs.

To see the benefit of deferring parallelizable work, suppose we have a job, A, that can only use one server and a job, B, that can parallelize across all k servers. If we prioritize job B, there will be a period after B completes where job A runs and $k-1$ servers sit idle. To minimize mean response time, it is better to give one server to job A and use the remaining $k-1$ servers to run job B. This holds regardless of the sizes of the jobs. By prioritizing the less parallelizable job A, we defer working on the more parallelizable job B.

This raises the question of how to handle the tradeoff between favoring jobs that are shorter versus deferring parallelizable work. What does a policy do with a job that has a small expected remaining size, but is also highly parallelizable? Does the policy prioritize this job due to its small size, or defer working on this job because of its high parallelizability? To derive an optimal scheduling policy, we must compare the relative benefits of these two effects. We find that the optimal choice between prioritizing short jobs and deferring parallelizable work depends on the scaling behavior of the system. When the system scales such that queueing is rare, it is more important to defer parallelizable work. However, if the system scales such that the probability of queueing goes to one, it is more important to prioritize short jobs.

1.4. Contributions

This paper derives the first results on asymptotic optimality when scheduling many classes of parallelizable jobs. Specifically, this is the first work to develop asymptotically optimal policies when there are more than two classes of parallelizable jobs. We analyze the mean response time of $\mathcal{\ell }$ classes of jobs, each with a different level of parallelizability. We prove our results by considering how the system behaves under a variety of scaling regimes, where the number of servers goes to infinity and the system load goes to one simultaneously (see Section 2). Although our results rely on asymptotic analysis, the results cover a wide range of scaling regimes, including sub-Halfin-Whitt regimes and mean field (constant load) scaling. We find that the choice of an optimal policy depends on the chosen scaling regime. Specifically, our contributions are as follows.

• When the system load is not too heavy (sub-Halfin-Whitt), we show that the benefit of deferring parallelizable work outweighs the benefit of prioritizing short jobs. In this case, it is beneficial to use a least-parallelizable-first (LPF) policy that assigns the highest priorities to the least parallelizable classes of jobs. We show in Theorem 1 that LPF is asymptotically optimal with respect to mean response time. Furthermore, we show in Theorem 2 that it can be suboptimal to simply prioritize short jobs in these lighter-load scaling regimes.

• Conversely, when system load is very heavy (super-nondegenerate slowdown (NDS)), it is more important to prioritize short jobs by using the shortest-expected-remaining-processing-time (SERPT) policy as shown in Theorem 4. In these scaling regimes, there are almost always enough jobs to fully utilize all k servers. Hence, it is more important to minimize queueing times by using SERPT than it is to defer parallelizable work. As a result, we also prove in Theorem 5 that LPF can be suboptimal in these heavier-load scaling regimes.

• Although the above results suggest that one may need to know the system scaling behavior a priori to select an asymptotically optimal policy, we show that this is not the case. Specifically, we define a policy called Threshold (THRESH) that switches between LPF and SERPT depending on how many jobs are in the system. We show in Theorem 6 that THRESH can perform well in both sub-Halfin-Whitt and super-NDS scaling regimes by deferring parallelizable work (using LPF) when there are few jobs in the system and prioritizing short jobs (using SERPT) when there are many jobs in the system.

• Finally, we examine extensions to our theoretical results via simulation in Section 6.

2. Model

We model a system with k identical servers managed by a centralized scheduler. Arriving jobs are placed in a central queue. We consider the case where jobs are preemptible and malleable, meaning that the scheduler can change the number of servers on which a job runs over time. Although more complex architectures may exist, this scenario is common in a wide range of real-world systems that process parallelizable jobs.

Without loss of generality (WLOG), we assume each server runs at speed 1. We assume that each job belongs to one of $\mathcal{\ell }$ job classes. Each job class, i, has its own job size distribution, denoted by the random variable $S_i$, and parallelizability level, $c_i$.

A job’s size denotes its running time (service time) on a single server. We generally assume that job sizes are unknown and exponentially distributed, that is,

Our theoretical results assume exponential job sizes, but we discuss other size distributions in Section 6.2.

Class i jobs have a parallelizability level of $c_i$, meaning a class i job can run on up to $c_i$ servers. When a class i job is run on $m\le c_i$ servers, the job is served at rate m. As a result, this job’s remaining service time is distributed as $\text{Exp}(m·{\mu }_i)$.

We assume class i jobs arrive according to a Poisson process with rate ${\lambda }_i^{(k)}$, where the total arrival rate is ${\lambda }^{(k)}={\sum }_{i=1}^{\mathcal{\ell }}{\lambda }_i^{(k)}$. We define the system load as

The system is stable under any work-conserving scheduling policy if $\rho <1$ (Berg et al. 2020b).

2.1. Asymptotic Analysis

We analyze the system under several scaling regimes. In the conventional heavy traffic scaling regime, the number of servers, k, is held constant, and we take the limit as $\rho \to 1$. We will also consider several scaling regimes where $k\to \infty$ and the arrival rate, ${\lambda }^{(k)}$, scales with k, meaning that load, $\rho$, scales with k. See Appendix A for a summary of the standard asymptotic notation used in this paper.

We assume that the proportion of jobs from each class and the job size distributions remain fixed. That is, we define the constants $p_1,p_2,\dots ,p_{\mathcal{\ell }}$ such that

We restrict ourselves to scaling regimes where ${\lambda }^{(k)}=\mathrm{\Theta }(k)$ so that $\rho$ does not go to zero as we scale k.

It is convenient to describe the scaling behavior of ${\lambda }^{(k)}$ in terms of $\alpha$, the number of “spare servers” worth of capacity. Specifically, we define $\alpha$ to be

Note that, although $\alpha$ and $\rho$ depend on k, we omit this dependence from the notation for brevity. We will write expressions in terms of ${\lambda }^{(k)}$ when an explicit dependence on k requires emphasis.

The asymptotic behavior of many queueing systems is known to depend on the asymptotic behavior of $\alpha$. For example, consider a simple $M/M/k$ system. When $\alpha =\mathrm{\Theta }(k)$, the scaling regime is known as the large-system limit or mean-field limit. The probability of queueing in an $M/M/k$ goes to zero in the mean-field limit. When $\alpha =\mathrm{\Theta }(\sqrt{k})$, the scaling regime is known as the Halfin-Whitt regime (Halfin and Whitt 1981). The probability of queueing in an $M/M/k$ converges to a constant in the Halfin-Whitt regime, but the mean queueing time goes to zero. When $\alpha =\mathrm{\Theta }(1)$, the scaling regime is known as the NDS regime (Atar 2012, Gupta and Walton 2019). The probability of queueing in an $M/M/k$ goes to one in the NDS regime, and the mean queueing time converges to a constant. We refer to all scaling regimes where $\alpha =\omega (\sqrt{k\hspace{0.17em}\text{log}\hspace{0.17em}k})$ as sub-Halfin-Whitt scaling regimes.¹ In the sub-Halfin-Whitt regime, the probability of queueing in an $M/M/k$ goes to zero. We refer to all scaling regimes where $\alpha =o(1)$ as super-NDS regimes. The probability of queueing in an $M/M/k$ goes to one and the mean queueing time goes to $\infty$ in super-NDS regimes. Note that, under all super-NDS scaling regimes, $\rho \to 1$. Under the sub-Halfin-Whitt scaling regimes, $\rho$ either goes to one or converges to a constant less than one, as in mean-field scaling. It is not clear which, if any, of the results from the simple $M/M/k$ system hold when scheduling parallelizable jobs.

Although ${\rho }_i$ depends on k for each class i, ${\rho }_i$ asymptotically approaches a subcritical load. Specifically, let

where $0<{\rho }_i^{*}<1$ for any class i, and ${\sum }_{i=1}^{\mathcal{\ell }}{\rho }_i^{*}\le 1.$ Further, ${\sum }_{i=1}^{\mathcal{\ell }}{\rho }_i^{*}=1$ in any heavy-traffic scaling regime.

2.2. Scaling Parallelizability Levels

We previously stated that each job class, i, has an associated parallelizability level $c_i$. For some job classes, this parallelizability level results from algorithmic limitations or limitations of a job’s software implementation. For these job classes, the parallelizability level will not change as the system scales. However, other more-parallelizable classes of jobs can be easily reconfigured as the system scales to leverage newly available servers. We therefore allow the value $c_i$ to scale with k for some classes of jobs. In general, we allow each $c_i$ to be any nondecreasing function of k. In this way, we can represent a variety of real-world system constraints that might cause a job’s parallelizability level to grow sublinearly with k. For example, in a system with a complex network topology, it is common that only a fraction of the servers (e.g., $\sqrt{k}$) can communicate directly with one another. Hence, for a class of jobs with high communication overhead, the parallelizability level of the jobs might scale as $\sqrt{k}$.

WLOG, let the classes be asymptotically ordered by parallelizability so that, for sufficiently large k,

$c_1\le c_2\le \dots \le c_{\mathcal{\ell }}.$ Furthermore, we assume that $c_1=O(1)$, so at least one class of jobs requires a constant number of servers. This mild technical assumption holds in the vast majority of real-world systems. For simplicity, we assume that $c_1=1$, but setting $c_1$ to some other constant does not affect our results.

2.3. Scheduling Policies

A scheduling policy must decide, at every moment in time, how many servers to allocate to each job in the system. Let $\{N(t)\}$ be the stochastic process denoting the number of jobs in the system at time $t\ge 0$. Because we only consider scheduling policies that do not idle servers unnecessarily, $\rho <1$ implies that $\{N(t)\}$ is a positive-recurrent, irreducible continuous-time Markov chain. By ergodicity, there exists a distribution, N, such that $N(t)\stackrel{d}{\to }N$ as $t\to \infty$. N is the unique stationary distribution of $N(t)$ and $\mathbb{E}[N]<\infty$. We refer to $\mathbb{E}[N]$ as the mean number of jobs in system. We define $\{N_i(t)\}$, $N_i$, and $\mathbb{E}[N_i]$ analogously, but to describe class i jobs in the system. This gives $\mathbb{E}[N]={\sum }_{i=1}^{\mathcal{\ell }}\mathbb{E}[N_i]$. Let $X=(N_1,N_2,\dots ,N_{\mathcal{\ell }})$ denote the full state of the system in stationarity.

Let T denote the response time—the time from when a job arrives until it completes—of a job that arrives to a system whose state is drawn according to X. We refer to $\mathbb{E}[T]$ as the mean response time across jobs. By Little’s law, $\mathbb{E}\left[T\right]={\displaystyle \mathbb{E}\left[N\right]/{\displaystyle {\lambda }^{\left(k\right)}}}<\infty$. We similarly define $\mathbb{E}[T_i]$ to be the mean response time of a class i job, where $\mathbb{E}[T]={\sum }_{i=1}^{\mathcal{\ell }}\mathbb{E}[T_i]p_i$ by conditioning. Our goal is to find scheduling policies that minimize $\mathbb{E}[T]$ (or, equivalently, minimize $\mathbb{E}[N]$). We assume the scheduling policy knows the class information (${\mu }_i$ and $c_i$) for each job, as well as the system state.

Let $\mathbb{E}[T^{\pi }]$ denote the mean response time under any scheduling policy, $\pi$; $\pi$ is asymptotically optimal if

for all policies ${\pi }^{\prime }$. Again, the asymptotic optimality of a policy generally depends on the asymptotic behavior of $\alpha$. Asymptotic optimality is defined analogously in the conventional heavy traffic limit.

Our results primarily focus on analyzing two policies: one based solely on deferring parallelizable work and the other based solely on favoring short jobs. The policy that defers parallelizable work is called LPF. LPF preemptively prioritizes the jobs with the lowest parallelizability levels. For example, LPF will allocate as many servers as possible to jobs belonging to the first i classes before allocating any leftover servers to jobs in the $i+1$st class. The policy that favors short jobs is called the SERPT policy (Scully et al. 2020b), which at all times preemptively prioritizes the job with the smallest expected remaining size. Recall that a job’s size is its running time on a single server. The SERPT policy allocates as many servers as can be used to the job with the smallest expected remaining size before allocating any servers to the next larger size job.

We also introduce a new policy called THRESH, which is the first policy to dynamically combine the orthogonal goals of deferring parallelizable work and favoring short jobs. THRESH runs LPF when the number of jobs in the system is small and runs SERPT when the number of jobs is large. We will fully define THRESH in Section 5.

In analyzing these policies, we use a combination of coupling and drift arguments.

3. Scheduling Parallelizable Jobs in sub-Halfin-Whitt Regimes

In this section, we consider scheduling in the sub-Halfin-Whitt scaling regimes described in Section 2. We begin by showing that LPF, the policy that defers parallelizable work by prioritizing the least parallelizable jobs, is asymptotically optimal in this case. Intuitively, in the lighter-load sub-Halfin-Whitt scaling regimes where queueing is rare, the benefit of prioritizing short jobs ahead of long jobs is reduced. Furthermore, because there will frequently be fewer than k jobs in the system under these scaling regimes, it is important to “save up” the more parallelizable jobs, which are better at occupying many servers when there are few jobs. LPF performs well because it keeps more servers occupied than other policies.

Given that there is little queueing in sub-Halfin-Whitt regimes, one might expect a wide variety of policies to be asymptotically optimal. However, we also show the surprising result that SERPT can be asymptotically suboptimal in sub-Halfin-Whitt regimes. If SERPT happens to prioritize very parallelizable jobs that fully utilize the system, all the other jobs in the system are forced to queue unnecessarily. The system is then underutilized when running less-parallelizable jobs. Hence, the choice of scheduling policy greatly affects the overall mean response time of the system, even in sub-Halfin-Whitt scaling regimes.

We begin by showing the asymptotic optimality of LPF in Theorem 1.

Theorem 1.

If $\alpha =\omega (\sqrt{k\hspace{0.17em}\text{log}\hspace{0.17em}k})$, then for any scheduling policy $\pi$,

$$\underset{k\to \infty }{\text{lim}}\hspace{0.17em}\frac{\mathbb{E}\left[T^{\pi }\right]}{\mathbb{E}\left[T^{\mathit{\text{LPF}}}\right]}\ge 1.$$

That is, LPF is asymptotically optimal with respect to mean response time in sub-Halfin-Whitt scaling regimes.

We will prove Theorem 1 via Lemmas 1, 2, and 3. We first outline our argument at a high level. Then, we prove the necessary lemmas before proving Theorem 1.

We will prove that, for each class of jobs i, the mean response time of class i jobs under LPF approaches some lower bound as $k\to \infty$, and thus the overall mean response time under LPF is asymptotically optimal. When analyzing LPF in this section, we will omit the LPF superscript for the sake of readability.

For any class, i, it is desirable to have more than ${\rho }_{i}k$ servers working on class i jobs. In this case, class i jobs are being completed at a rate greater than ${\mu }_i{\rho }_{i}k={\lambda }_i^{(k)}$, and hence the number of class i jobs in the system will tend to decrease. Given a system with $\alpha$ spare servers, it is theoretically possible to guarantee that ${\rho }_{i}k+\alpha {\displaystyle /\mathcal{\ell }}$ servers are available to class i jobs for all classes, i. Our goal is to prove that LPF guarantees this property with high probability, and therefore it is usually possible to complete class i jobs at a very fast rate. We then argue that this is sufficient to keep the average number of class i jobs in the system very low.

We divide the $\mathcal{\ell }$ job classes into two cases. First, we consider all the job classes whose level of parallelism, $c_i=O(1)$. We call these inelastic (I) jobs, because their level of parallelism does not scale with k. Second, we consider all the job classes whose level of parallelism $c_i=\omega (1)$. We refer to these as elastic (E) jobs.

To handle any inelastic job class, i, we argue in Lemma 1 that the probability of having a large number of jobs belonging to the first $i-1$ job classes goes to zero very quickly as $k\to \infty$. As a result, LPF almost always devotes a sufficient number of servers to the class i jobs. This allows us to show in Lemma 2 that the mean response time of class i jobs is asymptotically optimal.

We use a similar argument to prove the asymptotic optimality for elastic jobs in Lemma 3. However, we can prove this result for all elastic classes simultaneously instead of treating the classes one by one as we did for the inelastic classes. The proof of Theorem 1 follows easily from Lemmas 2 and 3.

The key to proving these lemmas is that we have $\alpha /\mathcal{\ell }$ spare servers to devote to each class. Roughly, this means the LPF policy can tolerate fluctuations in the number of class i jobs on the order of $\alpha$ without having these jobs interfere significantly with the service of lower priority jobs. In sub-Halfin-Whitt scaling regimes, we assume $\alpha =\omega (\sqrt{k\text{\hspace{0.17em}log\hspace{0.17em}}k})$. Hence, our proofs use drift arguments to recover a well-known form of result—that fluctuations in the number of class i jobs larger than $O(\sqrt{k})$ are rare as $k\to \infty$.

We define ${\beta }_i$ to be the smallest number of class i jobs that can fully utilize ${\rho }_{i}k+\alpha /\mathcal{\ell }$ servers, giving

We begin with the following lemma that the number of class i jobs rarely exceeds ${\beta }_i$ for any inelastic class.

Lemma 1.

Let I be the highest number such that $c_I=O(1)$. For any class of jobs, $i\le I$, let ${\mathcal{E}}_i$ be the set of states defined as

$${\mathcal{E}}_i=\{(n_1,n_2,\dots n_{\mathcal{\ell }}):n_j<{\beta }_j,\forall 1\le j\le i\}.$$

In sub-Halfin-Whitt scaling regimes,

$$\text{Pr}((N_1,N_2,\dots ,N_{\mathcal{\ell }})\notin {\mathcal{E}}_i)=o\left(\frac{1}{k^3}\right)\hspace{1em}\forall i\le I.$$(1)

Proof.

We will prove (1) by induction on the job class, i. Specifically, we will prove the following two properties by simultaneous induction. First, we will show there exist constants $d_j^{(i)}$ and $f_j^{(i)}>0$ such that

$$\text{Pr}(N_i\ge {\beta }_i)={\displaystyle \sum _{j=1}^i{f}_j^{(i)}}{\left(\frac{k}{\alpha }\right)}^{j-1}{e}^{-d_j^{(i)}{\alpha }^2/k}\hspace{1em}\forall i\le I.$$(2)

Second, for some constants $g_j^{(i)}>0$ and $h_j^{(i)}>0$, we will show that

$$\text{Pr}((N_1,N_2,\dots ,N_{\mathcal{\ell }})\notin {\mathcal{E}}_i)\le {\displaystyle \sum _{j=1}^i{g}_j^{(i)}}{\left(\frac{k}{\alpha }\right)}^{j-1}{e}^{-h_j^{(i)}{\alpha }^2/k}\hspace{1em}\forall i\le I.$$(3)

Once we have established (2) and (3), we note $\alpha =\omega (\sqrt{k\text{\hspace{0.17em}log\hspace{0.17em}}k})$ in the sub-Halfin-Whitt scaling regimes and thus $\frac{{\alpha }^2}{k}=\omega \left(\text{log}\hspace{0.17em}k\right)$. Note that, for any constant $x>0$, ${\alpha }^2/k=\omega (x\hspace{0.17em}\text{log}\hspace{0.17em}k)=\omega (\text{log}\hspace{0.17em}{k}^x)$. Hence, by setting $x=(j+2)/h_j^{\left(i\right)}$, (3) implies

$$g_j^{(i)}{\left(\frac{k}{\alpha }\right)}^{j-1}·e^{-h_j^{(i)}{\alpha }^2/k}=o\left(\frac{1}{k^3}\right)$$

for any $i,j\le I$, as desired.² We require (2) as part of our inductive proof.

Our inductive proof of (2) and (3) relies on the drift bounds established in Wang et al. (2022). These bounds require one to define a Lyapunov function $V(x)$, that takes a system state $x=(n_1,n_2,\dots n_{\mathcal{\ell }})$ and returns a real number. The goal is to choose a Lyapunov function such that, for a state x, the instantaneous rate of change of $\mathbb{E}[V(X)|X=x]$, known as the Lyapunov drift, is almost always negative. Specifically, if the instantaneous rate of change of $\mathbb{E}[V(X)|X=x]$ is negative whenever $V(x)>B$, Wang et al. (2022) provides bounds on $\text{Pr}(V(X)>B)$ (see Appendix B for a precise statement). We set $V(x)=n_1$ to bound $\text{Pr}(N_1>B)$ and prove the base case for our induction ($i=1$). To prove our claims inductively for class $i+1$ jobs, we set $V(x)=n_{i+1}$. Here, we must account for the fact that there may be many lower-class jobs in the system preventing the class $i+1$ jobs from running and causing positive drift, even when $V(x)$ is large. To handle this issue, we exploit a stronger drift bound (see Appendix C for a precise statement) that tolerates some positive drift as long as the states with positive drift occur with bounded probability. The problematic states in this scenario are exactly $\{x\notin {\mathcal{E}}_i\}$. Our inductive hypothesis holds that $\text{Pr}(X\notin {\mathcal{E}}_i)$ is small, resulting in the desired bounds on $\text{Pr}(N_{i+1}>B)$ and $\text{Pr}(X\notin {\mathcal{E}}_{i+1})$.

To prove both statements when $i=1$, we define the Lyapunov function $V(x)=n_1$. When $n_1\ge {\rho }_{1}k+\alpha /2\mathcal{\ell }$, the drift of the Lyapunov function, $\mathrm{\Delta }V$, is

$$\mathrm{\Delta }V(x)={\lambda }_1^{(k)}-{\mu }_1·n_1\le {\lambda }_1^{(k)}-{\mu }_1({\rho }_{1}k+\frac{\alpha }{2\mathcal{\ell }})=-{\mu }_1\frac{\alpha }{2\mathcal{\ell }}.$$

Hence, the drift bound from Appendix B yields

$$Pr(N_1\ge {\beta }_1)\le Pr\left(N_1\ge {\rho }_{1}k+\frac{\alpha }{\mathcal{\ell }}\right)\le f_1^{(1)}{e}^{-d_1^{(1)}{\alpha }^2/k}$$

for some constant $d_1^{(1)}>0$ and $f_1^{(1)}=1$. This proves both (2) and (3) when $i=1$.

Now, we inductively assume that (2) and (3) hold for the first i job classes. If the Lyapunov function $V\left(x\right)=n_{i+1}>{\rho }_{i+1}k+\alpha /2\mathcal{\ell }$, the drift is positive if and only if $x\notin {\mathcal{E}}_i$; otherwise, the drift is negative. We can therefore use the modified drift bound from Appendix C to get the bound

$$\text{Pr}(N_{i+1}\ge {\beta }_{i+1})\le f_{i+1}^{(i+1)}{e}^{-d_{i+1}^{(i+1)}{\alpha }^2/k}+O\left(\frac{k}{\alpha }\right)Pr(X\notin {\mathcal{E}}_i)$$

for some constants $d_{i+1}^{(i+1)}>0$ and $f_{i+1}^{(i+1)}>0$.

Using our inductive hypothesis to bound $\text{Pr}(X\notin {\mathcal{E}}_i)$, we see that there exist some new constants $f_j^{(i+1)}$ and $d_j^{(i+1)}$ for all $1\le j\le i+1$ such that (2) holds for the $i+1$st class of jobs.

Finally, to prove (3) for the $i+1$st class, we note that

$$\text{Pr}(X\notin {\mathcal{E}}_{i+1})=Pr\left({\displaystyle \underset{j=1}{\overset{i+1}{\cup }}{N}_j}>{\beta }_j\right)\le Pr(X\notin {\mathcal{E}}_i)+Pr(N_{i+1}>{\beta }_{i+1})\le {\displaystyle \sum _{j=1}^{i+1}{g}_j^{(i+1)}}{\left(\frac{k}{\alpha }\right)}^{j-1}{e}^{-h_j^{(i+1)}{\alpha }^2/k}$$

for some new set of constants $g_j^{(i+1)}>0$ and $h_j^{(i+1)}>0$. This completes the proof by induction. □

We now use Lemma 1 to prove the optimality of the inelastic response times via a drift argument.

Lemma 2.

For any class $i\le I$, if $\alpha =\omega (\sqrt{k\text{\hspace{0.17em}log\hspace{0.17em}}k})$, then

$$\underset{k\to \infty }{\text{lim}}\hspace{0.17em}\mathbb{E}\left[T_i^{\mathit{\text{LPF}}}\right]=\frac{1}{c_i{\mu }_i}.$$

Proof.

Let $K_i$ be the number of servers that process class i jobs under LPF in a random state $X=(N_1,N_2,\dots ,N_i)$ in the stationary regime. Let ${\theta }_i=\lceil \frac{{\rho }_{i}k+\text{log}\hspace{0.17em}k}{c_i}\rceil$ be the number of class i jobs required to use slightly more than the average number of class i servers. The number of servers used by ${\theta }_i$ class i jobs is at most ${\rho }_{i}k+\text{log}\hspace{0.17em}k+c_i$ due to rounding. We also define ${\delta }_i={(N_i-{\theta }_i)}^{+}$, where ${(·)}^{+}$ denotes $\text{max}(·,0)$ (i.e., the positive part).

Intuitively, although class i jobs use ${\rho }_{i}k$ servers on average, Lemma 1 suggests that it should be rare for the class i jobs to use ${\rho }_{i}k+\text{log}\hspace{0.17em}k$ servers. We will use Lemma 1 to show that $\mathbb{E}[{\delta }_i]\to 0$ and hence $\mathbb{E}[N_i]$ is at most ${\theta }_i$ as k becomes large. We then apply Little’s law to this bound to finish our proof.

Formally, we will make a drift argument using the Lyapunov function $V(x)={({(n_i-{\theta }_i)}^{+})}^2$ so that $V(X)={\delta }_i^2$. Following standard techniques (Bertsimas et al. 1994, Eryilmaz and Srikant 2012, Wang et al. 2022, Xu 2023), we define $\mathrm{\Delta }V(x)={\sum }_{x^{\prime }\in \chi :x\ne x^{\prime }}{q}_{x{x}^{\prime }}(V(x^{\prime })-V(x))$, note that $\mathbb{E}[\mathrm{\Delta }V(X)]=0$, and use this equation to obtain the desired bounds.³ See Section EC.1 of the Online Appendix for a full overview of this technique.

To obtain $\mathrm{\Delta }V(X)$, note that ${\delta }_i$ does not change for small values of $N_i$. If an arrival occurs when there are fewer than ${\theta }_i$ jobs, nothing changes. Similarly, unless there are strictly more than ${\theta }_i$ jobs, nothing changes on a departure either. This gives

$$\mathrm{\Delta }V(X)={\mathrm{𝟙}}_{\left(N_i\ge {\theta }_i\right)}{\lambda }_i^{(k)}(2{\delta }_i+1)+{\mathrm{𝟙}}_{\left(N_i>{\theta }_i\right)}{\mu }_i{K}_i(-2{\delta }_i+1).$$

Setting $\mathbb{E}[\mathrm{\Delta }V(X)]=0$ then gives

$$\mathbb{E}[2{\mathrm{𝟙}}_{\left(N_i\ge {\theta }_i\right)}{\lambda }_i^{(k)}{\delta }_i+{\mathrm{𝟙}}_{\left(N_i\ge {\theta }_i\right)}{\lambda }_i^{(k)}+{\mathrm{𝟙}}_{\left(N_i>{\theta }_i\right)}{\mu }_i{K}_i]=\mathbb{E}[2{\mathrm{𝟙}}_{\left(N_i\ge {\theta }_i\right)}{\mu }_i{K}_i{\delta }_i].$$(4)

We now claim that $\mathbb{E}[{\mathrm{𝟙}}_{(N_i>{\theta }_i)}{\mu }_i{K}_i]=\mathbb{E}[{\mathrm{𝟙}}_{(N_i\ge {\theta }_i)}{\lambda }_i^{(k)}]$. Here, we use a similar drift argument (see Section EC.1 in the Online Appendix), this time using the Lyapunov function $G(x)={\delta }_i$.⁴ This gives

$$\begin{array}{l}\mathrm{\Delta }G(X)={\mathrm{𝟙}}_{\left(N_i\ge {\theta }_i\right)}{\lambda }_i^{(k)}-{\mathrm{𝟙}}_{\left(N_i>{\theta }_i\right)}{\mu }_i{K}_i.\\ \mathbb{E}[\mathrm{\Delta }G(X)]=\mathbb{E}[{\mathrm{𝟙}}_{\left(N_i>{\theta }_i\right)}{\mu }_i{K}_i]-\mathbb{E}[{\mathrm{𝟙}}_{\left(N_i\ge {\theta }_i\right)}{\lambda }_i^{(k)}]=0\end{array}$$(5)

as desired.

Applying (5) to (4) yields

$$\mathbb{E}[{\mathrm{𝟙}}_{\left(N_i\ge {\theta }_i\right)}{\lambda }_i^{(k)}{\delta }_i+{\mathrm{𝟙}}_{\left(N_i\ge {\theta }_i\right)}{\lambda }_i^{(k)}]=\mathbb{E}[{\mathrm{𝟙}}_{\left(N_i\ge {\theta }_i\right)}{\mu }_i{K}_i{\delta }_i].$$(6)

Now, noting that ${\mathrm{𝟙}}_{(N_i\ge {\theta }_i)}{\delta }_i={\delta }_i$, we have

$${\lambda }_i^{(k)}Pr(N_i\ge {\theta }_i)+{\lambda }_i^{(k)}\mathbb{E}[{\delta }_i]={\mu }_i\mathbb{E}[K_i{\delta }_i].$$(7)

If $K_i$ and ${\delta }_i$ were independent, ${\mu }_i\mathbb{E}[K_i{\delta }_i]$ would equal ${\lambda }_i^{(k)}\mathbb{E}[{\delta }_i]$ because we know the long run completion rate of type i jobs equals the long run arrival rate of type i jobs in a stable system. Intuitively, however, ${\delta }_i$ and $K_i$ should be positively correlated—we should expect to use more servers on type i jobs when more type i jobs are in the system. Hence, to turn (7) into an upper bound on $\mathbb{E}[{\delta }_i]$, we will lower bound $\mathbb{E}[K_i{\delta }_i]$ to be significantly larger than ${\lambda }_i^{(k)}\mathbb{E}[{\delta }_i]$; $K_i$ and ${\delta }_i$ only move inversely when many lower-class jobs enter the system and prevent class i jobs from running. Hence, we can use our upper bound on $\text{Pr}(X\notin {\mathcal{E}}_{i-1})$ to argue that $K_i$ and ${\delta }_i$ are positively correlated and thus

$$\mathbb{E}[K_i{\delta }_i]\ge (\mathbb{E}[K_i]+\text{log} k)\mathbb{E}[{\delta }_i]-O(1)=({\rho }_{i}k+\text{log} k)\mathbb{E}[{\delta }_i]-O(1),\hspace{1em}\forall i\le I.$$(8)

This is shown formally in Appendix D. Plugging (8) into (7) yields

$${\lambda }_i^{(k)}+O(1)\ge ({\mu }_i(k{\rho }_i+\text{log} k)-{\lambda }_i^{(k)})\mathbb{E}[{\delta }_i]={\mu }_i \text{log} k\mathbb{E}[{\delta }_i],$$(9)

$$\frac{{\lambda }_i^{(k)}+O(1)}{{\mu }_i \text{log} k}\ge \mathbb{E}[{\delta }_i],$$(10)

for sufficiently large k. Hence,

$$\mathbb{E}[N_i]\le \mathbb{E}[{\delta }_i]+{\theta }_i\le o(k)+{\theta }_i,$$(11)

$$\mathbb{E}[N_i]\le o(k)+\frac{{\rho }_{i}k}{c_i}.$$(12)

Applying Little’s law gives

$$\mathbb{E}[T_i]=o(1)+\frac{1}{c_i{\mu }_i}.$$

Hence, for the first I classes, the mean response time of each class converges to a service time plus an additive term that goes to 0 as $k\to \infty$. Note that this mean service time represents the lowest possible mean service time for a class i job and is thus a lower bound on the mean response time for class i jobs. □

At this point, we have shown that the I jobs have asymptotically optimal mean response time in sub-Halfin-Whitt regimes. Now, we handle the remaining classes whose level of parallelizability scales with k.

Lemma 3.

For any class $i>I$, if $\alpha =\omega (\sqrt{k\hspace{0.17em}\text{log} k})$, then

$$\underset{k\to \infty }{\text{lim}} \hspace{0.17em}\mathbb{E}\left[T_i^{\mathit{\text{LPF}}}\right]=0.$$

Proof.

Recall that $c_i=\omega (1)$ for all classes of elastic (E) jobs. We will bound the response time of all elastic classes simultaneously. Let

$${\rho }_E={\displaystyle \sum _{j=I+1}^{\mathcal{\ell }}{\rho }_j}\hspace{1em}\hspace{1em}\text{and}\hspace{1em}\hspace{1em}{\lambda }_E^{(k)}={\displaystyle \sum _{j=I+1}^{\mathcal{\ell }}{\lambda }_j^{(k)}}.$$

Let $K_E$ be the combined number of servers used on any elastic job and let ${\mu }_{\mathit{\text{min}}}={\text{min}}_{i\in [I+1,\mathcal{\ell }]}{\mu }_i$. We will bound $\mathbb{E}[N_E]$, the expected number of total jobs of class $I+1$ or higher. Following our earlier argument, we want to exploit our bound on ${\mathcal{E}}_I$ to get an upper bound on $\mathbb{E}[N_E]$.

Rather than tracking the number of jobs directly, we will track the expected sum of the sizes of elastic jobs in the system. We refer to this quantity as the expected work from elastic jobs, $W_E$. This quantity can be written as

$$W_E={\displaystyle \sum _{j=I+1}^{\mathcal{\ell }}\frac{N_j}{{\mu }_j}}.$$

Let ${\theta }_E=\frac{{\rho }_{E}k+\text{log}\hspace{0.17em}k}{c_{I+1}{\mu }_{\mathit{\text{min}}}}$ and let ${\delta }_E={(W_E-{\theta }_E)}^{+}$. Furthermore, let ${\delta }_E(x)$ be the value of ${\delta }_E$ given that the system is in state x.

Note that we divide by $c_{I+1}$ to be pessimistic about how many servers each job uses. We will develop a bound on $\mathbb{E}[{\delta }_E]$ and use this bound to recover a bound on $\mathbb{E}[N_E]$. The key to this lemma is that ${\theta }_E=o(k)$ because $c_{I+1}=\omega (1)$. Hence, we can stand to pick up a ${\theta }_E$ term in our bound on $\mathbb{E}[N_E]$, and this term will be dominated by ${\lambda }_E^{(k)}$ when applying Little’s law.

We will now use the drift argument of Section EC.1 in the Online Appendix with the Lyapunov function $V(x)={({\delta }_E(x))}^2$. This yields

$$\mathrm{\Delta }V(X)={𝟙}_{\left(W_E\ge {\theta }_E\right)}\left({\displaystyle \sum _{j=I+1}^{\mathcal{\ell }}\frac{2{\lambda }_j^{(k)}}{{\mu }_j}}{\delta }_E+\frac{{\lambda }_j^{(k)}}{{\mu }_j^2}\right)+{𝟙}_{\left(W_E>{\theta }_E\right)}\left({\displaystyle \sum _{j=I+1}^{\mathcal{\ell }}-}2k_j{\delta }_E+\frac{k_j}{{\mu }_j}\right).$$

Once again setting $\mathbb{E}[\mathrm{\Delta }V(X)]=0$,⁵ we get

$$\mathbb{E}[{𝟙}_{\left(W_E\ge {\theta }_E\right)}{\delta }_{E}k{\rho }_E]+O(k)=\mathbb{E}[{𝟙}_{\left(W_E\ge {\theta }_E\right)}{\delta }_E{K}_E],$$(13)

$$k{\rho }_E\mathbb{E}[{\delta }_E]+O(k)=\mathbb{E}[{\delta }_E{K}_E],$$(14)

where the indicators on both sides vanish because they are redundant, and the terms without ${\delta }_E$ are aggregated into the $O(k)$. Hence, lower bounding $\mathbb{E}[{\delta }_E{K}_E]$ will give an upper bound on $\mathbb{E}[{\delta }_E]$.

Our argument now follows the proof of (8) (see Appendix D) to show that, for sufficiently large k,

$$\mathbb{E}[{\delta }_E{K}_E]\ge ({\rho }_{E}k+\text{log}\hspace{0.17em}k)\mathbb{E}[{\delta }_E]-O(1).$$

Adapting Lemma D.2 to prove this claim is straightforward and makes use of our bound on $\text{Pr}(X\notin {\mathcal{E}}_I)$.

Plugging this lower bound into (14) gives

$$O(k)+O(1)\ge ({\rho }_{E}k+\text{log\hspace{0.17em}}k)\mathbb{E}[{\delta }_E]-{\rho }_{E}k\mathbb{E}[{\delta }_E],$$(15)

$$\frac{O(k)+O(1)}{\text{log} k}\ge \mathbb{E}[{\delta }_E],$$(16)

$$o(k)=\mathbb{E}[{\delta }_E].$$(17)

To conclude, we note that

$$\mathbb{E}[W_E]\le \mathbb{E}[{\delta }_E]+\mathbb{E}[{\theta }_E]=\mathbb{E}[{\delta }_E]+o(k).$$

Let ${\mu }_{\mathit{\text{max}}}={\text{max}}_{i\in [I+1,\mathcal{\ell }]}{\mu }_i$. We then have

$$\mathbb{E}[N_E]={\displaystyle \sum _{j=I+1}^{\mathcal{\ell }}\mathbb{E}}[N_j]\le {\displaystyle \sum _{j=I+1}^{\mathcal{\ell }}\frac{\mathbb{E}[N_j]{\mu }_{\mathit{\text{max}}}}{{\mu }_j}}={\mu }_{\mathit{\text{max}}}\mathbb{E}[W_E].$$

Hence,

$$\mathbb{E}[N_E]\le {\mu }_{\mathit{\text{max}}}(\mathbb{E}[{\delta }_E]+o(k))=o(k).$$

Applying Little’s law, we have

$$\underset{k\to \infty }{\text{lim}}\hspace{0.17em}\mathbb{E}[T_E]=\underset{k\to \infty }{\text{lim}}\hspace{0.17em}\frac{\mathbb{E}[N_E]}{{\lambda }_E^{(k)}}=0.$$

This implies our claim, that the mean response time of class i jobs goes to 0 for all $i>I$. □

We now combine the above lemmas to complete our proof of Theorem 1.

Proof of Theorem 1.

By Lemmas 2 and 3, for any class, i, $\mathbb{E}[T_i^{\mathit{\text{LPF}}}]$ converges to a lower bound as k becomes large, because the mean response time of a job is lower bounded by its mean service time. Hence, the overall mean response time across jobs, which is a linear combination of the mean response times for each class, also converges to a lower bound. For any policy, $\pi$, this gives

$$\underset{k\to \infty }{\text{lim}}\frac{\mathbb{E}\left[T^{\pi }\right]}{\mathbb{E}\left[T^{\mathit{\text{LPF}}}\right]}\ge 1,$$

and thus LPF is optimal in sub-Halfin-Whitt scaling regimes. □

We conclude this section with Theorem 2, which shows that SERPT is asymptotically suboptimal in sub-Halfin-Whitt scaling regimes. That is, LPF outperforms SERPT (sometimes significantly) in sub-Halfin-Whitt scaling regimes.

Theorem 2.

There exists a set of job classes such that, when $\alpha =\omega (\sqrt{k\hspace{0.17em}\text{log}\hspace{0.17em}k})$,

$$\underset{k\to \infty }{\text{lim}}\frac{\mathbb{E}\left[T^{\text{SERPT}}\right]}{\mathbb{E}\left[T^{\text{LPF}}\right]}>1.$$

That is, SERPT can be strictly suboptimal in the sub-Halfin-Whitt regime.

Proof.

Consider the case where $\mathcal{\ell }=2$ with $c_1=1$, $c_2=k$, and ${\mu }_2>{\mu }_1$. We can easily see that the mean response time of class 2 jobs goes to zero under SERPT in the sub-Halfin-Whitt regime. Hence, to prove the suboptimality of SERPT, we must show that ${\text{lim}}_{k\to \infty }\mathbb{E}[T_1^{\text{LPF}}]<{\text{lim}}_{k\to \infty }\mathbb{E}[T_1^{\text{SERPT}}]$. Lemma 2 shows that, under LPF in the sub-Halfin-Whitt regime, the mean response time of a class 1 job converges to $1/{\mu }_1$. We will show that SERPT does not attain this lower bound on the mean response time of class 1 jobs in the sub-Halfin-Whitt regime.

We consider the case where ${\mu }_2>{\mu }_1$, so SERPT gives strict priority to class 2 jobs. Consider the behavior of one particular class 1 job. This class 1 job will be served for some random amount of time, $S_1$. The queueing time of the job is therefore at least the amount of time spent waiting behind class 2 jobs that arrive during its $S_1$ time in service. We define $A_{S_1}^{(2)}$ to be the number of class 2 arrivals during a (random) class 1 service time. We can then write

$$\mathbb{E}\left[T_1^{\text{SERPT}}\right]\ge \mathbb{E}\left[{\displaystyle \sum _{i=1}^{A_{S_1}^{(2)}}\frac{S_{2_i}}{k}}\right]+\mathbb{E}[S_1].$$

Clearly, each $S_{2_i}$ is independent and identically distributed (i.i.d.) and independent of $A_{S_1}^{(2)}$, so we have

$$\mathbb{E}\left[T_1^{\text{SERPT}}\right]\ge \mathbb{E}\left[A_{S_1}^{(2)}\right]\mathbb{E}\left[\frac{S_2}{k}\right]+\mathbb{E}[S_1].$$

We can then see that

$$\mathbb{E}\left[A_{S_1}^{(2)}\right]={\displaystyle {\int }_0^{\infty }{\mu }_1}{e}^{-{\mu }_{1}t}\mathbb{E}\left[A_{S_1}^{(2)}|S_1=t\right]dt={\displaystyle {\int }_0^{\infty }t}·{\mu }_1{e}^{-{\mu }_{1}t}·{\lambda }_2^{(k)}dt={\lambda }_2^{(k)}\mathbb{E}[S_1].$$

Thus,

$$\mathbb{E}\left[T_1^{\text{SERPT}}\right]\ge \frac{{\lambda }_2^{(k)}}{k}\mathbb{E}[S_2]\mathbb{E}[S_1]+\mathbb{E}[S_1]=\left({\rho }_2+1\right)\mathbb{E}[S_1]$$

and

$$\underset{k\to \infty }{\text{lim}}\hspace{0.17em}\mathbb{E}\left[T_1^{\text{SERPT}}\right]\ge \frac{(1+{\rho }_2^{*})}{{\mu }_1}>\underset{k\to \infty }{\text{lim}}\hspace{0.17em}\mathbb{E}\left[T_1^{\text{LPF}}\right].$$

Because SERPT achieves suboptimal mean response time for class 1 jobs as $k\to \infty$, the overall mean response time under SERPT is suboptimal in sub-Halfin-Whitt scaling regimes. □

4. Scheduling Parallelizable Jobs in Super-NDS Regimes

LPF performs optimally in sub-Halfin-Whitt scaling regimes because it defers parallelizable work in order to keep servers occupied. SERPT, on the other hand, performs suboptimally in these regimes. In super-NDS scaling regimes, this trend is reversed. Namely, in super-NDS scaling regimes, the mean queueing time becomes the dominant term in the mean response time. Because SERPT minimizes mean queueing time by prioritizing short jobs ahead of long jobs, we can show it is asymptotically optimal in this case. Not only does LPF fail to minimize mean queueing time, but the benefits of deferring parallelizable work are diminished in super-NDS regimes. Here, there are usually enough jobs in the system to keep all servers occupied, even without deferring parallelizable work. Hence, we show that LPF is suboptimal in super-NDS scaling regimes. Additionally, we will show that both results also apply in the conventional heavy traffic limit, where k is fixed and $\rho \to 1$.

The point of this section will be to prove Theorems 3, 4, and 5, which state that SERPT is optimal in conventional heavy traffic and super-NDS scaling regimes, whereas LPF can be suboptimal in these cases. We start by proving a preliminary lemma that will be used repeatedly in our proofs.

This preliminary lemma, Lemma 4, relates the mean number of jobs in a SERPT system to a lower bound on the optimal mean number of jobs in system. Specifically, we consider the lower bound of an optimal policy for a single-server preemptive system that runs at speed k. The optimal policy for this single-server system serves jobs one at a time in SERPT order (Van Mieghem 1995). We will refer to the optimal policy for the single-server system as SERPT-1 to emphasize that this is SERPT applied to a system with one fast server. The SERPT policy (without the 1) will continue to denote SERPT in our k-server system.

To describe the priority ordering of classes under SERPT and SERPT-1, let $\gamma =({\gamma }_1,{\gamma }_2,\dots ,{\gamma }_{\mathcal{\ell }})$ be a sequence such that

We now compare the expected number of jobs under SERPT in our k-server system to the expected number of jobs in the SERPT-1 system.

Lemma 4.

The expected number of jobs under SERPT in the k-server system can be bounded as $\mathbb{E}[N^{\text{SERPT}-1}]\le \mathbb{E}[N^{\text{SERPT}}]\le \mathbb{E}[N^{\text{SERPT}-1}]+k·\mathcal{\ell }.$

Proof.

The first part of our claim, that $\mathbb{E}[N^{\text{SERPT}-1}]\le \mathbb{E}[N^{\text{SERPT}}]$, holds because SERPT-1 is optimal for the single-server system. Any policy from the k-server system can be mimicked by the single-server system, so SERPT-1 must provide a lower bound on the optimal policy for the k-server system.

The rest of this proof is devoted to proving the claim that $\mathbb{E}[N^{\text{SERPT}}]\le \mathbb{E}[N^{\text{SERPT}-1}]+k·\mathcal{\ell }$. To prove this, we will track the total work in the system, W, for each policy. Specifically, let $W_i^{\pi }(t)$ be the total remaining size of all class i jobs in a system using the scheduling policy $\pi$ at time t. Furthermore, let $W_{\le {\gamma }_i}^{\pi }(t)$ be the total remaining size of job in classes ${\gamma }_1$ through ${\gamma }_i$ at time t. Finally, let ${\mathrm{\Delta }}_{\le {\gamma }_i}(t)$ be defined as

$${\mathrm{\Delta }}_{\le {\gamma }_i}(t)≔W_{\le {\gamma }_i}^{\text{SERPT}}(t)-W_{\le {\gamma }_i}^{\text{SERPT}-1}(t).$$

We can take expectations to get

$$\mathbb{E}\left[W_{\le {\gamma }_i}^{\text{SERPT}}\right]=\mathbb{E}\left[W_{\le {\gamma }_i}^{\text{SERPT}-1}\right]+\mathbb{E}[{\mathrm{\Delta }}_{\le {\gamma }_i}].$$

Our goal is to get upper and lower bounds on $\mathbb{E}[{\mathrm{\Delta }}_{\le {\gamma }_i}]$, and then use these bounds on the work in system to get a bound on the expected number of jobs in system.

First, it is easy to see that $\mathbb{E}[{\mathrm{\Delta }}_{\le {\gamma }_i}]\ge 0$. Consider any fixed arrival sequence of jobs and their associated sizes. This sequence corresponds to one possible sample path for all the random variables in the system. Assume for contradiction that, at some time t,

$$W_{\le {\gamma }_i}^{\text{SERPT}}(t)<W_{\le {\gamma }_i}^{\text{SERPT}-1}(t).$$

This implies that just before time t, the SERPT system completes work on classes ${\gamma }_1$ through ${\gamma }_i$ at a faster rate than the SERPT-1 system. However, the SERPT-1 system always completes this work at the maximal rate unless $W_{\le {\gamma }_i}^{\text{SERPT}-1}(t)=0$. This implies that

$$W_{\le {\gamma }_i}^{\text{SERPT}}(t)<0,$$

a contradiction. Because $W_{\le {\gamma }_i}^{\text{SERPT}}(t)\ge W_{\le {\gamma }_i}^{\text{SERPT}-1}(t)$ at any time t, for any arrival sequence of jobs, we have

$$\mathbb{E}\left[W_{\le {\gamma }_i}^{\text{SERPT}}\right]\ge \mathbb{E}\left[W_{\le {\gamma }_i}^{\text{SERPT}-1}\right]\hspace{1em}\hspace{1em}\forall 1\le i\le \mathcal{\ell }.$$

To derive an upper bound, we again consider any fixed arrival sequence of jobs. For any value of i, we partition this arrival sequence into “nonbusy” intervals where the SERPT system has fewer than k jobs in classes ${\gamma }_1$ through ${\gamma }_i$ and “busy” intervals where SERPT has more than k jobs from these classes. For any time $t_n$ in a nonbusy interval, it is clear that ${\mathrm{\Delta }}_{\le {\gamma }_i}(t_n)$ is at most the total remaining size of the at most k jobs in the SERPT system.

We now take expectations over all possible sample paths, giving

$$\mathbb{E}[{\mathrm{\Delta }}_{\le {\gamma }_i}(t_n)]\le \mathbb{E}\left[{\displaystyle \sum _{j=1}^{N_{\le {\gamma }_i}^{\text{SERPT}}(t_n)}{S}_{{\gamma }_i}^{(j)}}\right]\le k\mathbb{E}[S_{{\gamma }_i}],$$

where $\mathbb{E}[S_{{\gamma }_i}]$ is the expected size of a job from the class with the ith smallest expected job size. We are exploiting memorylessness here—the remaining size of each of the jobs in the SERPT system is exponentially distributed. Furthermore, because the classes are ordered by their expected job sizes, the remaining size of each job is stochastically less than or equal to $S_{{\gamma }_i}$.

We now use a similar argument to handle any time $t_b$ in a busy interval. For any time $t_b$, there exists some $t^{*}\le t_b$ that marks the start of the busy interval. At time $t^{*}$, ${\mathrm{\Delta }}_{\le {\gamma }_i}(t^{*})$ is at most the total remaining size of the (exactly) k jobs in the SERPT system. In the interval $[t^{*},t_b]$, the SERPT completes work at rate k, the maximal rate of work for both systems, so ${\mathrm{\Delta }}_{\le {\gamma }_i}(t_b)\le {\mathrm{\Delta }}_{\le {\gamma }_i}(t^{*})$. We again take expectations to find that, for any time $t_b$,

$$\mathbb{E}[{\mathrm{\Delta }}_{\le {\gamma }_i}(t_b)]\le k\mathbb{E}[S_{{\gamma }_i}].$$

Because our upper bound on ${\mathrm{\Delta }}_{\le {\gamma }_i}$ holds for any time $t\ge 0$, we have

$$\mathbb{E}[{\mathrm{\Delta }}_{\le {\gamma }_i}]\le k\mathbb{E}[S_{{\gamma }_i}]\hspace{1em}\hspace{1em}\forall 1\le i\le \mathcal{\ell }$$

and therefore

$$\mathbb{E}\left[W_{\le {\gamma }_i}^{\text{SERPT}}\right]\le \mathbb{E}\left[W_{\le {\gamma }_i}^{\text{SERPT}-1}\right]+k\mathbb{E}[S_{{\gamma }_i}]\hspace{1em}\hspace{1em}\forall 1\le i\le \mathcal{\ell }.$$

For class ${\gamma }_1$ jobs, we now immediately use our upper bound to get

$$\mathbb{E}\left[W_{{\gamma }_1}^{\text{SERPT}}\right]\le \mathbb{E}\left[W_{{\gamma }_1}^{\text{SERPT}-1}\right]+\frac{k}{{\mu }_{{\gamma }_1}}.$$

Because job sizes are exponential, we can divide this expression by the mean size of a class ${\gamma }_1$ job to get

$$\mathbb{E}\left[N_{{\gamma }_1}^{\text{SERPT}}\right]\le \mathbb{E}\left[N_{{\gamma }_1}^{\text{SERPT}-1}\right]+k.$$

For class ${\gamma }_i$ jobs where $1<i\le \mathcal{\ell }$, we have

$$\mathbb{E}\left[W_{\le {\gamma }_i}^{\text{SERPT}}\right]\le \mathbb{E}\left[W_{\le {\gamma }_i}^{\text{SERPT}-1}\right]+\frac{k}{{\mu }_{{\gamma }_i}}\hspace{1em}\hspace{1em}\text{and}\hspace{1em}\hspace{1em}\mathbb{E}\left[W_{\le {\gamma }_{i-1}}^{\text{SERPT}}\right]\ge \mathbb{E}\left[W_{\le {\gamma }_{i-1}}^{\text{SERPT}-1}\right].$$

We subtract the latter inequality from the former to yield

$$\mathbb{E}\left[W_{\le {\gamma }_i}^{\text{SERPT}}\right]-\mathbb{E}\left[W_{\le {\gamma }_{i-1}}^{\text{SERPT}}\right]\le \mathbb{E}\left[W_{\le {\gamma }_i}^{\text{SERPT}-1}\right]+\frac{k}{{\mu }_{{\gamma }_i}}-\mathbb{E}\left[W_{\le {\gamma }_{i-1}}^{\text{SERPT}-1}\right],$$(18)

$$\mathbb{E}\left[W_{{\gamma }_i}^{\text{SERPT}}\right]\le \mathbb{E}\left[W_{{\gamma }_i}^{\text{SERPT}-1}\right]+\frac{k}{{\mu }_{{\gamma }_i}}.$$(19)

We again divide by the average size of a class ${\gamma }_i$ job to get

$$\mathbb{E}\left[N_{{\gamma }_i}^{\text{SERPT}}\right]\le \mathbb{E}\left[N_{{\gamma }_i}^{\text{SERPT}-1}\right]+k\hspace{1em}\forall 1\le i\le \mathcal{\ell }\Rightarrow \mathbb{E}\left[N^{\text{SERPT}}\right]\le \mathbb{E}\left[N^{\text{SERPT}-1}\right]+k·\mathcal{\ell }$$

as desired. □

We are now ready to use Lemma 4 to prove Theorems 3 and 4.

Theorem 3.

Consider a system in the conventional heavy traffic limit as $\rho \to 1$. For any policy, $\pi$,

$$\underset{\rho \to 1}{\text{lim}}\frac{\mathbb{E}\left[T^{\pi }\right]}{\mathbb{E}\left[T^{\text{SERPT}}\right]}\ge 1.$$

That is, SERPT is asymptotically optimal in the conventional heavy traffic regime.

Proof.

To establish the optimality of SERPT in conventional heavy traffic, we note that for any policy $\pi$, $\mathbb{E}[T^{\pi }]\ge \mathbb{E}[T^{\text{SERPT}-1}]$. If we can show that

$$\underset{\rho \to 1}{\text{lim}}\hspace{0.17em}\frac{\mathbb{E}[T^{\text{SERPT}}]}{\mathbb{E}\left[T^{\text{SERPT}-1}\right]}=1,$$

then

$$\underset{\rho \to 1}{\text{lim}}\frac{\mathbb{E}[T^{\pi }]}{\mathbb{E}[T^{\text{SERPT}}]}=\underset{\rho \to 1}{\text{lim}}\frac{\mathbb{E}[T^{\pi }]}{\mathbb{E}[T^{\text{SERPT}}]}·\underset{\rho \to 1}{\text{lim}}\frac{\mathbb{E}[T^{\text{SERPT}}]}{\mathbb{E}\left[T^{\text{SERPT}-1}\right]}=\underset{\rho \to 1}{\text{lim}}\frac{\mathbb{E}[T^{\pi }]}{\mathbb{E}\left[T^{\text{SERPT}-1}\right]}\ge 1.$$

Hence, we now show that the $\mathbb{E}[T^{\text{SERPT}}]$ converges to the $\mathbb{E}[T^{\text{SERPT}-1}]$ as $\rho \to 1$.

We apply Little’s law to the result of Lemma 4, which yields

$$\mathbb{E}\left[T^{\text{SERPT}-1}\right]\le \mathbb{E}\left[T^{\text{SERPT}}\right]\le \mathbb{E}\left[T^{\text{SERPT}-1}\right]+O(1).$$(20)

The mean response time of the SERPT-1 system in conventional heavy traffic can be derived from standard results on priority queueing (e.g., (32.1) in Harchol-Balter (2013)), yielding

$$\underset{\rho \to 1}{\text{lim}}\mathbb{E}\left[T^{\text{SERPT}-1}\right]=\mathrm{\Theta }\left(\frac{1}{1-\rho }\right).$$

Combining these two results gives

$$\underset{\rho \to 1}{\text{lim}}\frac{\mathbb{E}[T^{\text{SERPT}}]}{\mathbb{E}[T^{\text{SERPT}-1}]}\le \underset{\rho \to 1}{\text{lim}}\frac{\mathbb{E}[T^{\text{SERPT}-1}]+O(1)}{\mathbb{E}[T^{\text{SERPT}-1}]}=\underset{\rho \to 1}{\text{lim}}1+O\left(1-\rho \right)=1.$$

Because the mean response time under SERPT converges to that of the SERPT-1 system, SERPT is optimal in conventional heavy traffic. □

We now extend our proof from conventional heavy traffic to cover all super-NDS scaling regimes.

Theorem 4.

If $\alpha =o(1)$, then for any policy, $\pi$,

$$\underset{k\to \infty }{\text{lim}}\frac{\mathbb{E}\left[T^{\pi }\right]}{\mathbb{E}\left[T^{\text{SERPT}}\right]}\ge 1.$$

That is, SERPT is asymptotically optimal in super-NDS scaling regimes.

Proof.

This argument closely follows the proof of Theorem 3. We again apply Lemma 4 to get (20). In super-NDS scaling regimes, we can again use a standard analysis of priority queueing systems to find that $\mathbb{E}\left[T^{\text{SERPT}-1}\right]=\mathrm{\Theta }(1/\alpha )$. This gives the analogous result that

$$\underset{k\to \infty }{\text{lim}}\frac{\mathbb{E}[T^{\text{SERPT}}]}{\mathbb{E}[T^{\text{SERPT}-1}]}\le \underset{k\to \infty }{\text{lim}}\frac{\mathbb{E}[T^{\text{SERPT}-1}]+O(1)}{\mathbb{E}[T^{\text{SERPT}-1}]}=\underset{k\to \infty }{\text{lim}}1+O\left(\alpha \right)=1.$$

Hence, SERPT is asymptotically optimal in super-NDS scaling regimes. □

To conclude this section, we show that LPF can fail to minimize mean queueing time and can therefore be asymptotically worse than SERPT in both conventional heavy traffic and super-NDS scaling regimes.

Theorem 5.

Consider a system with a constant number of servers, $k_0$, in conventional heavy traffic. There exists a set of job classes such that

$$\underset{\rho \to 1}{\text{lim}}\frac{\mathbb{E}\left[T^{\text{LPF}}\right]}{\mathbb{E}\left[T^{\text{SERPT}}\right]}>1.$$

Furthermore, in super-NDS scaling regimes where $\alpha =o(1)$, there exists a set of job classes such that

$$\underset{k\to \infty }{\text{lim}}\frac{\mathbb{E}\left[T^{\text{LPF}}\right]}{\mathbb{E}\left[T^{\text{SERPT}}\right]}>1.$$

That is, LPF can be strictly suboptimal in conventional heavy traffic and super-NDS scaling regimes.

Proof.

Consider the case where $\mathcal{\ell }=2$ with $c_1=1$, $c_2=k$, and ${\mu }_2>{\mu }_1$. We established that SERPT is optimal in conventional heavy traffic by showing that

$$\underset{\rho \to 1}{\text{lim}}\hspace{0.17em}\frac{\mathbb{E}\left[T^{\text{SERPT}}\right]}{\mathbb{E}\left[T^{\text{SERPT}-1}\right]}=1.$$

Given this result, we can prove the first part of our claim by showing that

$$\underset{\rho \to 1}{\text{lim}}\frac{\mathbb{E}\left[T^{\text{LPF}}\right]}{\mathbb{E}\left[T^{\text{SERPT}-1}\right]}>1\Rightarrow \underset{\rho \to 1}{\text{lim}}\frac{\mathbb{E}\left[T^{\text{LPF}}\right]}{\mathbb{E}\left[T^{\text{SERPT}}\right]}=\underset{\rho \to 1}{\text{lim}}\frac{\mathbb{E}\left[T^{\text{LPF}}\right]}{\mathbb{E}\left[T^{\text{SERPT}-1}\right]}·\frac{\mathbb{E}\left[T^{\text{SERPT}-1}\right]}{\mathbb{E}\left[T^{\text{SERPT}}\right]}=\underset{\rho \to 1}{\text{lim}}\frac{\mathbb{E}\left[T^{\text{LPF}}\right]}{\mathbb{E}\left[T^{\text{SERPT}-1}\right]}>1.$$

We will also make an analogous argument for the case of super-NDS scaling. We begin by proving a lower bound on the performance of LPF.

We refer to a single-server system of speed k that serves jobs in LPF order as an LPF-1 system. We compare the performance of LPF-1 to the performance of LPF in our original k-server system to get ${\text{lim}}_{\rho \to 1}\frac{\mathbb{E}\left[T^{\text{LPF}}\right]}{\mathbb{E}\left[T^{\text{LPF}-1}\right]}\ge 1.$ Similarly, in a super-NDS scaling regime, ${\text{lim}}_{k\to \infty }\frac{\mathbb{E}\left[T^{\text{LPF}}\right]}{\mathbb{E}\left[T^{\text{LPF}-1}\right]}\ge 1.$ These claims follow from a coupling argument similar to the proof of Lemma 4. The main difference is that we are assuming a different priority ordering of the job classes in this case, but this does not affect our coupling argument.

To complete the first part of our claim, we will show that in conventional heavy traffic,

$$\underset{\rho \to 1}{\text{lim}}\frac{\mathbb{E}\left[T^{\text{LPF}-1}\right]}{\mathbb{E}\left[T^{\text{SERPT}-1}\right]}>1.$$(21)

This will imply that

$$\underset{\rho \to 1}{\text{lim}}\frac{\mathbb{E}\left[T^{\text{LPF}}\right]}{\mathbb{E}\left[T^{\text{SERPT}-1}\right]}=\underset{\rho \to 1}{\text{lim}}\frac{\mathbb{E}\left[T^{\text{LPF}-1}\right]}{\mathbb{E}\left[T^{\text{SERPT}-1}\right]}·\frac{\mathbb{E}\left[T^{\text{LPF}}\right]}{\mathbb{E}\left[T^{\text{LPF}-1}\right]}>1.$$(22)

To show (21), we rewrite this claim in terms of class 1 and class 2 response times to get

$$\begin{array}{l}\frac{\mathbb{E}\left[T^{\text{LPF}-1}\right]}{\mathbb{E}\left[T^{\text{SERPT}-1}\right]}=\frac{p_1\mathbb{E}\left[T_1^{\text{LPF}-1}\right]+p_2\mathbb{E}\left[T_2^{\text{LPF}-1}\right]}{p_1\mathbb{E}\left[T_1^{\text{SERPT}-1}\right]+p_2\mathbb{E}\left[T_2^{\text{SERPT}-1}\right]}=\frac{p_1\frac{\mathbb{E}[S_1]}{k(1-{\rho }_1)}+p_2\mathbb{E}\left[T_2^{\text{LPF}-1}\right]}{p_2\frac{\mathbb{E}[S_2]}{k(1-{\rho }_2)}+p_1\mathbb{E}\left[T_1^{\text{SERPT}-1}\right]}=\frac{O(1)+p_2\mathbb{E}\left[T_2^{\text{LPF}-1}\right]}{O(1)+p_1\mathbb{E}\left[T_1^{\text{SERPT}-1}\right]}\hfill \\ =\frac{\frac{O(1)}{p_1\mathbb{E}\left[T_1^{\text{SERPT}-1}\right]}+\frac{p_2\mathbb{E}\left[T_2^{\text{LPF}-1}\right]}{p_1\mathbb{E}\left[T_1^{\text{SERPT}-1}\right]}}{\frac{O(1)}{p_1\mathbb{E}\left[T_1^{\text{SERPT}-1}\right]}+1}.\hfill & \hfill \end{array}$$

Hence, it suffices to show that

$$\mathbb{E}\left[T_1^{\text{SERPT}-1}\right]=\omega (1)$$(23)

and

$$\underset{\rho \to 1}{\text{lim}}\frac{p_2\mathbb{E}\left[T_2^{\text{LPF}-1}\right]}{p_1\mathbb{E}\left[T_1^{\text{SERPT}-1}\right]}>1.$$(24)

From standard techniques for analyzing single-server priority queues, we know that $\mathbb{E}\left[T_1^{\text{SERPT}-1}\right]=\mathrm{\Theta }\left(\frac{\rho }{1-\rho }\right)=\omega (1)$ as $\rho \to 1$, and that (24) holds when ${\mu }_2>{\mu }_1$. Combined, these two conditions prove (21) and (22), completing the first part of the theorem.

To prove our second claim, we make an analogous argument about super-NDS scaling, where all limits are taken as $k\to \infty$. Specifically, $\mathbb{E}\left[T_1^{\text{SERPT}-1}\right]=\mathrm{\Theta }\left(\frac{1}{\alpha }\right)$ under super-NDS scaling, so (23) still holds in this case. Similarly, we know from standard single-server queueing analysis that

$$\underset{k\to \infty }{\text{lim}}\hspace{0.17em}\frac{p_2\mathbb{E}\left[T_2^{\text{LPF}-1}\right]}{p_1\mathbb{E}\left[T_1^{\text{SERPT}-1}\right]}>1.$$(25)

Thus, we can conclude that

$$\underset{k\to \infty }{\text{lim}}\hspace{0.17em}\frac{\mathbb{E}\left[T^{\text{LPF}}\right]}{\mathbb{E}\left[T^{\text{SERPT}-1}\right]}=\underset{k\to \infty }{\text{lim}}\hspace{0.17em}\frac{\mathbb{E}\left[T^{\text{LPF}-1}\right]}{\mathbb{E}\left[T^{\text{SERPT}-1}\right]}·\frac{\mathbb{E}\left[T^{\text{LPF}}\right]}{\mathbb{E}\left[T^{\text{LPF}-1}\right]}=\underset{k\to \infty }{\text{lim}}\hspace{0.17em}\frac{\mathbb{E}\left[T^{\text{LPF}-1}\right]}{\mathbb{E}\left[T^{\text{SERPT}-1}\right]}>1.$$□

5. THRESH Policy

One limitation of our results thus far is that one may not know their system’s scaling regime. Theorems 1 and 4 suggest that one must know the system scaling behavior in order to select an asymptotically optimal policy. We therefore propose THRESH that dynamically chooses between LPF and SERPT without knowing the system scaling regime. THRESH toggles between LPF and SERPT depending on whether the number of jobs in the system exceeds some threshold, $\tau \approx k$. When the number of jobs in the system is less than $\tau$, THRESH uses LPF to defer parallelizable work and avoid idling servers. When the number of jobs in the system is at least $\tau$, THRESH uses SERPT to minimize queueing time.

Given two job classes with $c_1=1$ and $c_2=k$, we show that THRESH is asymptotically optimal in both sub-Halfin-Whitt and super-NDS regimes. Although our theoretical results are limited to this two-class case, we show in Section 6 that THRESH also performs well with additional inelastic and elastic classes of jobs.

The exact threshold value, $\tau$, affects the traffic regimes in which THRESH is asymptotically optimal. We show that when $\tau =\omega (k)$, THRESH is asymptotically optimal in sub-Halfin-Whitt and conventional heavy traffic regimes. Furthermore, THRESH is asymptotically optimal in any super-NDS regime where $\alpha =o(k/\tau )$. That is, the threshold value $\tau$ can be any function that is $\omega (k)$, but its exact order affects the optimality result in the super-NDS regime. For example, we can choose $\tau$ to be $\tau =k\hspace{0.17em}{\text{log}}^{*}k$, where ${\text{log}}^{*}$ is the iterated logarithm function. Then in the super-NDS regime, THRESH is asymptotically optimal when $\alpha =o(1/{\text{log}}^{*}k)$. Hence, THRESH can be asymptotically optimal in an arbitrarily large portion of the super-NDS regimes, depending on the choice of $\tau$. We state this formally in Theorem 6.

Theorem 6.

Consider the problem of scheduling $\mathcal{\ell }=2$ classes of parallelizable jobs with $c_1=1$ and $c_2=k$. Consider the THRESH policy with a threshold value $\tau =\omega (k)$. For any policy, $\pi$:

1. If $\alpha =\omega (\sqrt{k\hspace{0.17em}\text{log} k})$, then ${\text{lim}}_{k\to \infty }\frac{\mathbb{E}\left[T^{\pi }\right]}{\mathbb{E}\left[T^{\text{THRESH}}\right]}\ge 1.$

2. In a conventional heavy-traffic scaling regime, ${\text{lim}}_{\rho \to 1}\frac{\mathbb{E}\left[T^{\pi }\right]}{\mathbb{E}\left[T^{\text{THRESH}}\right]}\ge 1.$

3. If $\alpha =o(k/\tau )$, then ${\text{lim}}_{k\to \infty }\frac{\mathbb{E}\left[T^{\pi }\right]}{\mathbb{E}\left[T^{\text{THRESH}}\right]}\ge 1.$

Proof.

When ${\mu }_1\ge {\mu }_2$, LPF, SERPT, and THRESH are equivalent, and this result is immediate. Hence, we will assume that ${\mu }_1<{\mu }_2$. We prove the three claims of Theorem 6 here.

5.1. Proof of Claim 1

We first split the mean response time into two parts by conditioning on job class:

To prove the asymptotic optimality of THRESH, we begin by showing that ${\text{lim}}_{k\to \infty }\mathbb{E}[T_1^{\text{THRESH}}]=\frac{1}{{\mu }_1}$.

Our proof strategy is to prove that $\mathbb{E}[\#\hspace{0.17em}\text{class} 1 \text{jobs} \text{in} \text{queue}]=o(k)$. Specifically, let $N_1$ and $K_1$ be the number of class 1 jobs in the system and in service, respectively, in steady state. Then we know that $\mathbb{E}[\#\hspace{0.17em}\text{class} 1 \text{jobs} \text{in} \text{queue}]=\mathbb{E}[N_1]-\mathbb{E}[K_1]=\mathbb{E}[N_1]-k{\rho }_1$, where we have used the fact that $\mathbb{E}[K_1]=k{\rho }_1$, which can be verified using Little’s law. Then $\mathbb{E}[N_1]-k{\rho }_1$ can be further upper bounded as

where $\delta$ is chosen such that $k{\rho }_1+\delta$ is an integer and $\delta =\mathrm{\Theta }(\sqrt{k})$, and the superscript ${}^{+}$ means taking the positive part, that is, $x^{+}=\text{max}\{x,0\}$ for any real number x. We assume that k is sufficiently large that $k{\rho }_1+\delta <k$. Inequality (26) can be verified by considering the two cases that $N_1-(k{\rho }_1+\delta )\ge 0$ and $N_1-(k{\rho }_1+\delta )<0$. We choose to bound $\mathbb{E}[N_1]-k{\rho }_1$ in this particular way because ${(N_1-(k{\rho }_1+\delta ))}^{+}$ effectively removes the dynamics of $N_1$ when $N_1<k{\rho }_1+\delta$, enabling us to focus on the more tractable scenario where $N_1\ge k{\rho }_1+\delta$. Note that $\delta =\mathrm{\Theta }(\sqrt{k})=o(k)$. Therefore, it suffices to prove $\mathbb{E}[{(N_1-(k{\rho }_1+\delta ))}^{+}]=o(k)$, which is the focus of the remainder of this proof.

We bound $\mathbb{E}[{(N_1-(k{\rho }_1+\delta ))}^{+}]$ using Lyapunov drift analysis. We consider the Lyapunov function $V(n_1,n_2)={({(n_1-(k{\rho }_1+\delta ))}^{+})}^2$ for any state $(n_1,n_2)$. Let $k_1$ denote the number of class 1 jobs in service when the state is $(n_1,n_2)$. Then the drift of V can be written as

We know that in steady state, $\mathbb{E}[\mathrm{\Delta }V(N_1,N_2)]=0$. Therefore,

We lower bound the left-hand-side term $\mathbb{E}[2{(N_1-(k{\rho }_1+\delta ))}^{+}({\mu }_1{K}_1-{\lambda }_1^{(k)})·1_{(N_1\ge k{\rho }_1+\delta +1)}]$. We abuse notation slightly and reuse $\text{LPF}$ to also denote the event that the system is running LPF, that is, the event that $N_1+N_2\le \tau$. Then,

where (28) is because $K_1\ge k{\rho }_1+\delta +1$ when LPF is in use and $N_1\ge k{\rho }_1+\delta +1$, and (29) is due to the equality ${(N_1-(k{\rho }_1+\delta ))}^{+}·1_{(N_1\ge k{\rho }_1+\delta +1)}={(N_1-(k{\rho }_1+\delta ))}^{+}$.

We now plug the lower bound (30) back into (27), which gives

Because the first term $\frac{{\lambda }_1^{(k)}+k{\mu }_1}{2{\mu }_1(\delta +1)}=o(k)$, it suffices to show the second term is also $o(k)$. To this end, we have

Here, (31) follows from the Cauchy-Schwarz inequality, and (32) follows from the same moment bound used in Appendix D. What remains is to bound $\text{Pr}({\text{LPF}}^c)$.

Recall that THRESH performs LPF if $N_1+N_2\le \tau$. Thus, $\text{Pr}({\text{LPF}}^c)=\text{Pr}(N_1+N_2>\tau )$. Given sufficiently large values of k,

where (33) uses the assumption that ${\mu }_1<{\mu }_2$ and $\tau =\omega (k)$. We consider the Lyapunov function $W(n_1,n_2)=n_1/{\mu }_1+n_2/{\mu }_2$. When $W(n_1,n_2)\ge \frac{k}{{\mu }_1}$, we have either at least k class 1 jobs or at least 1 class 2 job in service. This means all servers are busy under THRESH. Let $k_1$ and $k_2$ be the numbers of servers working on class 1 and class 2 jobs, respectively, in state $(n_1,n_2)$. Therefore, because $k_1+k_2=k$, we have

Then, using the same tail bound from Appendix B, we have

for some constant $d>0$ independent of k. Therefore,

Plugging this back into (32) yields

Putting everything together gives

Applying Little’s law then gives

To complete our proof, note that the response time of class 2 jobs under THRESH should intuitively be lower than their response time under LPF, because the number of servers devoted to class 2 jobs under THRESH is greater than or equal to the number of servers used for class 2 jobs by LPF in every state. Formally, we can prove this using a drift argument that is nearly identical to that of Lemma 3. Specifically, we pessimistically assume that class 2 jobs always get ${(k-N_1)}^{+}$ servers. Then, we bound the number of class 1 jobs using the modified tail bound from Appendix C. Here, we use our bound on $Pr({\text{LPF}}^c)$ to bound the probability of having positive drift in the number of class 1 jobs. From this point, the argument to bound $\mathbb{E}[N_2]$ is identical to the proof of Lemma 3, giving ${\text{lim}}_{k\to \infty }\mathbb{E}[T_2^{\text{THRESH}}]=0.$

Hence, the mean response time of both class 1 and class 2 jobs under THRESH is asymptotically optimal.

5.2. Proof of Claim 2

Our proof follows the general argument of Theorem 3 with some adjustments. Recall that in the proof of Theorem 3, we consider the SERPT-1 system, which uses a single server of speed k to run the optimal single-server policy that prioritizes jobs with the highest values of ${\mu }_i$.

For any scheduling policy $\pi$, ${\text{lim}}_{\rho \to 1}\frac{\mathbb{E}\left[T^{\pi }\right]}{\mathbb{E}\left[T^{\text{SERPT}-1}\right]}\ge 1.$ Therefore, to prove that ${\text{lim}}_{\rho \to 1}\frac{\mathbb{E}\left[T^{\pi }\right]}{\mathbb{E}\left[T^{\text{THRESH}}\right]}\ge 1$, it suffices to prove that ${\text{lim}}_{\rho \to 1}\frac{\mathbb{E}\left[T^{\text{SERPT}-1}\right]}{\mathbb{E}\left[T^{\text{THRESH}}\right]}=1.$ Because ${\text{lim}}_{\rho \to 1}\frac{\mathbb{E}\left[T^{\text{SERPT}-1}\right]}{\mathbb{E}\left[T^{\text{THRESH}}\right]}\le 1$, it suffices to prove that ${\text{lim}}_{\rho \to 1}\frac{\mathbb{E}\left[T^{\text{SERPT}-1}\right]}{\mathbb{E}\left[T^{\text{THRESH}}\right]}\ge 1.$

We first split the mean response time into two parts based on class 1 and class 2 jobs:

Intuitively, class 1 jobs should perform well under THRESH compared with the SERPT-1 system, because class 1 jobs always have low priority in the SERPT-1 system. Specifically, we can show that

To prove this, we compare THRESH to a single-server system of speed k that also runs THRESH. Using the same coupling argument from the proof of Theorem 3, we show that the single-server version of THRESH is within k jobs of the k server version of THRESH on average. Then, because the SERPT-1 system gives lower priority to class 1 jobs than THRESH, the SERPT-1 system must have more class 1 jobs than the single-server THRESH system on average. Taken together, these arguments yield (36). We then have

Next, we know from classical queueing theory that

We can also prove the following lemma, whose proof is given in Appendix E.

Lemma 5.

The mean response time of class 2 jobs under THRESH can be bounded as $\mathbb{E}[T_2^{\text{THRESH}}]\le \frac{2\tau }{k{\mu }_2{\rho }_2}+\frac{4}{k{\mu }_2{\rho }_2(1-{\rho }_2)}.$

To finish our proof, we can apply these bounds to (37), giving

5.3. Proof of Claim 3

To prove Claim 3, we can slightly modify our proof of Claim 2. Recall that for THRESH in super-NDS regimes, we have assumed $\alpha =o(k/\tau )$. Furthermore, we have that ${\text{lim}}_{k\to \infty }{\rho }_2={\rho }_2^{*}$ where ${\rho }_2^{*}$ is a constant. Therefore, in super-NDS regimes, the bound in (38) becomes $\mathbb{E}[T_1^{\text{SERPT}-1}]=\omega (\tau /k),$ and the upper bound in Lemma 5 becomes $\mathbb{E}[T_2^{\text{THRESH}}]=O(\tau /k).$ Applying these bounds to (37) (which remains the same) gives

Taken together, these three claims give Theorem 6. □

6. Evaluation

In this section, we evaluate our theoretical results via simulation. Although our theoretical results require some technical assumptions, we find that the high-level lessons from these theorems—deferring parallelizable work in lighter load and prioritizing short jobs in heavier load—apply more generally.

6.1. THRESH with Additional Classes

Although we prove the asymptotic optimality of THRESH in a special case of our model with $\mathcal{\ell }=2$ job classes, we conjecture that THRESH works well in general for any number of job classes with arbitrary levels of parallelizability. To validate this intuition, we simulate LPF, SERPT, and THRESH in various scaling regimes in Figure 1. Indeed, given $\mathcal{\ell }=4$ job classes with a variety of parallelizability levels, THRESH performs near-optimally in both sub-Halfin-Whitt and super-NDS scaling regimes.

Although our theoretical results only consider the sub-Halfin-Whitt and super-NDS scaling regimes, we simulated the performance of these policies in a middle scaling regime that lies between these cases for the sake of completeness. These results are presented in Appendix F.

6.2. General Job Size Distributions

We have thus far assumed that each class of jobs, i, is associated with some exponential job size distribution. It is not clear how our results generalize when job sizes are generally distributed.

First, consider scheduling generally distributed parallelizable jobs in conventional heavy traffic. Recent results (Scully et al. 2020a) have demonstrated that a Gittins index policy is optimal for scheduling nonparallelizable jobs in conventional heavy traffic. We find that these results hold when jobs are parallelizable. Specifically, Scully et al. (2020a) define a quantity called $B(r)$ that tracks the number of servers used to run jobs with a Gittins index of r or less. When moving from nonparallelizable jobs to parallelizable jobs, $B(r)$ does not decrease for any given system state, implying that the bounds from this work continue to hold when scheduling parallelizable jobs. The key fact exploited in Scully et al. (2020a) is that, when $B(r)$ is small because fewer than k servers are working on a job with Gittins index at most r, there must be at most $k-1$ rank r jobs in the system. When jobs are parallelizable, this same principle holds because we now assume that each job runs on at least one server. Following the arguments from Scully et al. (2020a), we find that prioritizing parallelizable jobs based on their Gittins indices is optimal in conventional heavy traffic.

Unfortunately, this argument does not generalize cleanly to other scaling regimes. The proof of heavy-traffic optimality in Scully et al. (2020a) relies on the analysis of SRPT in conventional heavy traffic from Lin et al. (2010). Currently, the behavior of SRPT in other scaling regimes is not well understood. We conjecture that a Gittins-based policy is asymptotically optimal in super-NDS scaling regimes, but a proof of this claim does not follow immediately from Scully et al. (2020a) and is beyond the scope of this paper.

Second, consider scheduling non–exponentially distributed jobs in sub-Halfin-Whitt scaling regimes. Given that our results hold for $\mathcal{\ell }$ exponential job classes, we conjecture that our results hold for phase-type job size distributions. Specifically, our current proof of the optimality of LPF bounds $\mathbb{E}[T_i]$ by showing that the departure rate of class i jobs is almost always greater than ${\lambda }_i^{(k)}$. Given jobs with phase-type distributions, we can use a similar argument to bound the time required to complete each phase of each type of job. However, when considering some phase, j, of class i jobs, the rate at which jobs enter phase j is not stationary—It depends on the number of class i jobs in service whose next phase could be j. Hence, we must argue that the completion rate of jobs in phase j is almost always greater than the time-varying rate at which jobs enter phase j. We can easily compute the long-run average rate at which jobs enter phase j, but we must show that the fluctuations around this average rate do not cause problems for a policy like LPF.

Although a proof for the case of phase-type job sizes is beyond the scope of this paper, we check via simulation to confirm that our conjecture is plausible. Figure 2 shows that our results appear to hold given jobs that follow different hyperexponential distributions with various levels of job size variability. Here, $C^2=1$ corresponds to the same exponential distributions as Figure 1. The larger values of $C^2$ denote that the job size distributions are balanced-mean hyperexponential distributions with the same mean job sizes but correspondingly higher squared coefficients of variation. We find that, although convergence appears slower as $C^2$ increases, LPF and THRESH appear to be asymptotically optimal in sub-Halfin-Whitt scaling regimes.

7. Conclusion

This paper presents the first theoretical results on balancing the tradeoff between prioritizing short jobs and deferring parallelizable work. Additionally, this paper provides the first optimality results on scheduling more than two classes of parallelizable jobs, where each class has its own job size distribution and parallelizability level. We show that the choice of an asymptotically optimal scheduling policy depends on the scaling regime chosen. LPF is asymptotically optimal in sub-Halfin-Whitt regimes, and SERPT is asymptotically optimal in super-NDS regimes. The THRESH policy, which combines LPF and SERPT, is asymptotically optimal in both sub-Halfin-Whitt and super-NDS scaling regimes.

We see two main avenues for extending our results. First, as discussed in Section 6.2, allowing jobs to follow arbitrary size distributions complicates our analysis. Existing techniques for analyzing $M/G/k$ systems with nonparallelizable jobs have only considered scheduling in conventional heavy traffic, and it remains unclear how to extend these results both to lighter-load scaling regimes and to scheduling parallelizable jobs. Second, we have assumed that our jobs are perfectly parallelizable up to some parallelizability level. In practice, however, jobs may receive a sublinear speedup from parallelization. Hence, although our results consider a work-conserving system, it is of great practical interest to analyze a non–work-conserving variant of our problem. We note that this generalization is related to the problem of state-dependent service rates (Ayesta et al. 2020) and the analysis of systems with Markov-Modulated service rates (Duran et al. 2022). We hope that the techniques and intuition developed in these papers can be applied to the problem of scheduling jobs with sublinear speedups.