Asymptotic Optimality of Switched Control Policies in a Simple Parallel Server System Under an Extended Heavy Traffic Condition

1. Introduction

1.1. Background

Parallel server systems (PSSs) are queueing control problems in which a number of servers offer service to customers of different classes, and choices as to which customer class each server is dedicated to are made dynamically. Since its introduction in Harrison and López (1999), its study in heavy traffic has attracted much attention, due to its simple structure, its practical significance, and the theoretical challenges it poses. The problem formulation in Harrison and López (1999) includes a key assumption, referred to as the heavy traffic condition (HTC), which states that an underlying “static allocation” linear program (LP) satisfies a critical load condition and that it has a unique solution. Whereas critical load is universally considered a defining condition of any notion of heavy traffic, uniqueness of solutions has been assumed mainly because it simplifies the mathematical treatment. The extended HTC (EHTC), which merely states that the LP is at criticality, but does not require uniqueness, has recently been introduced in Atar et al. (2024) in order to address a considerably broader notion of heavy traffic. The main result of Atar et al. (2024) is a lower bound on the asymptotically achievable cost in a general PSS under the EHTC. This paper focuses on the two-class, two-server PSS referred to in this introduction as the 2 × 2 PSS, which is the simplest case in which the EHTC is strictly broader than the HTC. The goal is to complement the results of Atar et al. (2024), in this case by constructing policies that asymptotically achieve the lower bound, which, hence, are asymptotically optimal (AO) in heavy traffic.

The structure of the 2 × 2 PSS is as follows. Each of the two servers is capable of serving each of the two classes. The classes (respectively, servers) are usually indexed using the symbol i (respectively, k) and activities, namely, class-server pairs, by $j=(i,k)$. Arriving customers await service in class-based queues and, upon receiving a single service, leave the system. The control decisions consist of routing (determining which server serves each customer) and sequencing (determining the order in which they are served). The rates of arrivals of customers of the two classes are denoted by ${\lambda }_i^n$, i = 1, 2, and the rates of service at each of the four activities are denoted by ${\mu }_{ik}^n$, where n denotes the usual heavy traffic parameter. These rates are assumed to be asymptotic to ${\lambda }_{i}n+{\widehat{\lambda }}_i{n}^{1/2}$ and ${\mu }_{ik}n+{\widehat{\mu }}_{ik}{n}^{1/2}$, for some given λ_i, ${\widehat{\lambda }}_i$, μ_ik, ${\widehat{\mu }}_{ik}$. The cost consists of an expected infinite horizon discounted linear combination of the two queue lengths and is rescaled at the diffusion scale.

Whereas the cost and, consequently, the notion of AO are set up at the diffusion scale, the underlying LP alluded to above addresses the behavior of the PSS at the fluid, or law-of-large-numbers (LLN), scale. Posed in terms of the first-order parameters, λ_i, μ_ik, it is concerned with the mean fraction of time devoted by each server to each class. When the LP has a unique solution, at least one activity is nonbasic, in the sense that the fraction allocated to it is zero. The so-called graph of basic activities (GBA), formed by the activities with positive allocation fraction, is static. In this case, the critical load condition dictates that any policy not adhering to this solution, in the sense of effort allocation, causes the total queue length to blow up and, in particular, cannot be AO. Under policies that adhere to this solution, the LLN assures that the aforementioned fractions of effort converge to those given by the LP solution (a necessary, but certainly not sufficient, condition for AO). When there are multiple LP solutions, a result from Atar et al. (2024) states that for the 2 × 2 PSS, the space of solutions, denoted by ${\mathcal{S}}_{\text{LP}}$, forms a line segment $\text{ch}({\xi }^{*,1},{\xi }^{*,2})$ in the space of 2 × 2 matrices (where “ch” denotes the convex hull). In each of the two extremal solutions, ${\xi }^{*,1},{\xi }^{*,2}$ there is again at least one nonbasic activity. We refer to these two extreme points as control modes, or simply modes. For similar reasons, any policy that does not lead to an unbounded cost should keep the system critically loaded at all times, and, thus, asymptotically, the fractions of effort will vary dynamically within ${\mathcal{S}}_{\text{LP}}$. In the control literature, a control process that takes values only at the vertices of the action space is called a bang-bang control. The analogue of this notion in our setting is a policy for which the limiting fractions of effort take values only in $\{{\xi }^{*,1},{\xi }^{*,2}\}$, switching between the two extremal solutions. Some of the policies introduced in this paper are designed to act that way.

Contrary to the setting where the HTC holds, it is impossible to construct an AO policy based only on the first-order data under the EHTC. A second-order approximation of the PSS, which is often referred to as a Brownian control problem (BCP), is required. The BCP represents a diffusion limit of the PSS, in which Brownian motion (BM) replaces stochastic fluctuations associated with cumulative arrival and service processes. Closely related to the BCP is another diffusion control problem, called a workload control problem (WCP). Obtained by a certain projection of the BCP, it is a control problem in which the process is one-dimensional, representing the total workload asymptotics. The structure of the WCP obtained is quite simple to describe. The state process is a reflected diffusion on ${\mathbb{R}}_{+}$, with controlled drift and diffusion coefficients, $b=b(\xi ),\hspace{0.17em}\sigma =\sigma (\xi )$, where the control process, $\xi ={\xi }_t$, takes values in ${\mathcal{S}}_{\text{LP}}$, and $\xi \mapsto (b(\xi ),\sigma {(\xi )}^2)$ is an affine map. The cost is given as an expected discounted version of the state process itself. By a standard argument based on the Hamilton-Jacobi-Bellman (HJB) equation, there exists an optimal bang-bang control for the WCP. There can therefore be two possibilities for the WCP solution: the single-mode case, where one of the modes is always used, and the dual-mode case, where both modes are used by the optimal control in different parts of the state space. Note that in this case, the GBA can be changed dynamically. The HJB equation also reveals the structure of the feedback function from state to control. This particular HJB equation was solved in Sheng (1978). It was shown that in the dual-mode case, there is a switching point $z^{*}\in (0,\infty )$, such that one of the modes is used when the state is below $z^{*}$ and the other otherwise. The HJB equation can be viewed, in this case, as an equation involving a free boundary, in which the solution is a pair, where one component is the value function and the other is $z^{*}$. The results of Sheng (1978) also characterize $z^{*}$ as the unique solution to an explicit equation, as well as a solution to the HJB equation.

Our policies are obtained by “translating” the WCP solution. In the case of a single mode, the prescribed policy corresponds either to a threshold policy of the form that first appeared in Bell and Williams (2001) (see below) or a simple priority policy, depending on the mode used and the cost. In the dual-mode case, pairs of elementary policies are identified, which are combined together to form switched control policies, so that one is active when the normalized workload process is below the switching point and the other above it. In each case, the policy is designed to meet the target allocation efforts determined by the corresponding mode, and the set of operational activities is restricted by the corresponding GBA.

The paper closest to ours is the aforementioned Bell and Williams (2001), which studies a two-server, two-class PSS with three activities. This PSS is known as an “N” network because upon relabeling, the activities are given by (1, 1), (1, 2), and (2, 2), forming the symbol N. (See Figure 1(a).) In this network, the number of solutions to the LP cannot exceed one, and, thus, the requirement of a unique solution does not pose a restriction. In an earlier work, Harrison (1998), it had been observed that when the larger “$c\mu$” value is in class 1, the BCP solution suggests that the queue length of class 1 customers and the idleness process at server 1 should both converge to zero at the diffusion scale and that a simple priority policy does not achieve this. In Bell and Williams (2001), this was addressed by putting a threshold on class 1 queue length that, when exceeded, server 2 prioritizes class 1, and otherwise it prioritizes class 2. The size of the threshold must converge to zero at the diffusion scale so as to achieve the first goal. To achieve AO of a threshold policy with logarithmic (in n) size threshold, as used in Bell and Williams (2001), the interarrival and service times are assumed there to possess exponential moments. (More on the history of the problem and the works that contributed to its development can be read in Atar et al. 2024.)

As already mentioned, one of the policies we implement is a threshold policy similar to the one used by Bell and Williams (2001). However, our assumptions are positioned differently with respect to the threshold-moment tradeoff, assuming a larger (still $o(\sqrt{n})$), polynomial size threshold, but requiring only a polynomial moment assumption. We assume $2+\epsilon$ moment assumptions for all of our policies except the single-mode threshold policy and the dual-mode policies that employ the threshold policy when the workload is above $z^{*}$. For these, a finite ${\mathbf{m}}_0$-th moment is assumed, where the number $4<{\mathbf{m}}_0<5$ is indicated explicitly. Another difference between our results and those of Bell and Williams (2001) is that our policies do not use preemption. Although the policy introduced in Bell and Williams (2001) uses preemption, it is plausible that an analogous nonpreemptive policy is also AO under similar conditions; see Corollary 2.15 and Remark 2.16. In this paper, our choice not to use preemption leads to nontrivial issues in the dual-mode case. Instead of a simple switching between elementary policies when the workload crosses $z^{*}$, it is sometimes the case that one must wait for a particular server to become available before switching. This is described in Section 5.1.3.

It is also worth mentioning that we have argued in Atar et al. (2024) that the AO of the threshold policy from Bell and Williams (2001) extends beyond the HTC to the case of multiple solutions and a single mode (under some assumptions, which include the existence of exponential moments).

Besides the objective to break the uniqueness barrier, an additional source of motivation for this work stems from the relation between nonuniqueness and service rate decomposability. As stated in Lemma 2.1, for the 2 × 2 PSS, the LP exhibits multiple solutions if and only if the service rates decompose as ${\mu }_{ik}={\alpha }_i{\beta }_k$. Service rates decompose this way when the mean size of a job is characteristic to the class (and then α_i is the reciprocal mean) and each server has its own processing speed (here given by β_k). As the HTC does not hold under decomposability, this important class of service rates has been left out by earlier work.

1.2. Results

The description of the policies given above is only a sketch. There are nontrivial issues that arise regarding the need to “patch” two policy types, requiring us to slightly modify the policies, where the details differ from one pairing to another.

The main result states that, under the prescribed policies, the rescaled workload process converges in law to the diffusion process that solves the WCP, and these policies are AO. As far as convergence is concerned, in addition to the “standard” issues involved in proving state-space collapse, we need to deal with issues related to switching control modes at $z^{*}$. Moreover, to obtain AO from weak convergence, uniform integrability needs to be established, and it is here where the $2+\epsilon$ and ${\mathbf{m}}_0$ moment assumptions are used.

An approach to proving convergence to a diffusion with discontinuous coefficients, addressing especially the technicalities involved with the discontinuity of the diffusion coefficient, was developed in Krylov and Liptser (2002), going beyond the general framework for convergence of semimartingales, such as that from Liptser and Shiriaev (1977). Whereas the tools from Krylov and Liptser (2002) are not directly applicable in our setting, an argument that, as in Krylov and Liptser (2002), shows that the time spent near the discontinuity set is negligible is also at the basis of our proof. The paper Krylov and Liptser (2002) also gives an example of a queueing model whose scaling limit yields a diffusion process with discontinuities in both drift and diffusion coefficients. Our dual-mode case provides what seems to be the first example where this occurs under an AO policy of a queueing control problem (for AO in heavy traffic leading to discontinuity in the drift only, see Atar and Lev-Ari 2018).

1.3. Organization of the Paper

In Section 2.1, we describe our model and the control problem associated with it in more detail. The LP and the extended heavy traffic condition are introduced in Section 2.2, and preliminary results about the LP from Atar et al. (2024) are stated. In Section 2.3, the WCP and the associated HJB equation are introduced, and in Proposition 2.6, it is stated that there exists a unique classical solution to the HJB equation. This proposition also provides a condition that determines whether an optimal solution to the WCP must employ a single mode or two modes (not to be confused with the number of modes in the space of LP solutions, which is always two under multiplicity) and asserts that in the dual-mode case, there exists a single switching point $z^{*}$ in workload space. We also present in this section the lower bound from Atar et al. (2024) stated in Theorem 2.4. The main result is stated in Section 2.4. The definitions of the proposed policies appear first, and then, in Theorem 2.13, the weak convergence and AO results are stated. Numerical results are presented in Section 2.5.

In Section 3, we state and prove some results related to the static allocation LP, providing, in particular, explicit expressions for the extreme points of the set of optimal solutions. Development of the WCP is carried out in Section 4. Preliminary results proved in Atar et al. (2024) in a general case are included in this section. This section also contains proofs of results related to the HJB equation, some of which rely on Sheng (1978).

The proof of our main result, Theorem 2.13, is the subject of Section 5. In Section 5.1, we present the general scheme for proving Theorem 2.13; the weak convergence result is stated in Theorem 5.1. We then present four propositions that are used for the proof. Each proposition corresponds to a specific section and step of the proof. Proposition 5.3, in Section 5.2.2, proves uniform integrability; state space collapse is proved in Proposition 5.4 in Section 5.2.3; a key nonidling property is proved in Proposition 5.5 in Section 5.2.4; and a “fast switching” property, showing the aforementioned property that the process spends asymptotically negligible time near the discontinuity, is proved in Proposition 5.6 in Section 5.2.6. Appendix A contains proofs of several lemmas stated earlier. Appendix B presents expressions from Sheng (1981) for the solution to the HJB equation. Finally, Appendix C contains a result providing symmetry conditions under which a single mode control is optimal.

1.4. Notation

$\mathbb{N},\hspace{0.17em}\mathbb{R}$, and ${\mathbb{R}}_{+}$ are the sets of natural, real, and, respectively, nonnegative real numbers. For $a,b\in \mathbb{R},\hspace{0.17em}a\vee b$ and $a\wedge b$ denote the maximum and minimum of a and b, respectively, and $a^{+}=a\vee 0$. For a set A, ${\mathrm{𝟙}}_A$ denotes its indicator function. For $f:{\mathbb{R}}_{+}\to \mathbb{R}$, and $t,\delta >0$, $\Vert f{\Vert }_t={\sup }_{s\in [0,t]}|f(s)|$ and

For $0\le s\le t$, the notation $f[s,t]$ stands for $f(t)-f(s)$. For real-valued functions and processes, the notation X(t) is used interchangeably with X_t. Given a Polish space E, $C_E[0,\infty )$ and $D_E[0,\infty )$ denote the spaces of E-valued, continuous and, respectively, càdlàg functions on $[0,\infty )$, equipped with the topology of convergence uniformly on compacts and, respectively, the J₁ topology. Denote by $C_{\mathbb{R}}^{+}[0,\infty )$ and $D_{\mathbb{R}}^{+}[0,\infty )$ the subset of $C_{\mathbb{R}}[0,\infty )$ and, respectively, $D_{\mathbb{R}}[0,\infty )$, of nonnegative, nondecreasing functions and by $C_{\mathbb{R}}^{0,+}[0,\infty )$ the subset of $C_{\mathbb{R}}^{+}[0,\infty )$ of functions that are null at zero. Write $X_n\Rightarrow X$ for convergence in law. A sequence of processes with sample paths in $D_E[0,\infty )$ is said to be C-tight if it is tight and the limit of every weakly convergent subsequence has sample paths in $C_E[0,\infty )$ almost surely (a.s.). The letter c denotes a deterministic constant whose value may change from one appearance to another.

2. Model and Main Results

The setup and results presented in this section have quite a few ingredients, as already mentioned in the introduction: the LP and modes, the diffusion scaling, the WCP and HJB equation, the switching point $z^{*}$, and threshold and switching policies. Before going into the details, we provide a roadmap. The two-class, two-server system, introduced in Section 2.1, is indexed by n and is observed at the diffusion scale. The assignment of jobs from the different classes to different servers is regarded as a control policy. A cost functional is considered, given by the expected discounted weighted sum of queue lengths, also rescaled at the diffusion scale; see Section 2.6. The weights of the queue lengths are given by a vector (h₁, h₂).

In order to formulate a policy-independent condition for heavy traffic, an LP (2.7) is introduced, involving first-order arrival and service rates, where the variable to be determined is a 2 × 2 allocation matrix describing the (first-order) fraction of effort each server dedicates to each class. It is assumed to be at criticality, in the sense that servers are fully occupied, but queue lengths stay balanced. In that regard, we adopt the heavy traffic notion of Harrison and López (1999) and many other papers that followed, with one important distinction: We do not assume that there is a unique allocation matrix that maintains criticality—that is, there may be multiple LP solutions. When there are multiple solutions, they are all given as convex combinations of two allocation matrices (Lemma 2.1), which we call modes. Because earlier work has addressed the unique solution case, we only treat the case of multiple solutions (Assumption 2.2). A result from Atar et al. (2024) states that under this assumption, the first-order rates μ_ik are necessarily decomposable as ${\alpha }_i{\beta }_k$. Each of the modes induces a so-called graph of basic activities, as in Figure 1. The parameters α_i and the structure of the graphs influence the type of control policy to be proposed.

The WCP (2.16) and (2.17) is a control problem for a diffusion process in dimension 1, in which both the drift and the diffusion coefficient are controlled by a control process that takes values in the space of allocation matrices. The values of these coefficients, evaluated at the two modes, are denoted b_m and, respectively, σ_m, m = 1, 2. The WCP formally describes the control problem associated with the PSS at the diffusion limit, and its control process represents the dynamic selection of the mode at which the PSS operates. The significance of the WCP has two aspects. First, as was shown in Atar et al. (2024), its solution gives a lower bound on the PSS cost asymptotics under any sequence of control policies (Theorem 2.4). Accordingly, any policy that achieves this bound is AO. Second, it suggests how AO policies should be structured. In particular: (a) State space collapse should hold, which, in our setting, involves two properties that should hold up to a level negligible at diffusion scale: (i) Both servers should be busy whenever there is any work in the system, and (ii) all queue length should be kept in the class i that minimizes $h_i{\alpha }_i$. Roughly speaking, (ii) implies that the class that maximizes $h_i{\alpha }_i$ should be prioritized. This type of sequencing policy is known as a $c\mu$ rule. (But, as shown by Harrison 1998 and Bell and Williams 2001, something more than a simple priority policy may be needed here in order to accomplish (i).) (b) When, for either $(m,m\prime )=(1,2)$ or $(m,m\prime )=(2,1)$, one has $b_m\le b_{m\prime }$ and ${\sigma }_m\le {\sigma }_{m\prime }$, only mode m should be used. Otherwise both modes should be used, by dynamically selecting them at different parts of the state space. The partition of the state space is defined via a switching point $z^{*}$: When the diffusion-scaled workload is below $z^{*}$, the mode m with $b_m\ge b_{m\prime }$ should be used; otherwise, $m\prime$. Determining this switching point is done by solving an HJB equation, (2.18) and (2.19).

The construction of an AO policy must take into account several considerations: whether to operate in one or two modes and, in the latter case, their ordering in workload space; which class has high priority; and the structure of the graph of basic activities for each of the modes. Different types of policies apply in different cases (Definitions 2.9, 2.10, 2.11, and 2.12). The main result states that these policies are AO and that the normalized workload converges weakly to the diffusion process given by the WCP state process under an optimal control (Theorem 2.13).

2.1. Queueing Model, Scaling, and Queueing Control Problem

The model under consideration is as in Atar et al. (2024), specialized to the case of two job classes, two servers, and four activities. We will refer to it as the 2 × 2 PSS when there is need to distinguish it from the general PSS treated in Atar et al. (2024). The symbol $i\in \{1,2\}$ is used as a generic index to a class and $k\in \{1,2\}$ to a server. For a general PSS, an activity is a class-server pair (i, k), where server k is capable of serving class i. In this paper, it is assumed that each server is capable of serving each class; hence, there are four activities. They are labeled by (i, k) or sometimes by $j=(i,k)$.

The model consists of a sequence of systems, indexed by $n\in \mathbb{N}$, that are all defined on one probability space $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$. For the nth system, one considers the following processes. The processes denoted $A^n=(A_i^n)$ and $S^n=(S_{ik}^n)$ represent arrival and potential service counting processes. That is, $A_i^n(t)$ is the number of arrivals of class i jobs until time t, i = 1, 2, and $S_{ik}^n(t)$ is the number of service completions of class i jobs by server k, by the time server k has devoted t units of time to class i, i = 1, 2, k = 1, 2. Next, $X^n=(X_i^n),\hspace{0.17em}{I}^n=(I_k^n),\hspace{0.17em}{D}^n=(D_{ik}^n)$, and $T^n=(T_{ik}^n)$ denote queue length, cumulative idleness, departure, and cumulative busyness processes. In other words, $X_i^n(t)$ is the number of class i customers in the system at time t, $I_k^n(t)$ is the cumulative time server k has been idle by time t, $D_{ik}^n(t)$ is the number of class i departures from server k, and $T_{ik}^n(t)$ is the cumulative time devoted by server k to class i. The process $T_{ik}^n$ takes the form $T_{ik}(t)={\int }_0^t{\text{Ξ}}_{ik}^n(s)ds$, where ${\text{Ξ}}_{ik}^n(t)$ is the fraction of effort devoted by server k to class-i jobs at t. In particular, ${\sum }_i{\text{Ξ}}_{ik}^n(t)\le 1$ for every k. Thus, ${\text{Ξ}}^n$ is referred to as the allocation process.

The aforementioned arrival and potential service processes are constructed as follows. Arrival rates ${\lambda }_i^n$ and service rates ${\mu }_{ik}^n$ are given, satisfying, for some constants ${\lambda }_i\in (0,\infty ),\hspace{0.17em}{\mu }_{ik}\in (0,\infty ),\hspace{0.17em}{\widehat{\lambda }}_i\in \mathbb{R}$, ${\widehat{\mu }}_{ik}\in \mathbb{R}$,

as $n\to \infty$. For each i, a renewal process ${\check{A}}_i$ is given, with interarrival distribution that has mean one and squared coefficient of variation $0<C_{A_i}^2<\infty$. Similarly, for each (i, k), a renewal process ${\check{S}}_{ik}$ is given with mean one interarrival and squared coefficient of variation $0<C_{S_{ik}}^2<\infty$. It is assumed that Aⁿ and Sⁿ are given by

It is assumed, moreover, that the six processes ${\check{A}}_i,\hspace{0.17em}{\check{S}}_{ik}$ are mutually independent and have strictly positive interarrival distributions and right-continuous sample paths. The independent and identically distributed interarrivals of ${\check{A}}_i$ and ${\check{S}}_{ik}$ are denoted by ${\check{a}}_i(l)$ and ${\check{u}}_{ik}(l),\hspace{0.17em}l\in \mathbb{N}$, respectively, and those of the accelerated processes $A_i^n$ and $S_{ik}^n$ are given by

The system is assumed to start empty; that is, $X^n(0)=0$ for all n. Simple relations between the processes are

The tuple $(\check{A},\check{S})$ is referred to as the stochastic primitives. In our formulation, we will consider Tⁿ as the control process (equivalently, the allocation process ${\text{Ξ}}^n$ may be regarded the control). In view of Equations (2.2), (2.3), and (2.4), given the stochastic primitives, the control uniquely determines the processes Dⁿ, Xⁿ, Iⁿ. Let an additional process be defined on the probability space denoted by $\Upsilon =(\Upsilon (l),l\in \mathbb{N})$, taking values in a Polish space ${\mathcal{S}}_{\text{rand}}$ and assumed to be independent of the stochastic primitives, for each n (there is no need to let $\Upsilon$ vary with n, as the primitives are all defined on the same probability space). It is included in the model in order to allow the construction of randomized controls; for more details about its potential use, see Atar et al. (2024, remark 2.1.ii).

The process Tⁿ is said to be an admissible control for the queueing control problem (QCP) for the n-th system if for each (i, k), $T_{ik}^n$ has sample paths in $C_{\mathbb{R}}^{0,+}[0,\infty )$ that are 1-Lipschitz, and the associated processes Dⁿ, Xⁿ, and Iⁿ given by (2.2), (2.3), and (2.4) satisfy (2.5); furthermore, Tⁿ is adapted to the filtration $\{{\mathcal{F}}_t^n\}$ defined by ${\mathcal{F}}_t^n=\sigma \{(A^n(s),D^n(s),s\in [0,t]),\Upsilon \}$. Denote by ${\mathcal{A}}^n$ the collection of all admissible controls for the QCP for the n-th system. As argued in Atar et al. (2024, remark 2.1.i), this definition allows for the control to depend on the history of all processes involved in the model (in addition to the auxiliary randomness $\Upsilon$).

The queue-length process normalized at the diffusion scale is defined by ${\widehat{X}}_i^n(t)=n^{-1/2}{X}_i^n(t)$. The cost of interest for the n-th system is given by

where $\gamma >0$ and $h(x)=h_1{x}_1+h_2{x}_2$, with constants $h_1,h_2>0$, and ${\widehat{X}}^n$ is the rescaled queue length process associated with the admissible control Tⁿ. The value for the n-th system is defined by

This completes the description of the queueing models and QCP. The complete set of problem data consists of the stochastic primitives mentioned above and the collection of parameters

We sometimes refer to $({\lambda }_i),({\mu }_{ik})$ as the first-order data and to $({\widehat{\lambda }}_i),({\widehat{\mu }}_{ik}),(C_{A_i}),(C_{S_{ik}})$ as the second-order data.

2.2. The Linear Program and Extended Heavy Traffic Condition

Given the first-order data ${\lambda }_i>0$, ${\mu }_{ik}>0,\hspace{0.17em}i,k=1,2$, consider the following linear program for the unknowns $({\xi }_{ik})\in {\mathbb{R}}_{+}^{2\times 2}$ and $\rho \in \mathbb{R}$.

Linear Program.

Minimize ρ subject to

$$\{\begin{array}{ll}{\displaystyle \sum _{k=1}^2{\xi }_{ik}}{\mu }_{ik}={\lambda }_i\hfill & i=1,2,\hfill \\ \hfill & \hfill \\ {\displaystyle \sum _{i=1}^2{\xi }_{ik}}⩽\rho \hfill & k=1,2,\hfill \\ \hfill & \hfill \\ {\xi }_{ik}⩾0\hfill & i,k=1,2.\hfill \end{array}$$(2.7)

Denote the optimal objective value of (2.7) by ${\rho }^{*}$.

Extended Heavy Traffic Condition.

${\rho }^{*}=1$

The extended heavy traffic condition is broader than the heavy traffic condition that has been extensively used in the literature, which requires, in addition to ${\rho }^{*}=1$, that there be a unique corresponding ξ.

Under the EHTC, any solution is of the form $(\xi ,1)$. Let ${\mathcal{S}}_{\text{LP}}$ denote the subset of ${\mathbb{R}}^{2\times 2}$, for which the set of all solutions is given by ${\mathcal{S}}_{\text{LP}}\times \{1\}$. We say that the EHTC with multiplicity (EHTCM) holds if the EHTC holds and the LP has multiple solutions (that is, there exist two distinct pairs $({\xi }^{(1)},1)$ and $({\xi }^{(2)},1)$ satisfying (2.7)). Following Atar et al. (2024), we say that the service rates μ_ik are decomposable if ${\mu }_{ik}={\alpha }_i{\beta }_k$ for all i, k, for some constants α_i and β_k.

A matrix $\xi \in {\mathbb{R}}_{+}^{2\times 2}$ is called column-stochastic if ${\sum }_i{\xi }_{ik}=1$ for both k = 1, 2. A column-stochastic matrix is called a mode if (at least) one of its columns is either ${(0,1)}^T$ or ${(1,0)}^T$. A mode is said to be degenerate if it has more than one zero entry; otherwise, it is said to be nondegenerate. A pair of nondegenerate modes is said to be a class-switched (server-switched) pair of modes if the zero entries in the two modes are in distinct rows but the same column (respectively, distinct columns but the same row). For example, the graphs in Figure 1, (a) and (b) correspond to a class-switched pair of modes, whereas those in Figure 1, (a) and (c) correspond to a server-switched pair.

The following condition will be referred to as the nondegeneracy condition, namely,

$${\lambda }_i\ne {\mu }_{ik} \text{for} \text{all} (i,k)\in {\{1,2\}}^2.$$(2.8)

The following is proved in Section 3.

Lemma 2.1.

Let the EHTC hold.

1. For any solution $(\xi ,1)$, ξ is column-stochastic.

2. The LP (2.7) has multiple solutions if and only if $({\mu }_{ik})$ are decomposable.

3. If the LP has multiple solutions, then there exists a pair of modes $({\xi }^{*,1},{\xi }^{*,2})$ such that

   $${\mathcal{S}}_{\text{LP}}=\text{ch}(\{{\xi }^{*,1},{\xi }^{*,2}\}).$$(2.9)

4. If the LP has multiple solutions and the nondegeneracy condition (2.8) holds, then both ${\xi }^{*,1}$ and ${\xi }^{*,2}$ of (2.9) are nondegenerate. Moreover, they form either a class-switched or a server-switched pair.

The main result will be proved under the following.

Assumption 2.2.

1. The EHTCM holds.

2. The nondegeneracy condition (2.8) holds.

Note that the case where the EHTC holds, but EHTCM does not hold, is already covered in the work Bell and Williams (2001), although, as mentioned in the introduction, under different assumptions on preemption and moment conditions. (See Corollary 2.15 and Remark 2.16 for implications of our results to the case where uniqueness holds and more on the relation to Bell and Williams 2001 in that case.)

In view of Lemma 2.1(2), under Assumption 2.2, the rates $({\mu }_{ik})$ are decomposable. Thus, ${\mu }_{ik}={\alpha }_i{\beta }_k$, and clearly, there is a degree of freedom in choosing $({\alpha }_i)$ and $({\beta }_k)$. In this paper, we will always assume that they are chosen so that ${\sum }_k{\beta }_k=1$, and it is easy to see that, given $({\mu }_{ik})$, this normalization uniquely determines these parameters.

It is also guaranteed by the lemma that, under Assumption 2.2, the extreme points of ${\mathcal{S}}_{\text{LP}}$ are two nondegenerate modes ${\xi }^{*,1},{\xi }^{*,2}$ forming a class- or a server-switched pair. Once a labeling of these modes has been fixed, we will sometimes slightly abuse the terminology by referring to them as modes 1 and 2, rather than modes ${\xi }^{*,1}$ and ${\xi }^{*,2}$.

In earlier work on PSS, under the assumption that the LP has a unique solution $({\xi }^{*},1)$, activities are categorized as basic or nonbasic according to the positivity of the fraction allocated to them by ${\xi }^{*}$; that is, an activity (i, k) is basic if ${\xi }_{ik}^{*}>0$ and nonbasic if ${\xi }_{ik}^{*}=0$. We extend this terminology to the case of multiple solutions as follows. For $m\in \{1,2\}$, an activity (i, k) is said to be basic in mode m if the allocation associated to it by this mode does not vanish, namely, ${\xi }_{ik}^{*,m}>0$. If ${\xi }_{ik}^{*,m}=0$ (respectively, ${\xi }_{ik}^{*,m}=1$) it is said to be nonbasic (respectively, full) in mode m.

Figure 1 demonstrates the second part of Lemma 2.1(4)—namely, that a pair of modes can be class-switched, as in Figure 1, (a) and (b), or server-switched, as in Figure 1, (a) and (c), but the LP does not give rise to a pair such as Figure 1, (b) and (c). The terms class-switched and server-switched will sometimes be abbreviated as “CS” and “SS.”

A mode is said to be in canonical form if its first column is ${(1,0)}^T$. It is clear by the definition of a mode that it is always possible to relabel the classes and the servers so that a given mode is in canonical form and that if the mode is nondegenerate, there is only one such relabeling. The graph of a mode in canonical form is shown in Figure 1(a). Because of its resemblance to the symbol N, this form is sometimes called an N-system.

If the EHTCM holds, but (2.8) does not—that is, there exist i, k such that ${\lambda }_i={\mu }_{ik}$—the situation is different: at least one of the modes will be degenerate—that is, have two nonbasic activities (see Lemma 3.1). In the terminology of linear programming, this corresponds to a case where one of the basic solutions of the LP (2.7) is degenerate (cf. Goldfarb and Todd 1989, definition 3.1). The degenerate case is not covered in this paper. The key difficulty in the degenerate case is that, in at least one of the modes, the servers do not communicate in the graph of basic activities, so the pooling required to reach the cost lower bound is not possible. (See Atar et al. 2024, section 2.4 for a more detailed discussion of this issue.)

Under Assumption 2.2, both modes have a single nonbasic activity. Then, given a mode, the graph of basic activities has exactly three edges, and one can speak of the single-activity class (the one associated with only one nonbasic activity), the dual-activity class, and, similarly, the single- and dual-activity server. These terms allow us to refer to the roles of classes and servers in the graph without considering a particular labeling. It is also useful to accompany these terms with matching notation. For a mode ξ, let the single- (respectively, dual-) activity class be denoted by $i_1(\xi )$ (respectively, $i_2(\xi )$), and, similarly, let the single- (respectively, dual-) activity server be denoted by $k_1(\xi )$ (respectively, $k_2(\xi )$).

The following example, which corresponds to examples (A) and (B) in Atar et al. (2024), should help to make the above ideas more concrete.

Example 2.3.

Let $({\mu }_{ik})$ be given by

$${\mu }_{11}=3,\hspace{1em}\hspace{1em}{\mu }_{12}=4,\hspace{1em}\hspace{1em}{\mu }_{21}=6,\hspace{1em}\hspace{1em}{\mu }_{22}=8.$$

Then, μ_ik are decomposable as ${\alpha }_i{\beta }_k$, where ${\alpha }_1=7,{\alpha }_2=14,{\beta }_1=3/7,$ and ${\beta }_2=4/7$. For $({\lambda }_i)$, consider two cases—namely,

$$(A)\hspace{1em}{\lambda }_1=5,\hspace{0.17em}{\lambda }_2=4,\hspace{1em}\hspace{1em}(B)\hspace{1em}{\lambda }_1=3.5,\hspace{0.17em}{\lambda }_2=7.$$

The linear program takes the form: Minimize ρ subject to

$$\{\begin{array}{ll}\hfill & 3{\xi }_{11}+4{\xi }_{12}={\lambda }_1,\hfill \\ \hfill & 6{\xi }_{21}+8{\xi }_{22}={\lambda }_2,\hfill \\ \hfill & {\xi }_{11}+{\xi }_{21}\le \rho ,\hfill \\ \hfill & {\xi }_{12}+{\xi }_{22}\le \rho ,\hfill \\ \hfill & \min {\xi }_{ik}\ge 0.\hfill \end{array}$$(2.10)

The solutions to the LP were calculated in Atar et al. (2024), and it was found that, in both cases, ${\rho }^{*}=1$, and the two modes are given by

$${\xi }^{*,1}={(1,\frac{1}{2},0,\frac{1}{2})}^T,\hspace{1em}\hspace{1em}{\xi }^{*,2}={(\frac{1}{3},1,\frac{2}{3},0)}^T,$$

in case (A) and

$${\xi }^{*,1}={(1,\frac{1}{8},0,\frac{7}{8})}^T,\hspace{1em}\hspace{1em}{\xi }^{*,2}={(0,\frac{7}{8},1,\frac{1}{8})}^T,$$

in case (B). In particular, the system is critically loaded, and there are multiple ways to allocate the effort so as to meet the demand. That is, the EHTCM holds. Figures 2 and 3 depict the graphs of basic activities corresponding to these modes. The examples differ in the way the two modes are paired. In case (A) (respectively (resp.), (B)), the nonbasic activity switches a server (a class). This distinction is of crucial significance to the way AO policies are designed in this paper.

2.3. Workload Control Problem

The WCP was derived and studied in Atar et al. (2024) under the EHTC. We describe this problem in the special case needed here—namely, under the setting of a 2 × 2 PSS and assuming that the EHTCM holds. In particular, as mentioned above, the parameters $({\alpha }_i),\hspace{0.17em}({\beta }_k)$ are uniquely determined by the problem data. Define the workload process and its scaled version as

(It follows from Atar et al. 2024, lemma 2.4(2) that (2.11) agrees with the definition of Wⁿ and ${\widehat{W}}^n$ given in Atar et al. 2024). Let the process that appears in the definition of the Cost (2.6) be denoted by

Throughout, denote by $p,q\in \{1,2\}$ the two distinct indices for which

where in the special case $h_1{\alpha }_1=h_2{\alpha }_2$, set p = 1 and q = 2. The policies constructed in this paper aim at keeping ${\widehat{X}}_p^n$ close to zero. Hence, we call p the high-priority class (HPC) and q the low-priority class (LPC). Next, let ${\sigma }_{A,i}={\lambda }_i^{1/2}{C}_{A_i},\hspace{0.17em}{\sigma }_{S,ik}={\mu }_{ik}^{1/2}{C}_{S_{ik}}$, and

Let also

It was shown in Atar et al. (2024) that the asymptotics of the pair $({\widehat{W}}^n,{\text{Ξ}}^n)$ are governed by a state-control pair of processes $(Z,\text{Ξ})$, where Z is a one-dimensional controlled diffusion given by

$\text{Ξ}$ is a control process, B is a standard BM (SBM), L is a reflection term at zero, and $z⩾0$. A precise definition is as follows.

A tuple $\mathfrak{S}=(\mathrm{\Omega }\prime ,\mathcal{F}\prime ,({\mathcal{F}}_t^{\prime }),\mathbb{P}\prime ,B,\text{Ξ},Z,L)$ is said to be an admissible control system for the WCP with initial condition z if $(\mathrm{\Omega }\prime ,\mathcal{F}\prime ,({\mathcal{F}}_t^{\prime }),\mathbb{P}\prime )$ is a filtered probability space; B, $\text{Ξ}$, Z, and L are processes defined on it; B is a SBM and an $({\mathcal{F}}_t^{\prime })$-martingale; $\text{Ξ}$ is $({\mathcal{F}}_t^{\prime })$-progressively measurable taking values in ${\mathbb{R}}^{2\times 2}$ and satisfying ${\mathbb{P}}^{\prime }(\text{for} \text{a}.\text{e}. t,{\text{Ξ}}_t\in S_{\text{LP}})=1$; Z is continuous nonnegative and $({\mathcal{F}}_t^{\prime })$-adapted; L has sample paths in $C_{\mathbb{R}}^{0,+}[0,\infty )$ and is $({\mathcal{F}}_t^{\prime })$-adapted; and Equation (2.16) and the identity ${\int }_{[0,\infty )}{Z}_{t}d{L}_t=0$ are satisfied $\mathbb{P}\prime$-a.s.

Denoting by ${\mathcal{A}}_{\text{WCP}}(z)$ the collection of all control systems for the WCP with initial condition z, the cost and value are defined as

The significance of the WCP lies in the fact that it provides a lower bound on the large n asymptotics of the n-th system value. More precisely, the main result of Atar et al. (2024), when specialized to the 2 × 2 PSS, states the following.

Theorem 2.4

(Atar et al. 2024). Let Assumption 2.2 (multiplicity and nondegeneracy) hold. Then,

$$\underset{n}{\lim \inf } {\widehat{V}}^n⩾V_0≔h_q{\alpha }_q{V}_{\text{WCP}}(0).$$

To prove this result, one only needs to verify that the assumptions from Atar et al. (2024) hold under Assumption 2.2. This is done in Section 3.

Remark 2.5.

The general result from Atar et al. (2024) does not assume multiplicity and, moreover, uses different notation based on the formulation of a dual to the LP. In the 2 × 2 setting with multiplicity, the lower bound from Atar et al. (2024) reduces to the above expression given in terms of the parameters $({\alpha }_i)$ in place of the dual.

In view of Theorem 2.4, a sequence $T^n\in {\mathcal{A}}^n$ of admissible controls for the QCP, also referred to as a sequence of policies, is said to be asymptotically optimal if

$$\underset{n\to \infty }{\lim \sup } {\widehat{J}}^n(T^n)⩽V_0.$$

2.3.1. A Heuristic Discussion of the WCP and Sheng’s Tortoise–Hare Problem.

The WCP is important not only because it provides a lower bound on performance, but also because one can learn from it how to construct a policy for the queueing model that performs near optimality. This problem has been solved completely. Before presenting its solution, we discuss its nature informally. Assume first that the pairs $(b_1,{\sigma }_1)$ and $(b_2,{\sigma }_2)$ are such that $b_1<b_2$, while ${\sigma }_1={\sigma }_2$. Then, it is intuitively clear and can be shown by a simple coupling that $J_{\text{WCP}}$ is minimized by always using mode 1, because it has a smaller drift. Next, consider the case where b₁ = b₂, but ${\sigma }_1<{\sigma }_2$. Mode 2 has greater variance, and, thus, one expects that the constraining mechanism, causing the diffusion to bounce back from the boundary, will be more active under mode 2 than under mode 1. Hence, again, using mode 1 at all times is optimal. More generally, mode 1 is optimal when $b_1\le b_2$ and ${\sigma }_1\le {\sigma }_2$.

A more interesting case is when $b_1<b_2$ but ${\sigma }_1>{\sigma }_2$, referred to in Sheng (1978) as the tortoise–hare problem. It seems reasonable to use the mode with smaller drift when the diffusion process is far from the origin and switch to the mode with smaller variance when it is close to the origin, where the aforementioned boundary effect is more prominent.

These heuristic arguments were validated rigorously in Sheng (1978). In particular, in the case $b_1<b_2,\hspace{0.17em}{\sigma }_1>{\sigma }_2$, it was shown that there exists a point $z^{*}\in (0,\infty )$ such that it is optimal to select mode 2 (resp., 1) when Z_t is in $[0,z^{*})$ (resp., $[z^{*},\infty )$). The identification of $z^{*}$ and the proof of the result were based on an HJB equation. The precise details are as follows.

2.3.2. The HJB Equation.

The value function can be characterized in terms of an HJB equation (see Fleming and Soner 2006 for an introduction to the subject). To present this equation, for $(v_1,v_2,\xi )\in {\mathbb{R}}^2\times {\mathcal{S}}_{\text{LP}}$, let

where the identity on the right-hand side (RHS) follows from the fact that both b and ${\sigma }^2$ are affine as a function of ξ, and ${\mathcal{S}}_{\text{LP}}$ is the convex hull of $\{{\xi }^{*,1},{\xi }^{*,2}\}$. A classical solution to the HJB equation is a $C^2({\mathbb{R}}_{+}:\mathbb{R})$ function u satisfyingand the boundary conditions at 0 and $\infty$,

Given a C² function u, denote ${\mathbb{H}}_m^u(z)=\overline{\mathbb{H}}(u\prime (z),u″(z),{\xi }^{*,m})$, m = 1, 2, and ${\mathbb{H}}^u(z)={\min }_m{\mathbb{H}}_m^u(z)$.

The following two conditions play an important role in what follows. They correspond to the two cases discussed above and will be referred to as the single-mode case and, respectively, the dual-mode case (not to be confused with uniqueness and multiplicity of the LP solution):

The C² smoothness of the value function is tied to the question of existence of a classical solution to the HJB equation. Owing to the uniform ellipticity ($\sigma {(\xi )}^2>0$ at both $\xi ={\xi }^{*,1}$ and ${\xi }^{*,2}$), one can show that a classical solution uniquely exists (Atar et al. 2024, proposition 2.5), a type of result that, in the general context of optimal switching of a diffusion process, has been called the principle of smooth fit. The results of Sheng (1978) alluded to above shed more light on the specific problem at hand, providing structural properties (parts 2 and 3 of the result below) that are harder to obtain via the general approach.

Proposition 2.6.

1. There exists a unique classical solution u to (2.18) and (2.19). Moreover, $u=V_{\text{WCP}}$.

2. If (2.20) holds, then, with m as in (2.20),

   $${\mathbb{H}}^u(z)={\mathbb{H}}_m^u(z)\hspace{1em}z\in {\mathbb{R}}_{+}.$$(2.22)

3. Alternatively, if (2.21) holds, then there exists $z^{*}\in (0,\infty )$ such that, with the pair $(m,m\prime )$ of (2.21),

   $${\mathbb{H}}^u(z)=\{\begin{array}{ll}{\mathbb{H}}_{m\prime }^u(z)\hfill & z<z^{*},\hfill \\ {\mathbb{H}}_m^u(z)\hfill & z>z^{*}.\hfill \end{array}$$(2.23)

The proof of this result appears in Section 4. Some details on the construction from Sheng (1978) (as corrected in Sheng (1981), by which parts 2 and 3 above were proved, appear in Appendix B.

Further terminology is as follows. In the single-mode case, the mode ${\xi }^{*,m}$ for which m satisfies (2.20) will be referred to as the active mode and denoted ξ^A because the above result indicates that it is optimal to always select ${\text{Ξ}}_t={\xi }^{*,m}$. In the dual-mode case, the modes ${\xi }^{*,m\prime }$ and ${\xi }^{*,m}$ for which $m\prime$ and m satisfy (2.21) will be referred to as ξ^L, the lower- and, respectively, ξ^H the higher-workload mode, and $z^{*}$ as the switching point. These terms refer to the fact that the result suggests that it is optimal to select ${\text{Ξ}}_t={\xi }^L$ (respectively, ${\text{Ξ}}_t={\xi }^H$) when $Z_t<z^{*}$ (respectively, $Z_t>z^{*}$).

Example 2.7.

We go back to Example 2.3, focusing on case (A), adding now information on the second-order data. Assume that the squared coefficients of variation $C_{A_i}^2$ and $C_{S_{ik}}^2$ are all one except $C_{S_{11}}^2=4$. Set both ${\widehat{\lambda }}_i$ to zero. As for ${\widehat{\mu }}_{ik}$, consider two cases. In case (A1), all ${\widehat{\mu }}_{ik}$ are set to zero. In case (A2), they are all zero except ${\widehat{\mu }}_{11}=1$. For each of the modes, computing the drift and squared diffusion coefficients via (2.14) and (2.15) gives, in case (A1),

$$b_1=0,\hspace{1em}{\sigma }_1^2=\frac{3}{7},\hspace{1em}{b}_2=0,\hspace{1em}{\sigma }_2^2=\frac{15}{49}.$$(2.24)

In case (A2),

$$b_1=-\frac{1}{7},\hspace{1em}{\sigma }_1^2=\frac{3}{7},\hspace{1em}{b}_2=-\frac{1}{21},\hspace{1em}{\sigma }_2^2=\frac{15}{49}.$$(2.25)

Note that case (A1) is a single-mode case, whereas case (A2) is a dual-mode case. Roughly speaking, we may infer that, in the former case, in order to perform near optimality, it is necessary to keep the proportions of the work allocated to the different activities close to the fractions given by ξ^A. That is, the policies should be designed to achieve ${\text{Ξ}}^n\Rightarrow {\xi }^A$. As for case (A2), recall that Z approximates ${\widehat{W}}^n$. Hence, in this case, it is necessary for the work allocation to vary over time in such a way that the aforementioned proportions are close to ξ^L when ${\widehat{W}}^n(t)<z^{*}$ and to ξ^H when ${\widehat{W}}^n(t)>z^{*}$. This is, again, only a rough statement; a precise formulation of this behavior appears next.

2.3.3. The Controlled Diffusion.

Controlling (2.16) according to the above description results in two different diffusion processes. In the single-mode case, the optimally controlled process Z is given by

with $b^A=b({\xi }^A)$ and ${\sigma }^A=\sigma ({\xi }^A)$, which is nothing but a reflecting BM with drift b^A and diffusivity σ^A. In the dual-mode case, consider the stochastic differential equation (SDE)where, throughout, we denote

For this equation, weak existence and uniqueness of solutions hold, as we shall argue in Lemma 4.1. As a result, there exists a control system for the WCP that behaves exactly as described above, with ${\text{Ξ}}_t={\xi }^L$ (respectively, ${\text{Ξ}}^H$) when $Z_t^{(2)}\le z^{*}$ ($>z^{*}$), and, moreover, this description uniquely determines the law of the process $Z^{(2)}$.

As for the asymptotics of the QCP, the preceding discussion and the fact that the system starts empty suggest that in order to achieve the lower bound, the convergence

should hold in the single-mode case, andin the dual-mode case, where $Z^{(1)}$ is given by (2.26), $(Z^{(2)},\text{Ξ},L,B)$ is a weak solution to (2.27), and z = 0.

2.4. Asymptotic Optimality Results

This section is devoted to the description of several policies that are shown to be AO under different conditions. We have already assumed that the interarrival times of the primitive processes possess finite second moments. Our main results require a stronger assumption.

Assumption 2.8.

There exists $\mathbf{m}>2$ such that

$$\underset{i,k}{\max } \mathbb{E}[{\check{a}}_i{(1)}^{\mathbf{m}}]\vee \mathbb{E}[{\check{u}}_{ik}{(1)}^{\mathbf{m}}]<\infty .$$

Whereas the assumption $\mathbf{m}>2$ is required for all our results, some of them will require yet a stronger moment assumption—namely, $\mathbf{m}>{\mathbf{m}}_0$—where, throughout, we denote

Different policies are proposed in different cases. The distinction between the various cases is based on whether the Single-Mode Condition (2.20) or the Dual-Mode Condition (2.21) holds and, further, for each of the relevant modes (ξ^A in the former case and both ξ^L and ξ^H in the latter), whether the HPC (class p) is the single- or dual-activity class. Our policies under the single-mode and dual-mode conditions are presented in Definitions 2.11 and 2.12, respectively. These use the P, ${\mathbf{T}}_1$ and ${\mathbf{T}}_2$ rules defined in Definition 2.10. The P rule is the simple priority rule that always give priority to the HPC, whereas the ${\mathbf{T}}_2$ rule involves a threshold, similar to the policy in Bell and Williams (2001), which prioritizes the HPC, except when the number of HPC customers is below a certain threshold. The ${\mathbf{T}}_1$ rule also involves a threshold (again, prioritizing the HPC, except when the number of HPC customers is below a certain threshold) and is only used in some cases of dual-mode policies for reasons described in the paragraph following Definition 2.11. Policies under the single-mode condition involve one rule, whereas policies under the dual-mode condition involve one or two rules.

All policies we describe are nonpreemptive; that is, the processing of a job is not interrupted once started. A job is said to be in the queue if it is waiting to be served, whereas it is in the system if it is either in the queue or being processed. (In what is a bit of an abuse of terminology, we use the term queue length to refer to the number in the system.) A server is said to be available at a time t if either it has just completed a job or has already been idle at that time.

Some of the policies to be described are defined in terms of a sequence of thresholds, ${\text{Θ}}^n$, put on the queue length at one of the two buffers. Under Assumption 2.8, $\mathbf{m}>2$. Fix $\overline{a}$ satisfying

Set the sequence of threshold levels ${\text{Θ}}^n$ and their normalized version ${\widehat{\text{Θ}}}^n$ to

Definition 2.9

(Server Dedicated to/Prioritizes a Class).

1. A server is said to be dedicated to class i at a given time if it acts as follows: if available at that time, it admits a job from class i, provided there is one in the queue, or there is a new class-i arrival, but does not admit a job from the other class.

2. A server is said to prioritize class i at a given time if it acts as follows: if available at that time, it admits a job from class i, provided there is one in the queue; otherwise, it admits a job from the other class, provided there is one in the queue. If the server is idle at that time and there is a new arrival of any class, it admits this arrival unless the other server is dedicated to that class and is free at that time (in which case the other server admits it).

Definition 2.10

(P, ${\mathbf{T}}_1$, and ${\mathbf{T}}_2$ rules). Let a mode ξ be given. At any moment in time the single-activity server is dedicated to the dual-activity class.

1. The servers are said to obey the priority rule, abbreviated the P rule, at a given time if the dual-activity server prioritizes the single-activity class at that time.

2. The servers are said to obey the single-activity class threshold rule, abbreviated the ${\mathbf{T}}_1$ rule, at a given time if in the n-th system, the dual-activity server prioritizes the single-activity class when the queue length of the single-activity class equals or exceeds ${\text{Θ}}^n$ at that time, and otherwise prioritizes the dual-activity class.

3. The servers are said to obey the dual-activity class threshold rule, abbreviated the ${\mathbf{T}}_2$ rule, at a given time if in the n-th system, the dual-activity server prioritizes the dual-activity class when the queue length of the dual-activity class equals or exceeds ${\text{Θ}}^n$ at that time, and otherwise prioritizes the single-activity class.

Recall the notations ξ^A, ξ^L, ξ^H, and p from Section 2.3. In the case of a single mode, the following two policies are proposed. (In Definitions 2.11 and 2.12, the text in square brackets is not a part of the definition, but serves to indicate when each policy is to be applied.)

Definition 2.11

(Single-Mode Policies P and ${\mathbf{T}}_2$). Let the Single-Mode Condition (2.20) hold.

1. The P policy [to be applied when $i_1({\xi }^A)=p$] is as follows: the servers obey the P rule corresponding to ξ^A at all times.

2. The ${\mathbf{T}}_2$ policy [to be applied when $i_2({\xi }^A)=p$] is as follows: the servers obey the ${\mathbf{T}}_2$ rule corresponding to ξ^A at all times.

In the dual-mode case, servers switch between two rules, depending, roughly speaking, on whether the rescaled workload is below or above the switching point $z^{*}$. This makes the structure of the policies more complicated. In particular, there is potential loss of capacity in every switching, especially because our policies are nonpreemptive. Moreover, the number of switchings grows without bound, as the rescaled workload converges to a diffusion. Therefore, one has to be careful about how to assure that the rule obeyed is updated soon enough after the workload level has crossed the switching point so as not to compromise optimality. The considerations differ in the different cases and give rise to the use of the ${\mathbf{T}}_1$ rule, as well as the sampling rules in Definition 2.12. Although it is possible that AO is not too sensitive to these fine details, proving that might be quite hard.

The precise definition requires the use of a state variable called current mode, which determines which rule is applicable. This variable is not updated continuously in time about whether $W^n>n^{1/2}{z}^{*}$, but only at certain sampling times, as detailed below. The four policies used in the dual-mode case are as follows.

Definition 2.12

(Dual-Mode Policies PP, ${\mathbf{T}}_2{\mathbf{T}}_2$, ${\mathbf{T}}_1{\mathbf{T}}_2$, and ${\mathbf{T}}_2{\mathbf{T}}_1$). Let the Dual-Mode Condition (2.21) hold.

1. The PP policy [applied when $i_1({\xi }^L)=i_1({\xi }^H)=p$] is as follows.

   1. The workload is sampled at each service completion of the single-activity server. If the workload is below $n^{1/2}{z}^{*}$, the current mode is set to $\xi ={\xi }^L$; otherwise, it is set to $\xi ={\xi }^H$.

   2. The servers always obey the P rule with respect to (w.r.t.) the current mode ξ.

2. The ${\mathbf{T}}_2{\mathbf{T}}_2$ policy [applied when $i_2({\xi }^L)=i_2({\xi }^H)=p$] is as follows.

   1. The workload is sampled at each service completion of the single-activity server. If the workload is below $n^{1/2}{z}^{*}$, the current mode is set to $\xi ={\xi }^L$; otherwise, it is set to $\xi ={\xi }^H$.

   2. The servers always obey the ${\mathbf{T}}_2$ rule w.r.t. the current mode ξ.

3. The ${\mathbf{T}}_1{\mathbf{T}}_2$ policy [applied when $i_1({\xi }^L)=i_2({\xi }^H)=p$] is as follows.

   1. The workload is sampled at each arrival and service completion. If the workload is below $n^{1/2}{z}^{*}$, the current mode is set to $\xi ={\xi }^L$; otherwise, it is set to $\xi ={\xi }^H$.

   2. Whenever $\xi ={\xi }^L$, the servers obey the ${\mathbf{T}}_1$ rule w.r.t. ξ; whenever $\xi ={\xi }^H$, they obey the ${\mathbf{T}}_2$ rule w.r.t. ξ.

4. The ${\mathbf{T}}_2{\mathbf{T}}_1$ policy [applied when $i_2({\xi }^L)=i_1({\xi }^H)=p$] is as ${\mathbf{T}}_1{\mathbf{T}}_2$, except that the roles of ${\mathbf{T}}_1$ and ${\mathbf{T}}_2$ are interchanged.

Our main result states conditions under which each of the six policies just introduced are AO.

Theorem 2.13.

Let Assumptions 2.2 and 2.8 hold. In parts 1(b), 2(b), and 2(c), assume moreover that $\mathbf{m}>{\mathbf{m}}_0$.

1. Assume that the Single-Mode Condition (2.20) holds.

   1. If $i_1({\xi }^A)=p$ , then under the P policy, (2.29) holds, and this policy is AO.

   2. If $i_2({\xi }^A)=p$ , then under the ${\mathbf{T}}_2$ policy, (2.29) holds, and this policy is AO.

2. Assume that the Dual-Mode Condition (2.21) holds.

   1. If $i_1({\xi }^L)=i_1({\xi }^H)=p$, then under the PP policy, (2.30) holds, and this policy is AO.

   2. If $i_2({\xi }^L)=i_2({\xi }^H)=p$, then under the ${\mathbf{T}}_2{\mathbf{T}}_2$ policy, (2.30) holds, and this policy is AO.

   3. If $i_1({\xi }^L)=i_2({\xi }^H)=p$, then under the ${\mathbf{T}}_1{\mathbf{T}}_2$ policy, (2.30) holds, and this policy is AO.

   4. If $i_2({\xi }^L)=i_1({\xi }^H)=p$, then under the ${\mathbf{T}}_2{\mathbf{T}}_1$ policy, (2.30) holds, and this policy is AO.

The proof of this result is in Section 5. Table 1 summarizes how to determine which of the above six case applies, based on the problem data. We discuss some of the fine details of our construction in the dual-mode case in Section 5.1.3.

Table 1. Identifying an AO Policy Assuming LP Solution Multiplicity

Remark 2.14.

In Section 5.1, Theorem 5.1 provides more detailed information than (2.29) and (2.30) on the weak limit of the processes involved.

Although the main goal of this paper is to address the case where the LP has multiple solutions, the following result about the case where it has a unique solution is a consequence of our treatment.

Corollary 2.15.

Let the “standard” HTC hold; that is, the EHTC with a unique LP solution $({\xi }^{*},1)$. Let also Assumption 2.8 hold. In part (b), assume moreover that $\mathbf{m}>{\mathbf{m}}_0$.

1. If $i_1({\xi }^{*})=p$, then under the P policy, (2.29) holds, and this policy is AO.

2. If $i_2({\xi }^{*})=p$, then under the ${\mathbf{T}}_2$ policy, (2.29) holds, and this policy is AO.

Remark 2.16.

This result is closely related to the main result of Bell and Williams (2001), which proved AO of a threshold policy under the standard HTC. In a remark in Bell and Williams (2001, p. 622), it was conjectured that the threshold policy without preemption has the same behavior in the heavy traffic limit as the one with preemption. Corollary 2.15 confirms that AO can indeed be achieved by a nonpreemptive threshold policy, although, strictly speaking, it does not prove the precise conjecture from Bell and Williams (2001), as our threshold sizes differ from those of Bell and Williams (2001).

Example 2.17.

We continue cases (A1) and (A2) from Example 2.7, specifying now which part of the main result applies in each case. Recall from Example 2.3 that ${\alpha }_1=7$ and ${\alpha }_2=14$. Recall from Example 2.7 that Figure 2 depicts the two modes and the corresponding graphs and that the drift-diffusion pairs are given by (2.24) and (2.25). Case (A1) is a single mode because b₁ = b₂, and the active mode is ${\xi }^A={\xi }^{*,2}$ because ${\sigma }_2<{\sigma }_1$. As can be seen in Figure 2 (right), this mode has $i_1({\xi }^A)=2$. Now, assume that the costs are $(h_1,h_2)=(1,1)$. Then, the class that maximizes $h_i{\alpha }_i$ is p = 2. Thus, $i_1({\xi }^A)=p$, and Theorem 2.13(1(a)) holds. If, instead, $(h_1,h_2)=(3,1)$, then p = 1, and, therefore, Theorem 2.13(1(b)) holds.

In case (A2), we have $b_1<b_2$ but ${\sigma }_2<{\sigma }_1$; hence, this is a dual-mode case with ${\xi }^L={\xi }^{*,2}$ and ${\xi }^H={\xi }^{*,1}$. By Figure 2, $i_1({\xi }^L)=2$ and $i_1({\xi }^H)=2$. Again, if $(h_1,h_2)=(1,1)$, then p = 2, and we see that Theorem 2.13(2(a)) applies, but if $(h_1,h_2)=(3,1)$, p = 1, and Theorem 2.13(2(b)) applies.

2.5. Some Numerical Results

The dual-mode policies that we introduce are admittedly complicated, and the proof of their asymptotic optimality is quite involved. A natural question thus arises here: Is all of this complexity worthwhile? What is the gain from it?

From a purely theoretical/mathematical context, the answer is simple: If the dual-mode policy has a cost that is strictly below that of both single-mode controls, then a nonswitching policy cannot be asymptotically optimal. From a practical viewpoint, this answer falls short. Implementing the dual-mode policy is clearly more complicated than implementing a single-mode policy. A key question thus arises: Is the gain from using a dual-mode policy sufficient to overcome the effort involved in implementing it? The answer to this question is context-dependent and clearly depends on the cost of the effort required to implement the dual-mode control, which we do not include as part of our model. Thus, we do not quite answer this question.

We do, however, partially answer the question of how much larger is the cost of single-mode policies over the optimal switching policy. We do this in two numerical examples. All of the numerical results that we present here are obtained by finding the unique root of Equation (B.3) and then using (B.1) and (B.2). Note that to use (B.3), (B.1), and (B.2), the identity of the two modes needs to be flipped around because in case (A2), we have $b_1<b_2$, and the analysis in Appendix B requires $b_1⩾b_2$. The mode identities in our presentation remains as in (A2).

The first numerical results are for the case (A2) introduced in Example 2.7, with $\gamma =0.01$. In particular, in Figure 4, we plot three curves: $V_1(z),V_2(z)$, and $V_{\mathit{\text{WCP}}}(z)$. Here, V_i is the cost function for using mode $i,1=1,2$. (The orange/top curve corresponds to V₁, and the green/middle curve corresponds to V₂.) It is clear from Figure 4 that there is a gap between $V_{\mathit{\text{WCP}}}(z)$ and both $V_1(z)$ and $V_2(z)$. We define the “gain” from using the optimal switching policy as

Thus, $G\ge 1$. For case (A2), G = 1.07. If the cost related to implementing the more complicated switching policy is great enough, it may indeed be decided that G = 1.07 is not sufficient to overcome this cost.

This raises a more general question: Can we place an a priori upper bound on G? It is beyond the scope of this paper to answer this question in any precise mathematical manner, but we provide a set of numerical results suggesting that the answer may be no: Given any $M<\infty$, it is possible to find a set of parameters $\{(b_i,{\sigma }_i^2),i=1,2)\}$ such that G > M. We examine a set of parameters loosely related to case (A2). In particular, we fix $b_2=-1/21$ and ${\sigma }_2^2=15/49$, which are the parameters in case (A2), throughout. We also use $\gamma =0.01$. We then take six different values for b₁ and set ${\sigma }_1^2$ so that

In particular, we take the b₁ values to be $\{-3/21,-6/21,-12/21,-24/21,-48/21,-96/21\}$. Table 2 contains the results of this numerical experiment. Note that G = 1.26 when $b_1=-3/21$ and grows to G = 5.01 when $b_1=-96/21$.

Table 2. Gain from Using Switching Policy

In a very real sense, the situation presented in Figure 4 is a “lucky” one for a system controller who does not want to go through the trouble of implementing the switching policy because the loss is only 7%. The results of Table 2 stand in contrast to that. To see this in graphical form, in Figure 5, we present the same plot as in Figure 4, but corresponding to the parameters in the third row of Table 2. (In this case, V₁ and V₂ have switched places: The green/top curve corresponds to V₂, and the orange/middle curve corresponds to V₁.)

3. The LP Under the EHTC

In this section, we prove Lemma 2.1. In addition, in a sequence of three lemmas, we provide an explicit solution to the LP and a criterion for determining whether the two modes are class-switched or server-switched. Finally, Theorem 2.4 is proved. The section is structured as follows. In Section 3.1, we first prove Lemma 2.1(1–3), based mostly on results from Atar et al. (2024). Then, we state Lemmas 3.1 and 3.2, which provide the LP solution, and Lemma 3.3, which is concerned with how the modes are paired. Lemma 2.1(4) is then proved based on Lemma 3.3. In Section 3.2, we prove Lemmas 3.1–3.3 and Theorem 2.4.

3.1. LP-Related Lemmas

Proof of Parts 1–3 of Lemma 2.1.

1. Let $\xi \in {\mathcal{S}}_{\text{LP}}$. It is impossible that ${\sum }_i{\xi }_{ik}<1$ for both k = 1 and 2, as this contradicts the EHTC ${\rho }^{*}=1$. Assume, then, that, say, ${\sum }_i{\xi }_{i1}<1$. Then, ${\xi }_{11}<1$. Define

   $$\tilde{\xi }=\xi +\left(\begin{array}{cc}\epsilon & -c\epsilon \\ 0& 0\end{array}\right),$$
   where $c={\mu }_{12}^{-1}{\mu }_{11}$. Then, for $\epsilon >0$ small, $\tilde{\xi }$ satisfies (2.7) with $\rho <1$, which again contradicts the EHTC. This proves Part 1.

2. This follows from Atar et al. (2024, lemma 2.4(4)). Note that uniqueness of the dual problem, which is a standing assumption in Atar et al. (2024), is not used in the proof of this statement.

3. This statement follows from Atar et al. (2024, lemma 2.3(1)) and Atar et al. (2024, lemma 2.4(4)), where, again, the uniqueness of the dual is not used. □

The following lemma computes the two modes.

Lemma 3.1.

Let the EHTCM hold. Then,

$${\displaystyle \sum _i\frac{{\lambda }_i}{{\alpha }_i}}={\displaystyle \sum _k{\beta }_k}=1,$$(3.1)

where the last equality merely expresses the normalization convention mentioned earlier in Section 2.2. Moreover, any $\xi \in {\mathcal{S}}_{\text{LP}}$ is determined by its entry ξ₁₁ via

$$\xi =\left(\begin{array}{cc}{\xi }_{11}& \frac{{\lambda }_1}{{\alpha }_1{\beta }_2}-\frac{{\beta }_1}{{\beta }_2}{\xi }_{11}\\ 1-{\xi }_{11}& 1-\frac{{\lambda }_1}{{\alpha }_1{\beta }_2}+\frac{{\beta }_1}{{\beta }_2}{\xi }_{11}\end{array}\right).$$(3.2)

The two modes ${\xi }^{*,1}$ and ${\xi }^{*,2}$ can be expressed by (3.2) with ξ₁₁ given by

$${\xi }_{11}^{*,1}=\max (0,\frac{{\lambda }_1}{{\alpha }_1{\beta }_1}-\frac{{\beta }_2}{{\beta }_1}),\hspace{1em}\hspace{1em}{\xi }_{11}^{*,2}=\min (\frac{{\lambda }_1}{{\alpha }_1{\beta }_1},1).$$(3.3)

Recall that under the nondegeneracy condition, for any mode, there is a unique relabeling of classes and servers, which transforms it to a canonical form. The following result shows that both modes, once put in canonical form, are given by the same formula.

Lemma 3.2.

Let Assumption 2.2 (EHTCM and nondegeneracy) hold. Fix $m\in \{1,2\}$. Relabel classes and servers so that ${\xi }^{*,m}$ is in canonical form. Then, ${\lambda }_1>{\alpha }_1{\beta }_1$ and

$${\xi }^{*,m}=\left(\begin{array}{l}1\hspace{1em}\frac{{\lambda }_1}{{\alpha }_1{\beta }_2}-\frac{{\beta }_1}{{\beta }_2}\hfill \\ 0\hspace{1em}\frac{{\lambda }_2}{{\alpha }_2{\beta }_2}\hfill \end{array}\right).$$(3.4)

In particular, if $\xi ,\xi \prime \in {\mathcal{S}}_{\text{LP}}$ and there are i, k such that ${\xi }_{ik}={\xi }_{ik}^{\prime }=0$, then $\xi =\xi \prime$.

Lemma 2.1(4), which is yet to be proved, states that under the nondegeneracy condition, the two modes must be either class- or server-switched. The following lemma contains this result and, in addition, provides a criterion for distinguishing between these cases. We will say that the class-switching condition holds if

and the server-switching condition holds if

Lemma 3.3.

Let Assumption 2.2 hold. Then, both modes are nondegenerate. Moreover, under the Class-Switching Condition (3.5), the modes are class-switched (as, for example, in Figure 1, (a) and (b)), and under the Server-Switching Condition (3.6), they are server-switched (as, for example, in Figure 1, (a) and (c)).

Proof of Part 4 of Lemma 2.1.

The statement is contained in Lemma 3.3. □

Remark 3.4.

Note that cases 2(c) and 2(d) of Theorem 2.13 correspond to class-switched modes (for example, under case 2(c), one has $i_1({\xi }^L)=i_2({\xi }^H)=p$; hence, the nonbasic activity must have switched from class p to class q when moving from ξ^L to ξ^H). By Lemma 3.3, this occurs under (3.5). Also note that in both cases, the proposed policies apply a different rule for the lower and upper workload modes. On the other hand, cases 2(a) and 2(b) of Theorem 2.13 correspond to server-switching and hold under (3.6), and our policies are such that the same rule is used for the lower and upper workload modes.

3.2. Proof of Lemmas 3.1–3.3 and Theorem 2.4

Proof of Lemma 3.1.

In view of Lemma 2.1(1), every solution ξ is column-stochastic, and, recalling ${\mu }_{ik}={\alpha }_i{\beta }_k$, must satisfy

$$\begin{array}{l}{\xi }_{11}{\beta }_1+{\xi }_{12}{\beta }_2=\frac{{\lambda }_1}{{\alpha }_1},\\ {\xi }_{21}{\beta }_1+{\xi }_{22}{\beta }_2=\frac{{\lambda }_2}{{\alpha }_2},\\ {\xi }_{11}+{\xi }_{21}=1,\\ {\xi }_{12}+{\xi }_{22}=1,\\ {\xi }_{i,k}⩾0,\hspace{0.17em}\hspace{0.17em}i,k\in \{1,2\}.\end{array}$$(3.7)

Identity (3.1) follows.

Next, because the Expression (3.2) is also column-stochastic, proving that any solution ξ is determined by ξ₁₁ as in (3.2) amounts to proving that ξ₁₂ is given as in (3.2). This follows from the first line in (3.7).

It remains to prove (3.3). By the expression just obtained for ξ₁₂, it follows that as long as

$${\xi }_{11}⩾\frac{{\lambda }_1}{{\alpha }_1{\beta }_1}-\frac{{\beta }_2}{{\beta }_1},$$

we obtain ${\xi }_{12}⩽1$. Clearly, in addition, ${\xi }_{11}⩾0$ must hold. Similarly, as long as

$${\xi }_{11}⩽\frac{{\lambda }_1}{{\alpha }_1{\beta }_1},$$

we obtain ${\xi }_{12}⩾0$, and, in addition, ${\xi }_{11}⩽1$ must hold. As a result, it is necessary that

$${\xi }_{11}\in \left[\max \right(0,\frac{{\lambda }_1}{{\alpha }_1{\beta }_1}-\frac{{\beta }_2}{{\beta }_1}),\min (\frac{{\lambda }_1}{{\alpha }_1{\beta }_1},1\left)\right].$$(3.8)

Moreover, setting ξ₁₁ to each of the two endpoints of the interval indicated in (3.8) and letting ξ be the corresponding expression from (3.2) gives rise to a solution satisfying all of (3.7), as can be checked directly. Because by (3.2) a solution ξ is an affine function of its entry ξ₁₁, these two endpoints correspond to the two extreme points of ${\mathcal{S}}_{\text{LP}}$; that is, to the two modes ${\xi }^{*,1},\hspace{0.17em}{\xi }^{*,2}$. This proves the lemma. □

Proof of Lemma 3.2.

Note that Relations (3.7) are invariant to relabeling of classes and servers. Hence, so is Relation (3.2), which was derived solely from (3.7). Let m be given and assume a relabeling has been performed to put ${\xi }^{*,m}$ in canonical form. Then, ${\xi }^{*,m}$ satisfies (3.2) with its first column given by ${(1,0)}^T$. Consequently ${\xi }_{11}^{*,m}=1$. Substituting ${\xi }_{11}^{*,m}=1$ into (3.2) proves (3.4). Because under the nondegeneracy assumption, there can be only one zero entry, in (3.4), we have ${\xi }_{12}^{*,m}>0$. Hence, ${\lambda }_1>{\alpha }_1{\beta }_1$. The final assertion follows from (3.4) using, again, the fact that there can be at most one zero entry □

The four possible graphs and their relabelings are described in Figure 6. Namely, if $(i\prime ,k)$ is the nonbasic activity in ${\xi }^{*,m}$, then defining

${\tilde{\xi }}^{*,m}$ is obtained from ${\xi }^{*,m}$ upon relabeling in the form of an “N.”

Proof of Lemma 3.3.

The nondegeneracy of both modes follows from Lemma 3.2.

Next, let the Class-Switching Condition (3.5) hold. Because of (3.1),

$$\underset{k}{\max }{\beta }_k>\underset{i}{\max }\frac{{\lambda }_i}{{\alpha }_i}⩾\underset{i}{\min }\frac{{\lambda }_i}{{\alpha }_i}>\underset{k}{\min }{\beta }_k.$$(3.9)

Recall from the proof of Lemma 3.1 that the two endpoints of the interval defined in (3.8) correspond to the two modes. Consider the right endpoint. If the minimum in expression in (3.8) is one, then, by (3.2), the nonbasic activity in that mode is (2, 1), and, moreover, $\frac{{\lambda }_1}{{\alpha }_1}>{\beta }_1$. By (3.1), this gives $\frac{{\lambda }_2}{{\alpha }_2}<{\beta }_2.$ In view of (3.9), this gives

$${\beta }_2>\underset{i}{\max }\frac{{\lambda }_i}{{\alpha }_i}.$$

Hence, the maximum in (3.8) is zero. By (3.2), this shows that the nonbasic activity in the other mode is (1, 1). If, on the other hand, the minimum in (3.8) is $\frac{{\lambda }_1}{{\alpha }_1{\beta }_1}$, then $\frac{{\lambda }_1}{{\alpha }_1}<{\beta }_1$, and the nonbasic activity in the corresponding mode is (1, 2). Similarly, by (3.9),

$$\underset{i}{\min }\frac{{\lambda }_i}{{\alpha }_i}>{\beta }_2.$$

This means the maximum in (3.8) is not zero. The nonbasic activity in the other mode is then (2, 2). In both cases, the two modes form a class-switched pair as claimed.

Consider now the Server-Switching Condition (3.6). Because of (3.1),

$$\underset{i}{\max }\frac{{\lambda }_i}{{\alpha }_i}>\underset{k}{\max }{\beta }_k⩾\underset{k}{\min }{\beta }_k>\underset{i}{\min }\frac{{\lambda }_i}{{\alpha }_i}.$$(3.10)

If the minimum in (3.8) is one, then $\frac{{\lambda }_1}{{\alpha }_1}>{\beta }_1$ and the nonbasic activity in one mode is (2, 1). By (3.10), $\frac{{\lambda }_1}{{\alpha }_1}>{\beta }_2$. Hence, the maximum in (3.8) is not zero, and the nonbasic activity in the other mode is (2, 2). Finally, if the minimum in (3.8) is not one, then $\frac{{\lambda }_1}{{\alpha }_1}<{\beta }_1$, and the nonbasic activity in one mode is (1, 2). By (3.10), $\frac{{\lambda }_1}{{\alpha }_1}<{\beta }_2$. Hence, the maximum in (3.8) is zero and the nonbasic activity in the other mode is (1, 1). In both cases, the two of modes forms a server-switched pair. □

Proof of Theorem 2.4.

This lower bound is precisely the one stated in Atar et al. (2024, theorem 2.6), when specialized to the 2 × 2 PSS. To prove that it is valid, we must verify that the standing assumption of Atar et al. (2024), namely, Atar et al. (2024, assumption 2.2), holds.

First, Atar et al. (2024, assumption 2.2.1), which states that the EHTC holds, is valid because of our Assumption 2.2.1. Next, Atar et al. (2024, assumption 2.2.2), when translated to the notation of this paper, states that every $\xi \in {\mathcal{S}}_{\text{LP}}$ is column-stochastic. This holds by our Lemma 2.1.1. It remains to show that Atar et al. (2024, assumption 2.2.3), which states that the dual of (2.7) has a unique solution, is satisfied.

To this end, we shall adopt in the remainder of this proof some notation and terminology from Atar et al. (2024). By Lemma 3.2, the nonbasic activity is different in both modes ${\xi }^{*,1},\hspace{0.17em}{\xi }^{*,2}$, for else one would have ${\xi }^{*,1}={\xi }^{*,2}$, contradicting the EHTCM. As a result, with the terminology introduced in Atar et al. (2024, section 2), all the activities are potentially basic. Using strict complementary slackness ((36) in Schrijver 1986, chapter 7) in the same way as in Atar et al. (2024, lemma 2.3.4), any (y, z) solution of the dual satisfies

$$y_i={\mu }_j{z}_k,\hspace{1em}\hspace{1em}i,k\in \{1,2\},\hspace{0.17em}j=(i,k).$$

It follows that $y_1{y}_2={\mu }_{11}{\mu }_{21}{z}_1^2={\mu }_{12}{\mu }_{22}{z}_2^2$. By positivity of both z_k, this gives z₁ = cz₂ for some constant c > 0. Moreover, one of the constraints of the dual problem Atar et al. (2024, equation (2.8)) is $z_1+z_2=1$. Therefore, $(z_k)$ are uniquely determined. As a consequence, so are $(y_i)$, which shows that the dual problem has at most one solution. The existence of a dual solution follows from the EHTC, as shown in Atar et al. (2024, lemma 2.4.2). This completes the verification of Atar et al. (2024, assumption 2.2). □

4. The WCP and HJB Equation

In this section, Proposition 2.6 is proved. Lemma 4.1, which is used to prove it, contains two additional results: An identification of optimal control systems for the WCP, and weak uniqueness of solutions to the SDE (2.27), both needed for the weak convergence proofs in Section 5.

Proof of Part 1 of Proposition 2.6.

This is a special case of Atar et al. (2024, proposition 2.5). We comment that the fact that $V_{\text{WCP}}$ is a classical solution to (2.18) and (2.19) has been established already in Sheng (1978). However, uniqueness of solutions is not covered there. □

In what follows, u always denotes the unique solution to (2.18) and (2.19).

In the following lemma, parts 1 and 2 are largely based on results from Sheng (1978). For completeness, we have included details on the construction from Sheng (1978) (as corrected in Sheng 1981) in Appendix B.

Lemma 4.1.

1. (Optimality in the single-mode case). Assume (2.20) and recall that in this case ${\xi }^A={\xi }^{*,m}$ for m as in (2.20). Then, with u as above, Equation (2.22) of Proposition 2.6 holds. Moreover, $J_{\text{WCP}}(z,{\mathfrak{S}}^{(1)})=V_{\text{WCP}}(z)$ for the admissible control system ${\mathfrak{S}}^{(1)}=(\mathrm{\Omega },\mathcal{F},\{{\mathcal{F}}_t\},\mathbb{P},B,\text{Ξ},Z^{(1)},L^{(1)})$, where $(Z^{(1)},L^{(1)},B)$ is the RBM from (2.26) (assumed to be constructed on the original probability space), ${\mathcal{F}}_t=\sigma \{B_s:s\in [0,t]\}$ and ${\text{Ξ}}_t={\xi }^A$.

2. (Optimality in the dual-mode case). Assume (2.21) and recall that in this case $({\xi }^L,{\xi }^H)=({\xi }^{*,m\prime },{\xi }^{*,m})$. Then, there exists a switching point $z^{*}\in (0,\infty )$ such that (2.23) of Proposition 2.6 holds. Moreover, SDE (2.27) possesses a weak solution $(\mathrm{\Omega }\prime ,\mathcal{F}\prime ,\{\mathcal{F}{\prime }_t\},\mathbb{P}\prime ,B,Z^{(2)},L^{(2)})$. Furthermore, one has $J_{\text{WCP}}(z,{\mathfrak{S}}^{(2)})=V_{\text{WCP}}(z)$ for the admissible control system defined by ${\mathfrak{S}}^{(2)}=(\mathrm{\Omega }\prime ,\mathcal{F}\prime ,\{{\mathcal{F}}_t^{\prime }\},\mathbb{P}\prime ,B,\text{Ξ},Z^{(2)},L^{(2)})$, where ${\text{Ξ}}_t={\phi }^{*}(Z_t^{(2)})$.

3. Weak uniqueness holds for solutions to SDE (2.27).

Proof of Parts 2 and 3 of Proposition 2.6.

These results are contained in parts 1 and 2 of Lemma 4.1. □

For Markov control problems, a map from the state space to the control action space is often called a stationary (feedback) control policy, or a policy for short. For our WCP, a policy is thus a measurable map $\overline{\xi }:{\mathbb{R}}_{+}\to {\mathcal{S}}_{\text{LP}}$. This term is used in Sheng (1978), and we adopt it in the next proof. Parts 1 and 2 take full advantage of several results from Sheng (1978), where a classical solution to Equations (2.18)–(2.19) is constructed, and a description of an optimal policy is provided.

Proof of Parts 1 and 2 of Lemma 4.1.

The Single-Mode Condition (2.20) corresponds to Sheng (1978, section 5.3, equations (41) and (42)). The Dual-Mode Condition (2.21) corresponds to the complementary case. It is stated in Sheng (1978, theorem 1, chapter 4) that a policy is optimal if and only if the cost associated to it is C² and satisfies Sheng (1978, equation (14), chapter 4), which is the HJB Equation (2.18)–(2.19) in our notation. However, the equation studied there is more general, and in order to reduce it to our (2.18)–(2.19), one must take the switching costs to vanish (by setting the expression K = 0) and the reflection-absorption parameter to correspond to reflection only (by setting λ = 1).

Under the single-mode condition, the policy constructed has the simple form

$$\overline{\xi }(z)={\xi }^{*,m},\hspace{1em}\hspace{1em}z\in {\mathbb{R}}_{+},$$

with the same m as in (2.20). It is shown that it is an optimal policy by computing the cost associated it and showing that it solves the HJB equation with its boundary conditions. The fact that (2.22) holds in this case is a direct consequence of the fact that the cost associated to the single-mode policy indeed solves the HJB equation. This completes the proof of part 1.

As for part 2, the claim that the SDE (2.27) possesses a weak solution is proved in Atar et al. (2024, lemma 4.1). Under the dual-mode case, the policy constructed in Sheng (1978) is

$${\overline{\xi }}_{z^{*}}(z)={\xi }^{*,m\prime }{\mathrm{𝟙}}_{z\le z^{*}}+{\xi }^{*,m}{\mathrm{𝟙}}_{z>z^{*}},\hspace{1em}\hspace{1em}z\in {\mathbb{R}}_{+},$$(4.1)

with the same m and $m\prime$ as in (2.21). By Sheng (1978, theorem 4, chapter 3), any policy of this form gives rise to a cost function that is C¹ in all of $(0,\infty )$ and C² in $(0,\infty )\backslash \{z^{*}\}$. The value of $z^{*}$ that leads to an optimal policy is found by the principle of smooth fit, namely by requiring that the second derivative is continuous also at $z^{*}$. The equation that states this smoothness condition, Sheng (1978, (61), chapter 5) (as corrected in Sheng 1981, (3.21)), turns out to have a unique solution $z^{*}\in (0,\infty )$. The solution to the HJB equation is then the cost associated to ${\overline{\xi }}_{z^{*}}$ with that value of $z^{*}$. The statement of part 2, by which the corresponding control system is optimal for the WCP, therefore follows from Sheng (1978, theorem 1, chapter 4). Once again, the very fact that this function solves the HJB equation implies that Equation (2.23) holds in this case. □

Proof of Part 3 of Lemma 4.1.

We slightly simplify the notation by writing (2.27)–(2.28) as

$$Z_t=z+{\displaystyle {\int }_0^t{b}^{*}}(Z_s)ds+{\displaystyle {\int }_0^t{\sigma }^{*}}(Z_s)d{B}_s+L_t,$$

where, with $a^{*}(x)={\sigma }^{*}{(x)}^2$, there exist constants $b_0,b_1\in \mathbb{R}$ and $a_0>0,\hspace{0.17em}{a}_1>0$, such that

$$b^{*}(x)=\{\begin{array}{ll}{b}_0,\hfill & x\le z^{*},\hfill \\ b_1,\hfill & x>z^{*},\hfill \end{array}\hspace{1em}\hspace{1em}{a}^{*}(x)=\{\begin{array}{ll}{a}_0,\hfill & x\le z^{*}\hfill \\ a_1,\hfill & x>z^{*}.\hfill \end{array}$$

In the remainder of this proof, $a^{*}$ and $b^{*}$ are written as a and b. Let $\mathcal{A}$ be the operator

$$\mathcal{A}f(x)≔b(x)f\prime (x)+\frac{1}{2}a(x)f^{″}(x),$$

on the domain $\mathcal{D}(\mathcal{A})≔\{f\in C_0^{\infty }[0,\infty ):f\prime (0)=0\}$, where $C_0^{\infty }[0,\infty )$ denotes the set of compactly supported members of $C^{\infty }[0,\infty )$. If $f\in \mathcal{D}(\mathcal{A})$ and (Z, L, B) is a weak solution to the SDE, then, by Ito’s formula, the boundary property of L and the boundary condition $f\prime (0)=0$, the process $f(Z_t)-{\int }_0^t\mathcal{A}f(Z_s)ds$ is a martingale. Therefore, it follows from the existence result in part 2 of the lemma that, for every probability distribution ν on $[0,\infty )$, there exists a solution of the $D_{[0,\infty )}[0,\infty )$ martingale problem for $(\mathcal{A},\nu )$. We will use the definition of the stopped martingale problem of Ethier and Kurtz (1986, chapter 4, section 6). Then, for every probability distribution ν on $[0,\infty )$, there exists a solution of the stopped martingale problem for $(\mathcal{A},\nu ,[0,\frac{2}{3}\hspace{0.17em}{z}^{*}\left)\right)$ and of the stopped martingale problem for $(\mathcal{A},\nu ,(\frac{1}{3}\hspace{0.17em}{z}^{*},\infty \left)\right)$.

Define the operators ${\mathcal{A}}_0$ and ${\mathcal{A}}_1$ in the following way:

$$\begin{array}{l}{\mathcal{A}}_{0}f(x)≔b_{0}f\prime (x)+\frac{1}{2}{a}_0{f}^{″}(x),\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\text{on} \text{the} \text{domain} \mathcal{D}({\mathcal{A}}_0):=\mathcal{D}(\mathcal{A})\\ {\mathcal{A}}_{1}f(x)≔b(x)f\prime (x)+\frac{1}{2}a(x)f^{″}(x),\hspace{1em}\hspace{1em}\text{on} \text{the} \text{domain} \mathcal{D}({\mathcal{A}}_1):{=C}_0^{\infty }(\mathbb{R}).\end{array}$$

The $D_{[0,\infty )}[0,\infty )$ martingale problem for ${\mathcal{A}}_0$ is well posed (for instance by corollary 8.1.2, theorem 4.4.1, and proposition 4.3.1 of Ethier and Kurtz 1986). Therefore, for every probability distribution ν on $[0,\infty )$, there exists a unique solution of the stopped martingale problem for $({\mathcal{A}}_0,\nu ,[0,\frac{2}{3}\hspace{0.17em}{z}^{*}\left)\right)$ by theorem 4.6.1 of Ethier and Kurtz (1986). Because, for every $f\in \mathcal{D}({\mathcal{A}}_0)=\mathcal{D}(\mathcal{A})$,

$${\mathcal{A}}_{0}f{|}_{[0,\frac{2}{3}{z}^{*}]}=\mathcal{A}f{|}_{[0,\frac{2}{3}{z}^{*}]},$$

every solution of the stopped martingale problem for $(\mathcal{A},\nu ,[0,\frac{2}{3}\hspace{0.17em}{z}^{*}\left)\right)$ is also a solution of the stopped martingale problem for $({\mathcal{A}}_0,\nu ,[0,\frac{2}{3}\hspace{0.17em}{z}^{*}\left)\right)$; therefore, the solution of the stopped martingale problem for $(\mathcal{A},\nu ,[0,\frac{2}{3}\hspace{0.17em}{z}^{*}\left)\right)$ is unique.

Next, the $D_{\mathbb{R}}[0,\infty )$ martingale problem for ${\mathcal{A}}_1$ is well posed by exercise 7.3.3 of Stroock and Varadhan (2006) (it is shown there that the $C_{\mathbb{R}}[0,\infty )$ martingale problem for ${\mathcal{A}}_1$ is well posed, but every solution of the $D_{\mathbb{R}}[0,\infty )$ martingale problem for ${\mathcal{A}}_1$ has paths in $C_{\mathbb{R}}[0,\infty )$ almost surely). Therefore, for every probability distribution ν on $[0,\infty )$, there exists a unique solution of the stopped martingale problem for $({\mathcal{A}}_1,\nu ,(\frac{1}{3}\hspace{0.17em}{z}^{*},\infty \left)\right)$ by theorem 4.6.1 of Ethier and Kurtz (1986). Because for every $f_1=\mathcal{D}({\mathcal{A}}_1)$ there exists $f\in \mathcal{D}(\mathcal{A})$ such that

$$f{|}_{[\frac{1}{3}{z}^{*},\infty )}=f_1{|}_{[\frac{1}{3}{z}^{*},\infty )},\hspace{1em}\hspace{1em}\mathcal{A}f{|}_{[\frac{1}{3}{z}^{*},\infty )}={\mathcal{A}}_1{f}_1{|}_{[\frac{1}{3}{z}^{*},\infty )},$$

every solution of the stopped martingale problem for $(\mathcal{A},\nu ,(\frac{1}{3}\hspace{0.17em}{z}^{*},\infty \left)\right)$ is also a solution of the stopped martingale problem for $({\mathcal{A}}_1,\nu ,(\frac{1}{3}\hspace{0.17em}{z}^{*},\infty \left)\right)$; therefore, the solution of the stopped martingale problem for $(\mathcal{A},\nu ,(\frac{1}{3}\hspace{0.17em}{z}^{*},\infty \left)\right)$ is unique.

Now, one can apply theorem 4.6.2 in Ethier and Kurtz (1986) with $U_1≔[0,\frac{2}{3}\hspace{0.17em}{z}^{*}),\hspace{0.17em}{U}_k≔(\frac{1}{3}\hspace{0.17em}{z}^{*},\infty )$ for $k\ge 2$, to conclude that, for every probability distribution ν on $[0,\infty )$, the solution of the $D_{[0,\infty )}[0,\infty )$ martingale problem for $(\mathcal{A},\nu )$ is unique.

Finally, because, as already mentioned, every solution to the SDE is a solution to the martingale problem, the weak uniqueness of solutions to the SDE follows. □

Remark 4.2

(Symmetry Conditions). As Lemma 4.1 states, (2.20) is a necessary and sufficient condition for the optimal control of the WCP to not switch between modes. It is natural to ask whether it can be determined if the single- or the dual-mode condition holds under various symmetry conditions. Specifically, consider

$$\frac{{\widehat{\mu }}_{1k}}{{\alpha }_1}=\frac{{\widehat{\mu }}_{2k}}{{\alpha }_2},\hspace{1em}\hspace{1em}k=1,2,$$(4.2)

$$\frac{{\widehat{\mu }}_{i1}}{{\beta }_1}=\frac{{\widehat{\mu }}_{i2}}{{\beta }_2},\hspace{1em}\hspace{1em}i=1,2,$$(4.3)

$$C_{S_{i1}}=C_{S_{i2}},\hspace{1em}\hspace{1em}i=1,2.$$(4.4)

As it turns out, each of the above three conditions is sufficient for (2.20). This is proved in Lemma C.1 in Appendix C. As a result, each of these conditions is sufficient for nonswitching. These conditions can arise naturally and occur in certain cases in the literature.

5. Asymptotic Optimality

In this section, we prove Theorem 2.13. Toward this, an important intermediate goal is to establish a weak convergence result, stated in Theorem 5.1. The proofs of both theorems rely on four main steps stated in Propositions 5.3–5.6.

5.1. Weak Convergence

5.1.1. Statement of Weak Convergence Result.

We will adopt the following convention regarding the six cases listed in Theorem 2.13. When a statement is said to hold in a certain case of Theorem 2.13, it is meant that the assumptions, as well as the policy, specified in this case are in force. For example, saying that a certain statement holds in case 1(a) of Theorem 2.13 means that it holds when the Single-Mode Condition (2.20) and the condition $i_1({\xi }^A)=p$ hold and the P policy is applied, and, moreover, the weaker moment assumption $\mathbf{m}>2$ is assumed (but $\mathbf{m}>{\mathbf{m}}_0$ in case 1(b), for example). When a claim is stated without specifying a case, it is meant that it holds in each one of the six.

In addition to the rescaled processes already defined, the weak convergence results will be concerned with additional rescaled processes, namely,

With this notation, the Balance Equation (2.3) for Xⁿ translates under scaling to

Thus, if we denote

we obtain the following representation for the workload:

The convergence of the rescaled primitives is a direct consequence of the central limit theorem for renewal processes (Billingsley 1999, section 17). Namely, the tuple $({\widehat{A}}_i^n,{\widehat{S}}_{ik}^n)$ converges to what we denote by $(A_i,S_{ik})$, comprising six mutually independent BMs with zero drift and diffusivity given by the constants ${\lambda }_i^{1/2}{C}_{A_i}$ and ${\mu }_{ik}^{1/2}{C}_{S_{ik}}$, which in Section 2.3, we have denoted by ${\sigma }_{A,i}$ and ${\sigma }_{S,ik}$, respectively.

Theorem 5.1.

Let the assumptions of Theorem 2.13 hold. Then, $(T^n,{\widehat{W}}^n,{\widehat{L}}^n,{\widehat{X}}^n)\Rightarrow (T,W,L,X)$, where the latter is defined as follows.

1. In cases 1, (a) and (b) of Theorem 2.13, (W, L) is the RBM and boundary term given by (2.26) and initial condition z = 0, and $T_t={\xi }^{A}t$ for all t.

2. In cases 2, (a)–(d) of Theorem 2.13, (W, L) is the (unique in law) weak solution to the SDE (2.27) with initial condition z = 0, and letting ${\text{Ξ}}_t={\phi }^{*}(W_t)$, one has $T_t={\int }_0^t{\text{Ξ}}_{s}ds$ for $t\ge 0$.

3. In all cases, X_p = 0 and $X_q={\alpha }_{q}W$.

The significance of this result is that it implies that, under each of the proposed policies, limits of the processes exist and form admissible control systems for the WCP, which are, in view of Lemmas 4.1.1–2, optimal.

We next present a lemma from Atar et al. (2024) concerning limits of $({\widehat{A}}^n,{\widehat{S}}^n,T^n,{\widehat{F}}^n)$ under general sequences of policies. The Skorohod map, $\mathrm{\Gamma }:D_{\mathbb{R}}[0,\infty )\to D_{{\mathbb{R}}_{+}}[0,\infty )\times D_{\mathbb{R}}^{+}[0,\infty )$, takes a function ψ to a pair $(\phi ,\eta )$, where

The corresponding maps $\psi \mapsto \phi$ and $\psi \mapsto \eta$ are denoted by ${\mathrm{\Gamma }}_1$ and ${\mathrm{\Gamma }}_2$, respectively.

Lemma 5.2.

Let $\{T^n\},\hspace{0.17em}{T}^n\in {\mathcal{A}}^n$ be any sequence of admissible controls for the QCP for which ${\lim \sup }_n {\widehat{J}}^n(T^n)<\infty$. Then, the following conclusions hold. The sequence $({\widehat{A}}^n,{\widehat{S}}^n,T^n)$ is C-tight. Along any convergent subsequence where $({\widehat{A}}^n,{\widehat{S}}^n,T^n)\Rightarrow (A,S,T)$, one has

$$({\widehat{A}}^n,{\widehat{S}}^n,T^n,{\widehat{F}}^n)\Rightarrow (A,S,T,F),$$

where F is defined in (5.8). There exist on $(\mathrm{\Omega },\mathcal{F})$ processes $(B,\text{Ξ},Z\prime ,L\prime )$ and a filtration $\{{\mathcal{H}}_t\}$ such that the tuple $\mathfrak{S}=(\mathrm{\Omega },\mathcal{F},\{{\mathcal{H}}_t\},\mathbb{P},B,\text{Ξ},Z\prime ,L\prime )$ forms an admissible control system for the WCP with initial condition 0. These processes satisfy the relations

$$\begin{array}{l}T={\displaystyle {\int }_0^{·}{\text{Ξ}}_s}ds,\hspace{1em}\hspace{1em}(Z\prime ,L\prime )=\mathrm{\Gamma }[F],\\ F_t={\displaystyle \sum _i\frac{A_i(t)+{\widehat{\lambda }}_{i}t}{{\alpha }_i}}-{\displaystyle \sum _{i,k}\frac{S_{ik}(T_{ik}(t))+{\widehat{\mu }}_{ik}{T}_{ik}(t)}{{\alpha }_i}}\\ ={\displaystyle {\int }_0^{t}b}({\text{Ξ}}_s)ds+{\displaystyle {\int }_0^t\sigma }({\text{Ξ}}_s)d{B}_s.\end{array}$$(5.8)

Proof.

This is the content of Atar et al. (2024, lemmas 5.1 and 5.5). □

This lemma is our starting point for proving Theorem 5.1. Whereas it relates limits of processes associated with the QCP to an admissible control system for the WCP, note that it does not make any claim regarding ${\widehat{X}}^n$ or ${\widehat{W}}^n$ and, hence, by itself is not sufficient to relate the prelimit cost (defined in terms of ${\widehat{X}}^n$) to the WCP cost. In particular, the pair $(Z\prime ,L\prime )$ need not be the weak limit of $({\widehat{W}}^n,{\widehat{L}}^n)$. To proceed, one must show that under the proposed policies, along the sequence specified in Lemma 5.2, one has

where $(W,L)=(Z\prime ,L\prime )$. Once this is achieved, the lemma guarantees that the weak limit (W, L) satisfieswith ${\int }_{[0,\infty )}{W}_{t}d{L}_t=0$, assuring that the limit tuple indeed forms an admissible system for the WCP. To go from here to the statements made in Theorem 5.1, one further needs to show that (W, L) are as given in (2.26) or (2.27) and that X_p = 0.

The propositions presented below address these issues as follows. Proposition 5.3 provides uniform integrability required to eventually deduce Theorem 2.13 from Theorem 5.1 and, in addition, ensures that the prelimit cost remains bounded so Lemma 5.2 may be applied. Proposition 5.4 shows that ${\widehat{X}}_p^n\to 0$ in probability. Proposition 5.5 states precisely what is needed to attain (5.9). Finally, Proposition 5.6 implies that (2.27) holds in the dual-mode case.

5.1.2. Main Steps Toward Weak Convergence.

Throughout what follows, the assumptions of Theorem 2.13 are in force. The four main steps required to achieve weak convergence and, later, Theorem 2.13, are as follows.

Proposition 5.3.

There exists ${\epsilon }_0>0$ such that

$$\underset{n}{\lim \sup } \mathbb{E}{\displaystyle {\int }_0^{\infty }{e}^{-\gamma t}}{({\widehat{H}}_t^n)}^{1+{\epsilon }_0}dt<\infty .$$

As already mentioned, this uniform integrability result will allow us to deduce convergence of the costs, as stated in Theorem 2.13, from the convergence stated in Theorem 5.1. Moreover, because it also implies boundedness of the cost under the proposed policies, it enables us to use Lemma 5.2. The proof is given in Section 5.2.2.

Proposition 5.4.

For every $t_0>0$, as $n\to \infty$,

$$\mathbb{P}\left(\Vert {\widehat{X}}_p^n{\Vert }_{t_0}⩾2{\widehat{\text{Θ}}}^n\right)\to 0.$$

The above type of result is often referred to as state-space collapse (SSC), as it asserts that, asymptotically, all workload is kept in one buffer, a property crucially used in establishing the one-dimensional state space description of the limiting dynamics, as well as asymptotic optimality, because all workload is held in the “less expensive” class. It is proved in Section 5.2.3.

Proposition 5.5.

Consider a subsequence as in Lemma 5.2, where $({\widehat{A}}^n,{\widehat{S}}^n,T^n)\Rightarrow (A,S,T)$. Then, along this sequence, one has $({\widehat{A}}^n,{\widehat{S}}^n,T^n,{\widehat{F}}^n,{\widehat{W}}^n,{\widehat{L}}^n)\Rightarrow (A,S,T,F,W,L)$, where F is given by (5.8), and $(W,L)=\mathrm{\Gamma }(F)$. In particular, $({\widehat{W}}^n,{\widehat{L}}^n)$ is a C-tight sequence, and the conclusions of Lemma 5.2 hold with $(W,L)=(Z\prime ,L\prime )$.

The proof appears in Sections 5.2.4 and 5.2.5.

Finally, the policies P and ${\mathbf{T}}_2$ that are proposed under the single-mode condition do not use the nonbasic activity of the active mode ξ^A. For the four policies employed under the dual-mode condition, we need the following control over the use of the nonbasic activities corresponding to ξ^L and ξ^H.

Proposition 5.6.

Consider the same subsequence as in Proposition 5.5 and cases 2(a)–(d) of Theorem 2.13. If $(i^l,k^l)$ (resp. $(i^h,k^h)$) denotes the nonbasic activity in ξ^L (resp. ξ^H), then for any $t_0>0$ and $\epsilon >0$,

$${\displaystyle {\int }_0^{t_0}}{\mathrm{𝟙}}_{{\widehat{W}}_t^n⩽z^{*}-\epsilon }d{T}_{i^l{k}^l}^n(t)\to 0,\hspace{1em}\hspace{1em}{\displaystyle {\int }_0^{t_0}}{\mathrm{𝟙}}_{{\widehat{W}}_t^n⩾z^{*}+\epsilon }d{T}_{i^h{k}^h}^n(t)\to 0,$$(5.10)

in probability, as $n\to \infty$.

To explain the role of this proposition, recall that if $\xi \in {\mathcal{S}}_{\text{LP}}$, then the condition ${\xi }_{ik}=0$ for some activity (i, k) not only implies that ξ is one is the modes ${\xi }^{*,1}$ or ${\xi }^{*,2}$, but also identifies which one by Lemma 3.2. Because any limit T of Tⁿ is given as ${\int }_0^{·}{\text{Ξ}}_{s}ds,\hspace{0.17em}{\text{Ξ}}_t\in {\mathcal{S}}_{\text{LP}}$, this proposition implies that when workload is either below or above the switching point, the resource allocation asymptotically follows the respective mode of operation ξ^L or ξ^H. This is very close to stating that the pair (W, L) follows the SDE (2.27) and, indeed, is the basis for proving this fact. The proof of this proposition appears in Section 5.2.6.

5.1.3. Considerations for the Construction of Dual-Mode Policies.

As noted above, two of the key results that we need to prove Theorem 2.13 are state-space collapse (Proposition 5.4) and a boundary property stating that there is asymptotically no idleness of either server when there is work in the system (Proposition 5.5). The proofs of these results differ by case/policy and, for dual-mode policies, rely on the rules used as well as the way that workload is sampled. Here, we provide a brief description of the reasons underlying the policy definitions that we have used.

• A difficulty arises in the proof of Proposition 5.4 in case 2(a), where the policy switches between two P rules. Only the dual-activity server in the current mode processes the HPC and the identity of the dual-activity server changes when switching modes. At each switching time, if the server processing the HPC in the new mode is busy with low-priority jobs and the service of the high-priority job at the other server ends, no server will process high-priority jobs for a time $O(n^{-1})$. In principle, this time could accumulate to let the number of high-priority jobs increase to a nonnegligible value. In order to prevent this, we designed switching between P rules to only occur at the time of service completion at the single-activity server. When switching, this server becomes dual activity and gives priority to the HPC (which is the single-activity class in P). In case 2(a), there is always at least one server processing the HPC, regardless of switching between modes.

• Similarly, in order to prove Proposition 5.5 in case 2(b), we need to show that the number of HPC is not zero when there are low-priority jobs in the system. To make sure that the high-priority class does not receive too much service, switching between two ${\mathbf{T}}_2$ rules only occurs at the time of service completion at the single-activity server. When switching, the single-activity server becomes dual activity and now gives priority to the low-priority jobs if the number of HPC jobs is low. In case 2(b), as long as the number of HPC jobs is below the threshold there is at most one server working on HPC jobs, regardless of switching between modes.

• In case 2(c), it should be noted that in the lower mode, the system looks similar to case 1(a), so one could consider using a P rule. Doing so, however, would cause difficulty in proving Proposition 5.5 for this case. Using a P rule keeps the number of HPC jobs O(1). At the moment of switching into the ${\mathbf{T}}_2$ rule, this can lead to the new single-activity server, which is dedicated to HPC, incurring idle time when there is work in the system. To avoid this situation, the ${\mathbf{T}}_1$ rule was used instead of P, guaranteeing that, at a switching time, there will not be too few HPC jobs in the system. A similar argument applies to case 2(d).

5.1.4. Proof of Weak Convergence.

Here, we prove Theorem 5.1 based on the four propositions.

Proof of Theorem 5.1.

First, by Proposition 5.3, one has that ${\lim \sup }_n {\widehat{J}}^n(T^n)<\infty$ for each one of the relevant policies Tⁿ. As a result, the assumptions of Lemma 5.2 and Proposition 5.5 are valid. To summarize the conclusions from these results, fix a subsequence along which $({\widehat{A}}^n,{\widehat{S}}^n,T^n)\Rightarrow (A,S,T)$. Then, there exists a tuple $(\{{\mathcal{H}}_t\},F,W,L,\text{Ξ},B)$ such that, along this sequence,

$$({\widehat{A}}^n,{\widehat{S}}^n,{\widehat{F}}^n,T^n,{\widehat{W}}^n,{\widehat{L}}^n)\Rightarrow (A,S,F,T,W,L),$$

where F is given in terms of A, S, T by (5.8) and W and L are given by $(W,L)=\mathrm{\Gamma }(F)$. Moreover, $\mathfrak{S}=(\mathrm{\Omega },\mathcal{F},\{{\mathcal{H}}_t\},\mathbb{P},B,\text{Ξ},W,L)$ forms an admissible control for initial condition 0, and $T={\int }_0^{·}{\text{Ξ}}_{s}ds$. In particular,

$$W=F+L={\displaystyle {\int }_0^{·}b}({\text{Ξ}}_s)ds+{\displaystyle {\int }_0^{·}\sigma }({\text{Ξ}}_s)d{B}_s+L_t.$$(5.11)

Next, by Proposition 5.4, ${\widehat{X}}_p^n\to 0$ in probability. Also, by (2.11), ${\widehat{X}}_q^n={\alpha }_q{\widehat{W}}^n-{\alpha }_p{\widehat{X}}_p^n$, and, therefore, we now have, along the subsequence, $({\widehat{A}}^n,{\widehat{S}}^n,{\widehat{F}}^n,T^n,{\widehat{W}}^n,{\widehat{L}}^n,{\widehat{X}}^n)\Rightarrow (A,S,F,T,W,L,X)$, where we denote

$$X_p=0,\hspace{1em}\hspace{1em}{X}_q={\alpha }_{q}W.$$(5.12)

Note that the control system $\mathfrak{S}$ thus constructed may depend on the subsequence. However, consider the following.

Claim.

In case 1, (a)–(b) of Theorem 2.13, (W, L) is the RBM, and its boundary term given by (2.26), and $T_t={\xi }^{A}t$ for all t. In cases 2(a)–(d) of Theorem 2.13, (W, L) is a weak solution to the SDE (2.27), and, moreover, ${\text{Ξ}}_t={\phi }^{*}(W_t)$ for a.e. t.

Suppose the above claim holds true. Then, the law of (W, L) is uniquely determined: in case 1 as an RBM; in case 2 as a weak solution to (2.27), for which weak uniqueness holds by Lemma 4.1.3. In particular, this law does not depend on the subsequence. Moreover, because by this claim and (5.12), the pair of processes (T, X) is uniquely determined by W (away from a $\mathbb{P}$-null set), it follows that the law of $(T,W,L,X)$ does not depend on the subsequence. This yields the convergence $(T^n,{\widehat{W}}^n,{\widehat{L}}^n,{\widehat{X}}^n)\Rightarrow (T,W,L,X)$ along the full sequence and completes the proof of the result. In what follows, the claim is proved.

Consider first the single-mode case, namely, cases 1(a)–(b) of Theorem 2.13. The policies employed are P and ${\mathbf{T}}_2$, and both do not use the nonbasic activity of the active mode ξ^A. In other words, if we denote this activity by $(i^a,k^a)$, then under these policies, $T_{i^a{k}^a}^n=0$ for all n. As a consequence, the limit process T must satisfy $T_{i^a{k}^a}(t)=0$ a.s.; hence, ${\text{Ξ}}_{i^a{k}^a}(t)=0$ for a.e. t, a.s. By the uniqueness statement made in Lemma 3.2, whenever $\tilde{\xi }\in {\mathcal{S}}_{\text{LP}}$ and ${\tilde{\xi }}_{i^a{k}^a}=0$, one must have $\tilde{\xi }={\xi }^A$. It follows that ${\text{Ξ}}_t={\xi }^A$ for a.e. t, and, hence $T_t={\xi }^{A}t$. As a consequence, (5.11) holds as $W_t=b({\xi }^A)t+\sigma ({\xi }^A)B_t+L_t$. That is, the pair (W, L) satisfies (2.26). This proves the first part of the claim.

Next, consider the dual mode, namely, cases 2(a)–(d) of Theorem 2.13. First, we will show based on Proposition 5.6 that, for every $\epsilon >0$ and $t_0>0$,

holds a.s. Let g be a continuous function such that

By the continuous mapping theorem, we have along the subsequence $(g({\widehat{W}}^n),T^n)\Rightarrow (g(W),T)$. In addition, Tⁿ is continuous with finite variation over compacts. By theorem 2.2 of Kurtz and Protter (1991),

By Proposition 5.6, ${\int }_0^{t_0}{\mathrm{𝟙}}_{\{{\widehat{W}}_t^n<z^{*}-\frac{\epsilon }{2}\}}d{T}_{i^l{k}^l}^n(t)\to 0$ in probability. Hence, the left-hand side (LHS) in (5.15) converges to zero in probability. Thus, the RHS in (5.15) equals zero a.s., and, therefore, by the first inequality in (5.14), the first part of (5.13) is proved. The second part of (5.13) is proved analogously.

Next, clearly, ${\text{Ξ}}_{i^l{k}^l}(t){\mathrm{𝟙}}_{\{{\text{Ξ}}_t={\xi }^L\}}=0$. Hence, by (5.13), ${{\int }_0^{t_0}\mathrm{𝟙}}_{\{W_t<z^{*}-\epsilon \}}{\mathrm{𝟙}}_{\{{\text{Ξ}}_t\ne {\xi }^L\}}{\text{Ξ}}_{i^l{k}^l}(t)dt=0$. Arguing, again, by the uniqueness statement in Lemma 3.2, one has ${\text{Ξ}}_{i^l{k}^l}(t)>0$ whenever ${\text{Ξ}}_t\ne {\xi }^L$. It follows that, a.s.,

where the second equality is proved analogously to the first one. Going back to (5.11), note that by (5.16), one has both ${\int }_0^{t_0}b({\text{Ξ}}_s){\mathrm{𝟙}}_{\{W_t<z^{*}-\epsilon \}}{\mathrm{𝟙}}_{\{{\text{Ξ}}_t\ne {\xi }^L\}}ds=0$ and ${\int }_0^{t_0}\sigma ({\text{Ξ}}_s){\mathrm{𝟙}}_{\{W_t<z^{*}-\epsilon \}}{\mathrm{𝟙}}_{\{{\text{Ξ}}_t\ne {\xi }^L\}}d{B}_s=0$. A similar statement hold for $\{W_t>z^{*}+\epsilon \}$ and ξ^H. Hence, by (5.11) and the Definition (2.28) of the functions $b^{*}$ and ${\sigma }^{*}$, it follows thatfor $t\le t_0$. Because t₀ is arbitrary, this is true for all t. Hence, denoting ${\delta }_t^{\epsilon }={\mathrm{𝟙}}_{|W_t-z^{*}|<\epsilon }$ and using the boundedness of $b(·)$,where

Notice that U_t does not depend on ε, so if we manage to prove that the RHS converges to zero in probability as $\epsilon \downarrow 0$, it follows that, for every t, U_t = 0 a.s. Hence, by continuity of this process, U_t = 0 for all t, a.s. That is, the processes (W, L, B) satisfy (2.27) a.s.

To this end, apply the occupation times formula (Revuz and Yor 1999, corollary VI.1.6), by which for any continuous semimartingale Y, one has, a.s.,

with $L^y(Y)$ the local time of Y at y. Consider the above with $Y_t=W_t-z^{*}$. Clearly, the RHS in the above display is zero. Moreover, ${〈Y,Y〉}_t={\int }_0^t\sigma {({\text{Ξ}}_s)}^{2}ds$, and because σ is bounded away from zero, we obtain that ${{\int }_0^t\mathrm{𝟙}}_{\{W_s=z^{*}\}}ds=0$ a.s. For fixed ω, one has for all t, ${\mathrm{𝟙}}_{\{|W_t-z^{*}|<\epsilon \}}\to {\mathrm{𝟙}}_{\{W_t=z^{*}\}}$ as $\epsilon \downarrow 0$. Hence, by dominated convergence, ${\gamma }_t^{\epsilon }\to 0$ a.s. as $\epsilon \downarrow 0$.

Next, for the stochastic integral ${\tilde{\gamma }}^{\epsilon }$, we have

By local boundedness of ${\gamma }^{\epsilon }$ and its a.s. convergence to 0 as $\epsilon \downarrow 0$, it follows that ${\tilde{\gamma }}_t^{\epsilon }\to 0$ in probability. A similar argument holds for ${\check{\gamma }}_t^{\epsilon }$. We conclude that (W, L, B) satisfies (2.27). Finally, by (5.16) and the fact ${{\int }_0^t\mathrm{𝟙}}_{\{W_s=z^{*}\}}ds=0$ a.s. just proved, one has ${\text{Ξ}}_t={\phi }^{*}(W_t)$ for a.e. t, a.s., which completes the proof of the claim, and also of the result. □

5.1.5. Proof of Theorem 2.13 and Corollary 2.15.

As a consequence of Theorem 5.1 and Proposition 5.3, we have the following.

Proof of Theorem 2.13.

The weak convergence statements asserted in the theorem are already established in Theorem 5.1. For the AO results, we need to show that in each of the six cases ${\widehat{J}}^n(T^n)\to V_0=h_q{\alpha }_q{V}_{\text{WCP}}(0)$. Combining Theorem 5.1 with the identification of an optimal control for the WCP given in Lemma 4.1 shows that ${\widehat{X}}^n\Rightarrow X$, where X_p = 0 and $X_q={\alpha }_{q}W$, W is given by (2.26) or (2.27) in the respective cases, and, moreover,

$$V_0=h_q{\alpha }_q\mathbb{E}{\displaystyle {\int }_0^{\infty }{e}^{-\gamma t}}{W}_{t}dt.$$

The convergence stated above implies

$${\widehat{H}}_t^n=h·{\widehat{X}}_t^n\Rightarrow h_q{\alpha }_q{W}_t.$$(5.17)

By (2.6), ${\widehat{J}}^n(T^n)=\mathbb{E}{\int }_0^{\infty }{e}^{-\gamma t}{\widehat{H}}_t^{n}dt$. Hence, the convergence ${\widehat{J}}^n(T^n)\to V_0$ will follow from (5.17) once uniform integrability is established. Arguing along the lines of Bell and Williams (2001, pp. 640–643), introduce the measure $dm=\gamma e^{-\gamma t}dt$ on $({\mathbb{R}}_{+},{\mathcal{R}}_{+})$ and invoke the Skorohod representation theorem to obtain from (5.17) that ${\widehat{H}}^n\to h_q{\alpha }_{q}W$ $(m\times \mathbb{P})$-a.e. Accordingly, uniform integrability of Hⁿ w.r.t. $m\times \mathbb{P}$ suffices to obtain ${\widehat{J}}^n(T^n)\to V_0$. However, this is ensured by Proposition 5.3, for

$$\underset{n}{\lim \sup }{\int }_{[0,\infty )\times \mathrm{\Omega }}{({\widehat{H}}^n)}^{1+{\epsilon }_0}d(m\times \mathbb{P})=\gamma \underset{n}{\lim \sup } \mathbb{E}{\displaystyle {\int }_0^{\infty }{e}^{-\gamma t}}{({\widehat{H}}_t^n)}^{1+{\epsilon }_0}dt<\infty ,$$

and the result is proved. □

Proof of Corollary 2.15.

As far as the proof of the Weak Convergence (2.29) and AO are concerned, there is no difference between the setting of Theorem 2.13(1), where the LP has multiple solutions but the single-mode condition holds, and the case where it has a single solution. Therefore, this result is a corollary of Theorem 2.13(1). □

5.2. Proof of Propositions 5.3–5.6

In Section 5.2.1, we provide several useful estimates. Then, Propositions 5.3, 5.4, 5.5, and 5.6 are proved in Section 5.2.2, Section 5.2.3, Sections 5.2.4 and 5.2.5, and Section 5.2.6, respectively.

5.2.1. Auxiliary Lemmas.

Two estimates on the rescaled primitives, ${\widehat{A}}_i^n$ and ${\widehat{S}}_{ik}^n$, are provided in (5.18) and Lemma 5.7, and a certain estimate on the maximum service duration is given in Lemma 5.9.

Because the assumptions on $A_i^n$ and $S_{ik}^n$ are similar, the estimates are stated for ${\widehat{A}}_i^n$, but apply also for ${\widehat{S}}_{ik}^n$. Recall that ${\check{a}}_i(l)$ are interarrival times of A_i and thus $a_i^n(l)≔{({\lambda }_i^n)}^{-1}{\check{a}}_i(l)$ are the interarrival times of $A_i^n$. Recall $E[{\check{a}}_i{(1)}^{\mathbf{m}}]<\infty$ for a constant $\mathbf{m}>2$. The first estimate is Krichagina and Taksar (1992, theorem 4), which states that for any $2\le \kappa \le \mathbf{m}$,

for a constant c that does not depend on n or t. The next useful estimate is as follows.

Lemma 5.7.

Let ${\nu }_1,{\nu }_2\in (0,1)$ be such that ${\nu }_1⩽{\nu }_2+\frac{1}{2}$ and assume that $h_0≔(\frac{\mathbf{m}}{2}-1){\nu }_1-\mathbf{m}{\nu }_2>0$ (note, in particular, that for every ${\nu }_1\in (0,\frac{1}{2}]$, there exists ${\nu }_2>0$ satisfying these conditions). Fix $c_1>0$. Then, for any $h<h_0$,

$$P(w_{t_0}({\widehat{A}}_i^n,n^{-{\nu }_1})⩾c_1{n}^{-{\nu }_2})⩽c{n}^{-h}{(1+t_0)}^{\mathbf{m}/2},\hspace{1em}\hspace{1em}n\in \mathbb{N},\hspace{0.17em}{t}_0\ge 1,$$

where $c=c(c_1,{\nu }_1,{\nu }_2,\mathbf{m})$ does not depend on n or t₀.

The proof appears in Appendix A.

Remark 5.8.

We sometimes use the balance equation in the following form, which follows from (5.4), namely,

$${\widehat{X}}_i^n(t)={\widehat{f}}_i^n(t)+n^{1/2}{\displaystyle {\int }_0^t(}{\lambda }_i-{\displaystyle \sum _k{\mu }_{ik}}{\text{Ξ}}_{ik}^n(s))ds,$$(5.19)

where

$${\widehat{f}}_i^n(t)≔{\widehat{A}}_i^n(t)-{\displaystyle \sum _k{\widehat{S}}_{ik}^n}(T_{ik}^n(t))+t{\widehat{\lambda }}_i^n-{\displaystyle \sum _k{T}_{ik}^n}(t){\widehat{\mu }}_{ik}^n.$$

Note that ${\widehat{F}}^n$ of (5.5) is given by ${\widehat{F}}^n(t)={\sum }_i{\alpha }_i^{-1}{\widehat{f}}_i^n(t).$ Then, using the 1-Lipschitz property of the trajectories of $T_{ik}^n$, it is easy to see that both estimates above imply some estimates for ${\widehat{f}}_i^n$. In particular, by (5.18), $\mathbb{E}\Vert {\widehat{f}}_i^n{\Vert }_t^{\kappa }\le c{(1+t)}^{\kappa }$. Moreover, under the assumptions of Lemma 5.7 and the additional assumption that ${\nu }_2<{\nu }_1$, the conclusion of the lemma holds for ${\widehat{f}}_i^n$ and ${\widehat{F}}^n$.

Next, we give an estimate on the maximal service duration and interarrival time up to a given time. The time in service by t of a given job is defined as the time that the job has spent in service up to time t. Let $\text{TIS}(n,i,k,l,t)$ denote the time in service by t of the lth job in activity (i, k). If service to job l has completed by time t, then, clearly, $\text{TIS}(n,i,k,l,t)=u_{ik}^n(l)$, but if it is still in service, $\text{TIS}(n,i,k,l,t)<u_{ik}^n(l)$. Of course, $\text{TIS}(n,i,k,l,t)=0$ for jobs for which service has not started by t. For t > 0 and a real-valued path $\phi$, denote

$$\mathrm{\Lambda }(\phi ,t)=\sup \{t_2-t_1:\hspace{0.17em}0\le t_1\le t_2\le t,\hspace{0.17em}{\phi }_{t_2}={\phi }_{t_1}\}.$$

Then, for activity (i, k), the maximal time in service by time t, namely, ${\sup }_l\text{TIS}(n,i,k,l)$, is bounded above by $\mathrm{\Lambda }(S_{ik}^n,t)$. We will need an upper bound on the service time as well as the interarrival times, and to this end define

$$e_{\text{max}}^n(t)=\underset{i,k}{\max } \mathrm{\Lambda }(S_{ik}^n,t)\vee \underset{i}{\max } \mathrm{\Lambda }(A_i^n,t).$$(5.20)

This process also bounds from above all service durations completed by time t.

Lemma 5.9.

One has $\mathbb{E}[{(e_{\text{max}}^n)}^2]\le c{n}^{-1}(1+t)$ for a constant c that does not depend on n or t. Moreover, for any $t<\infty$ and $c_1>0$, $\mathbb{P}(e_{\max }^n(t)⩾c_1{n}^{\overline{a}-1})\to 0,$ as $n\to +\infty$.

The proof appears in Appendix A.

5.2.2. Uniform Integrability.

Here, we prove Proposition 5.3. We sometimes need to refer to the variable keeping track of the current mode, which in the various policies is defined in slightly different ways according to different sampling times. Denote

Proof of Proposition 5.3.

The proof has three parts; part 1 appears below, while parts 2 and 3 are deferred to Appendix A. Fix any one of the sequences of policies $T^n\in {\mathcal{A}}^n$ for which we attempt to prove AO.

Part 1. This part is concerned with the case where, whenever the workload in the system is sufficiently large, policy P is active. This covers case 1(a) of Theorem 2.13, where the system has a single mode and the fixed priority policy P is applied, as well as case 2(a), where the dual-mode policy PP is applied. In this case, we will prove that the statement of the lemma holds with ${\epsilon }_0=1$, and specifically that, under the given sequence, $\mathbb{E}[{({\widehat{H}}_t^n)}^2]$ is bounded by a polynomial in t for all n. By (2.11), this is equivalent to the same property holding for $\mathbb{E}[{({\widehat{W}}_t^n)}^2]$.

To prove the result in this case, assume that in the single (resp., dual)-mode case, the active mode ξ^A (resp., the high-workload mode ξ^H) is in canonical form. Thus, provided that the workload in the system exceeds $z^{*}$ (when applicable), class 1 (resp., 2) is the dual (single)-activity class, and server 1 (resp., 2) is the single (dual)-activity server. In addition, p = 2: class 2 is the HPC. First, we provide a bound on the second moment of ${\widehat{X}}_2^n$. In the dual-mode case, fix K large enough so that ${\widehat{X}}_2^n(t)\ge K$ implies ${\widehat{W}}_t^n\ge z^{*}+1$; in the single-mode case let K = 1. Given t > 0, consider the event ${\widehat{X}}_2^n(t)>K$. Let $\tau ={\tau }_n(t)$ be defined by

$$\tau =\sup \{s\in [0,t]:{\widehat{X}}_2^n(s)\le K\}.$$

Because the system starts empty, $0\le \tau \le t$, and because the jumps of the normalized queue length are of size $n^{-1/2},\hspace{0.17em}{\widehat{X}}_2^n(\tau )\le K+1$. Thus,

$${\widehat{X}}_2^n(t)\le {\widehat{X}}_2^n(t)-{\widehat{X}}_2^n(\tau )+K+1.$$

By (5.3), denoting $C^n(t)={\sum }_i\Vert {\widehat{A}}_i^n{\Vert }_t+{\sum }_{ik}\Vert {\widehat{S}}_{ik}^n{\Vert }_t$,

$${\widehat{X}}_2^n(t)-{\widehat{X}}_2^n(\tau )\le 2C^n(t)+n^{-1/2}{\lambda }_2^n(t-\tau )-n^{-1/2}{\mu }_{22}^n(T_{22}^n(t)-T_{22}^n(\tau )).$$

Because ${\widehat{X}}_2^n\ge K$ in $[\tau ,t]$, the priority policy corresponding to a mode given in canonical form (either ξ^A or ξ^H) is in force after an initial time before the current mode updates and there are class 2 jobs to serve. We can bound the time until server 2 prioritizes class 2 and starts serving it at full rate in $[\tau ,t]$ by $e_{\text{max}}^n(t)$. If there currently is a class 2 job being served by server 2, server 2 only serves class 2 jobs for the whole period and

$$T_{22}^n(t)-T_{22}^n(\tau )=t-\tau .$$

If there currently is a class 1 job being served by server 2, because service is nonpreemptive, server 2 has to finish this job. If at that time, the current mode is ξ^H (resp. ξ^A in the single-mode case), server 2 prioritizes class 2 from that point on. If at that time, the current mode is ξ^L, the workload is then sampled because a service finished at the single activity server. The current mode changes to ξ^H and stays until t. In both cases, we get

$$T_{22}^n(t)-T_{22}^n(\tau )\ge t-\tau -e_{\max }^n.$$

Also, in the case under consideration, one has ${\mu }_{22}>{\lambda }_2$. Hence, for all sufficiently large n, ${\mu }_{22}^n>{\lambda }_{22}^n$. Moreover, $c_1≔{\sup }_n{n}^{-1}{\mu }_{22}^n<\infty$. Hence,

$${\widehat{X}}_2^n(t)\le 2C^n(t)+c_1{n}^{1/2}{e}_{\text{max}}^n(t)+K+1.$$

The above inequality holds also on the complementary event, namely, when ${\widehat{X}}_2^n(t)\le K$. Thus, using (5.18) and Lemma 5.9, we obtain

$$\mathbb{E}[\Vert {\widehat{X}}_2^n{\Vert }_t^2]\le c(1+t).$$(5.21)

In the next step, we bound ${\widehat{W}}_t^n$. Let $\tilde{K}$ be a constant that is sufficiently large to ensure that ${\widehat{X}}_1^n(t)\ge \tilde{K}$ implies ${\widehat{W}}^n(t)\ge z^{*}+1$ (where, again, $\tilde{K}=1$ in the single-mode case). Given t > 0, consider the event ${\widehat{X}}_1^n(t)>\tilde{K}$ and let $\sigma ={\sigma }_n(t)$ be

$$\sigma =\sup \{s\in [0,t]:{\widehat{X}}_1^n(s)\le \tilde{K}\}.$$

Then, clearly, $\sigma \in [0,t]$. Because during $[\sigma ,t]$, there are at least two jobs of class 1 in the system, both servers are never idle during $[\sigma ,t]$. Because one has ${\widehat{X}}_1^n(\sigma )\le \tilde{K}+n^{-1/2}$, it follows that ${\widehat{W}}_{\sigma }^n\le c(1+\tilde{K}+{\widehat{X}}_2^n(\sigma ))$. Hence,

$${\widehat{W}}_t^n\le {\widehat{W}}_t^n-{\widehat{W}}_{\sigma }^n+c(1+\tilde{K}+\Vert {\widehat{X}}_2^n{\Vert }_t).$$

By (5.6) and the nonidling of both servers during $[\sigma ,t]$, by which ${\widehat{L}}^n$ remains flat during this interval, we have ${\widehat{W}}_t^n-{\widehat{W}}_{\sigma }^n={\widehat{F}}_t^n-{\widehat{F}}_{\sigma }^n$. Thus, by (5.5), for a constant c (that may depend on $\tilde{K}$),

$${\widehat{W}}_t^n\le c(C^n(t)+t+1+\Vert {\widehat{X}}_2^n{\Vert }_t).$$

Clearly, the above bound is valid also in the complementary event, ${\widehat{X}}_1^n(t)\le \tilde{K}$. We can therefore apply (5.18) and (5.21), to obtain $\mathbb{E}[{({\widehat{W}}_t^n)}^2]\le c(1+t)$ for some constant c, for all n and t. Consequently, the same holds for the second moment of ${\widehat{H}}_t^n$, and the result follows. This completes part 1 of the proof. The remaining parts appear in Appendix A. □

5.2.3. State Space Collapse.

We now prove Proposition 5.4. Assume that either the active mode ξ^A or the lower workload mode ξ^L (whichever is applicable) is in canonical form. Let

This random time is used outside this proof with the notation ${\tau }_c^n$, but in this proof, the shorter notation τ is used. Then,

We will prove the lemma by showing that the RHS above converges to zero as $n\to \infty$. On the event $\{\tau ⩽t_0\}$, define

The proof relies on the fact that, under our policies, when the number of HPC jobs is above ${\text{Θ}}^n$, it is served at a rate that is enough to deplete the queue in all cases. The first step toward this goal is the following.

Lemma 5.10.

There exist constants $c_1,c_2>0$ such that, on $\{\tau ⩽t_0\}$,

$${\displaystyle {\int }_{\sigma }^{\tau }(}{\lambda }_p-{\displaystyle \sum _k{\mu }_{pk}}{\text{Ξ}}_{pk}^n(t))dt\hspace{0.17em}⩽-c_1(\tau -\sigma )+c_2{e}_{\max }^n,$$(5.22)

with $e_{\max }^n$ defined in (5.20).

Proof.

First, by definition of σ, and τ, and the fact that jumps of ${\widehat{X}}^n$ are of size $n^{-1/2}<{\widehat{\text{Θ}}}^n/2$ for large n, we obtain

$$\underset{t\in [\sigma ,\tau ]}{\inf }{\widehat{X}}_p^n(t)⩾{\widehat{\text{Θ}}}^n.$$

We address here one case only; the proof under the remaining cases is deferred to Appendix A.

• Case 1(a): In this case, we use the P policy, which is single mode. Because the active mode is in canonical form and $i_1({\xi }^A)=p$, p = 2, and server 2 prioritizes class 2. It is possible that server 2 is busy with the “wrong” class of job at time σ, but as soon as that job finishes, server 2 will only serve the class 2 jobs in the system:

  $${\displaystyle {\int }_{\sigma }^{\tau }{\text{Ξ}}_{22}^n}(t)dt⩾\tau -\sigma -e_{\max }^n.$$

Thus,

$${\displaystyle {\int }_{\sigma }^{\tau }(}{\lambda }_2-{\displaystyle \sum _k{\mu }_{2k}}{\text{Ξ}}_{2k}^n(t))dt⩽(\tau -\sigma )({\lambda }_2-{\mu }_{22})+{\mu }_{22}{e}_{\max }^n.$$

To show that ${\lambda }_2-{\mu }_{22}<0$, note that since the active mode is in canonical form, $\frac{{\lambda }_1}{{\alpha }_1}>{\beta }_1$, which implies $\frac{{\lambda }_2}{{\alpha }_2}<{\beta }_2$ by (3.1).

The remaining cases appear in Appendix A. □

Now that Lemma 5.10 has been proved in all cases, the proof of Proposition 5.4 does not need to differentiate between them.

Proof of Proposition 5.4.

Let ${\nu }_2=1/2-\overline{a}⩽1/4$ and ${\nu }_1\in ({\nu }_2,\hspace{0.17em}1/2)$. Recall that ${\widehat{\text{Θ}}}^n=n^{-1/2}\lceil n^{\overline{a}}\rceil$, as defined in (2.32), so that ${\widehat{\text{Θ}}}^n=n^{-1/2}\lceil n^{1/2-{\nu }_2}\rceil ⩾n^{-{\nu }_2}$. Notice that, as required in Lemma 5.7, ${\nu }_1⩽{\nu }_2+\frac{1}{2}$. Let us introduce the event

$${\mathrm{\Omega }}_1=\left\{\tau ⩽t_0,\hspace{0.17em}{\widehat{X}}_p^n(\tau )-{\widehat{X}}_p^n(\sigma )⩾\frac{{\widehat{\text{Θ}}}^n}{4},\underset{t\in [\sigma ,\tau ]}{\inf }{\widehat{X}}_p^n(t)⩾{\widehat{\text{Θ}}}^n\right\}.$$

For n large enough, one has ${\widehat{X}}_p^n(\sigma )<\frac{7}{4}{\widehat{\text{Θ}}}^n$. Consequently, $\{\tau \le t_0\}={\mathrm{\Omega }}_1$. We obtain

$$\mathbb{P}\left(\tau ⩽t_0\right)=\mathbb{P}\left({\mathrm{\Omega }}_1\right)=\mathbb{P}\left({\mathrm{\Omega }}_1\cap \{\tau -\sigma ⩽n^{-{\nu }_1}\}\right)+\mathbb{P}\left({\mathrm{\Omega }}_1\cap \{\tau -\sigma >n^{-{\nu }_1}\}\right).$$(5.23)

Picking up on (5.19), by Lemma 5.10

$$\begin{array}{l}{\widehat{X}}_p^n(\tau )-{\widehat{X}}_p^n(\sigma )={\widehat{f}}_p^n(\tau )-{\widehat{f}}_p^n(\sigma )+\sqrt{n}{\displaystyle {\int }_{\sigma }^{\tau }(}{\lambda }_p-{\displaystyle \sum _k{\mu }_{pk}}{\text{Ξ}}_{pk}^n(t))dt\\ ⩽{\widehat{f}}_p^n(\tau )-{\widehat{f}}_p^n(\sigma )-c\sqrt{n}(\tau -\sigma )+c\sqrt{n}{e}_{\max }^n.\end{array}$$

Notice that on the event $\{\tau -\sigma ⩽n^{-{\nu }_1},\hspace{0.17em}\tau ⩽t_0\}$,

$${\widehat{X}}_p^n(\tau )-{\widehat{X}}_p^n(\sigma )⩽w_{t_0}({\widehat{f}}_p^n,n^{-{\nu }_1})+c\sqrt{n}{e}_{\max }^n.$$

Thus,

$$\begin{array}{l}\mathbb{P}\left({\mathrm{\Omega }}_1\cap \{\tau -\sigma ⩽n^{-{\nu }_1}\}\right)⩽\mathbb{P}\left(w_{t_0}({\widehat{f}}_p^n,n^{-{\nu }_1})+e_{\max }^n\sqrt{n}⩾\frac{n^{-{\nu }_2}}{2}\right)\\ ⩽\mathbb{P}\left(w_{t_0}({\widehat{f}}_p^n,n^{-{\nu }_1})⩾\frac{n^{-{\nu }_2}}{4}\right)+\mathbb{P}\left(c{e}_{\max }^n\sqrt{n}⩾\frac{n^{-{\nu }_2}}{4}\right).\end{array}$$

Recall that ${\nu }_1\in ({\nu }_2,1/2)$, so $n^{-{\nu }_1}<n^{-{\nu }_2}$. By Lemma 5.7 and Remark 5.8, the first term converges to zero. By Lemma 5.9 and ${\nu }_2=1/2-\overline{a}$,

$$\mathbb{P}\left(e_{\max }^n⩾\frac{c}{4}{n}^{-{\nu }_2-1/2}\right)=\mathbb{P}\left(e_{\max }^n⩾\frac{c}{4}{n}^{\overline{a}-1}\right)\to 0.$$

For the second term in (5.23), notice that on $\{\tau -\sigma >n^{-{\nu }_1},\hspace{0.17em}\tau ⩽t_0\}$,

$${\widehat{X}}_p^n(\tau )-{\widehat{X}}_p^n(\sigma )⩽2\Vert {\widehat{f}}_p^n(t){\Vert }_{t_0}+e_{\max }^n\sqrt{n}-c\sqrt{n}{n}^{-{\nu }_1},$$

and

$${\widehat{X}}_p^n(\tau )-{\widehat{X}}_p^n(\sigma )⩾\frac{{\widehat{\text{Θ}}}^n}{2}-n^{-1/2}.$$

Hence,

$$\mathbb{P}\left({\mathrm{\Omega }}_1\cap \{\tau -\sigma >n^{-{\nu }_1}\}\right)⩽\mathbb{P}\left(2\Vert {\widehat{f}}_p^n{\Vert }_{t_0}+e_{\max }^n\sqrt{n}⩾c\sqrt{n}{n}^{-{\nu }_1}+\frac{{\widehat{\text{Θ}}}^n}{2}-n^{-1/2}\right).$$

By Lemma 5.9, $e_{\max }^n$ is smaller than $n^{\overline{a}-1}=o(n^{-1/2})$. By Remark 5.8, $2\Vert {\widehat{f}}_p^n{\Vert }_{t_0}$ is a tight sequence of random variables (RVs) (for t₀ fixed). Because ${\nu }_1<1/2,\hspace{0.17em}\sqrt{n}{n}^{-{\nu }_1}\to +\infty$. The claim follows. □

5.2.4. Boundary Behavior.

The goal of this section and the following one is to prove Proposition 5.5. The key is the following lemma, which states, roughly speaking, that ${\widehat{L}}^n$ is approximately the boundary term corresponding to ${\widehat{F}}^n$.

Let $c_3=\frac{3}{{\alpha }_1\wedge {\alpha }_2}$.

Lemma 5.11.

Fix $t_0>0$. With

$${\overline{R}}_t^n={\displaystyle {\int }_0^t }{\mathrm{𝟙}}_{{\widehat{W}}_s^n⩾c_3{\widehat{\text{Θ}}}^n}d{\widehat{L}}_s^n,$$(5.24)

${\overline{R}}_{t_0}^n\to 0$ in probability as $n\to \infty$.

This lemma is proved in the next subsection. Let us show how Proposition 5.5 now follows.

Proof of Proposition 5.5.

In addition to ${\overline{R}}^n$ just introduced, we shall need the following definitions:

$$\begin{array}{l}{Z}_t^n=\max ({\widehat{W}}_t^n-c_3{\widehat{\text{Θ}}}^n,\hspace{0.17em}0),\\ {\tilde{R}}_t^n={\displaystyle {\int }_0^t}{\mathrm{𝟙}}_{{\widehat{W}}_s^n<c_3{\widehat{\text{Θ}}}^n}d{\widehat{L}}_s^n,\\ {\mathrm{\Delta }}_t^n=Z_t^n-{\widehat{W}}_t^n.\end{array}$$

By (5.6) and definition of the new processes, one has

$$Z_t^n={\widehat{F}}_t^n+{\mathrm{\Delta }}_t^n+{\overline{R}}_t^n+{\tilde{R}}_t^n.$$

Consider the pair $(Z^n,{\tilde{R}}^n)$. The first component is nonnegative. The second is nonnegative, nondecreasing, and, moreover,

$${\int }_{[0,\infty )}{Z}_t^{n}d{\tilde{R}}_t^n={\int }_{[0,\infty )}\max ({\widehat{W}}_t^n-c_3{\widehat{\text{Θ}}}^n,\hspace{0.17em}0){\mathrm{𝟙}}_{{\widehat{W}}_t^n<c_3{\widehat{\text{Θ}}}^n}d{\widehat{L}}_t^n=0.$$

Hence, by Skorohod’s Lemma, $(Z^n,{\tilde{R}}^n)=\mathrm{\Gamma }({\widehat{F}}^n+{\mathrm{\Delta }}^n+{\overline{R}}^n)$. Hence,

$${\widehat{W}}^n={\mathrm{\Gamma }}_1({\widehat{F}}^n+{\mathrm{\Delta }}^n+{\overline{R}}^n)-{\mathrm{\Delta }}^n,\hspace{1em}\hspace{1em}{\widehat{L}}^n={\mathrm{\Gamma }}_2({\widehat{F}}^n+{\mathrm{\Delta }}^n+{\overline{R}}^n)+{\overline{R}}^n.$$(5.25)

Recall that we are considering a subsequence along which (according to the assumptions and to Lemma 5.2), $({\widehat{A}}^n,{\widehat{S}}^n,T^n,{\widehat{F}}^n)\Rightarrow (A,S,T,F)$, with F as in (5.8). Moreover, by the definition of Zⁿ and ${\mathrm{\Delta }}^n$, we have $0\le -{\mathrm{\Delta }}_t^n\le c_3{\widehat{\text{Θ}}}^n$, whereas by Lemma 5.11, ${\overline{R}}^n\to 0$ in probability. By the continuity of the map $\mathrm{\Gamma }$, we therefore conclude from (5.25) that, on the same subsequence,

$$({\widehat{A}}^n,{\widehat{S}}^n,T^n,{\widehat{F}}^n,{\widehat{W}}^n,{\widehat{L}}^n)\Rightarrow (A,S,T,F,W,L),$$

where $(W,L)=\mathrm{\Gamma }(F)$. This completes the proof. □

5.2.5. Proof of Lemma 5.11.

We first explain how the proof changes between the cases.

• Under the P policy, both servers can process the low priority jobs. This means that idling can only occur if the low-priority class has few jobs, and, in that case, the total number of jobs is also low by Proposition 5.4.

• Under the ${\mathbf{T}}_2$ rule, no server can incur idleness when the high-priority class is above the threshold. In addition, the high-priority class takes a small time to reach above ${\text{Θ}}^n$ and does not empty below two jobs after that time with high probability unless the total workload is close to zero (Lemma 5.13). This means that neither server will idle except when there are almost no jobs in the system.

• Under the PP policy, Proposition 5.4 is still enough to prove Lemma 5.11 in the same way as in the single-mode case P.

• Under the ${\mathbf{T}}_2{\mathbf{T}}_2$ policy, Lemma 5.12 and 5.13 hold. Because of that, Lemma 5.11 holds for the same reason as in the nonswitching case ${\mathbf{T}}_2$.

• When using a P rule, the high-priority class could become zero with a lot of LPC jobs in the system, and switching to the ${\mathbf{T}}_2$ rule could lead to idleness, even though there are a lot of low-priority jobs (approximately ${\alpha }_q{z}^{*}$). Thus, we introduce the ${\mathbf{T}}_1$ rule in place of the P rule in this case. This ensures that the number of high-priority jobs does not decrease too much during the corresponding period.

In some cases, some idleness can occur when the high-priority class starts with too few jobs, but in those cases, it takes a small time to leave such states.

In cases 1(a) and 2(a), Lemma 5.11 is a direct consequence of the state space collapse. Let us introduce two random times and a lemma that we will use in cases 1(b) and 2(b)–(d). Fix $t_0>0$. Let

Lemma 5.12.

If any of the following conditions hold, we have

$${\overline{R}}_{{\rho }^n}^n\to 0 \mathit{\text{in}} \mathit{\text{probability}}.$$(5.26)

• Case 1(b), (2.20) and $i_2({\xi }^A)=p$.

• Case 2(b), (2.21) and $i_2({\xi }^L)=i_2({\xi }^H)=p$.

• Cases 2(c) and 2(d), (2.21) and $i_1({\xi }^L)=i_2({\xi }^H)$.

Lemma 5.13.

Under the same assumptions as the previous lemma,

$$\mathbb{P}\left({\tau }_r^n⩽t_0\right)\to 0.$$(5.27)

The proofs of Lemmas 5.12 and 5.13 appear in Appendix A.

Remark 5.14.

The above two lemmas do not address cases 1(a) and 2(a). The reason for this is that in these cases, we can directly prove Lemma 5.11 when using a P or PP policy.

Proof of Lemma 5.11.

Here, we only treat one case, deferring the remaining cases to Appendix A.

• Case 1(a), P policy:

In this case, p = 2, and no server can be idle when $X_1⩾2$. Thus,

$${\displaystyle {\int }_0^{t_0}}{\mathrm{𝟙}}_{{\widehat{X}}_1^n(t)⩾2n^{-1/2}}d{\widehat{L}}_t^n=0.$$(5.28)

For any $\delta >0$,

$$\begin{array}{l}\mathbb{P}\left({\overline{R}}_{t_0}^n⩾\delta \right)⩽\mathbb{P}\left({\displaystyle {\int }_0^{t_0}({\mathrm{𝟙}}_{{\widehat{X}}_2^n(t)⩾2{\widehat{\text{Θ}}}^n}+{\mathrm{𝟙}}_{{\widehat{X}}_1^n(t)⩾2n^{-1/2}})}d{\widehat{L}}_t^n⩾\delta \right)\\ =\mathbb{P}\left({{\displaystyle {\int }_0^{t_0}\mathrm{𝟙}}}_{{\widehat{X}}_2^n(t)⩾2{\widehat{\text{Θ}}}^n}d{\widehat{L}}_t^n⩾\delta \right)\\ ⩽\mathbb{P}\left({\mathrm{𝟙}}_{\underset{t⩽t_0}{\sup }{\widehat{X}}_2^n(t)⩾2{\widehat{\text{Θ}}}^n}{\widehat{L}}^n(t_0)⩾\delta \right)\\ ⩽\mathbb{P}\left(\underset{t⩽t_0}{\sup }{\widehat{X}}_2^n(t)⩾2{\widehat{\text{Θ}}}^n\right)\\ =\mathbb{P}\left({\tau }_c^n⩽t_0\right).\end{array}$$

By Proposition 5.4,

$$\mathbb{P}\left({\tau }_c^n⩽t_0\right)\to 0.$$(5.29)

The treatment of the remaining cases appears in Appendix A. □

5.2.6. Fast Switching

Proof of Proposition 5.6.

Fix t₀ and $\epsilon >0$. Assume that ξ^L is in canonical form. Then, $(i^l,k^l)=(2,1)$. Let

$$\begin{array}{l}{\tau }_f=\inf \left\{t⩾0:\hspace{0.17em}{\displaystyle {\int }_0^t}{\mathrm{𝟙}}_{{\widehat{W}}_t^n⩽z^{*}-\epsilon }d{T}_{21}^n(t)>0\right\},\\ t_{\min }=\sup \left\{t⩽{\tau }_f:\hspace{0.17em}{\widehat{W}}_t^n⩾z^{*}\right\},\\ t_{\max }=\inf \left\{t⩾t_{\min }:\hspace{0.17em}{\widehat{W}}_t^n⩽z^{*}-\epsilon \right\},\\ {\tau }_1=\inf \left\{t⩾t_{\min }:{\text{MODE}}^n(t)={\xi }^L\right\},\end{array}$$

where the dependence on n is suppressed. The first statement of the lemma will be proved once we show $\mathbb{P}({\tau }_f⩽t_0)\to 0.$ We omit the proof of the second statement, which is similar. To this end, let

$${\kappa }^n=\inf \{s⩾0 \hspace{0.17em}\text{s}.\text{t}. \exists t⩽t_0,\hspace{0.17em}{\widehat{W}}_{t-s}^n⩾z^{*},\hspace{0.17em}{\widehat{W}}_t^n⩽z^{*}-\epsilon \}.$$

If ${\sup }_{t⩽t_0}{\widehat{W}}_t^n⩽z^{*}$, the current mode never changes, so the single-activity server is dedicated to only one class for the whole period and the nonbasic activity is never used. Thus,

$$\{{\tau }_f⩽t_0\}\subset \{t_{\max }⩽t_0\}.$$

Note that we have used the fact that, for all of our policies, jobs are never routed to a nonbasic activity of the current mode.

The remainder of the argument is based on the following fact, which must be argued separately for each case. This is concerned with the difference ${\tau }_1-t_{\min }$, which, although case-dependent, can in all cases be shown to satisfy

$$\underset{n\to +\infty }{\lim }\mathbb{P}\left({\tau }_1-t_{\min }>e_{\max }^n\right)=0.$$(5.30)

By Proposition 5.5, ${\widehat{W}}^n$ is C-tight. Hence, for any constant c > 0, $\mathbb{P}(c{\kappa }^n⩽n^{\overline{a}-1})\to 0$. On the other hand, by Lemma 5.9, $\mathbb{P}(e_{\max }^n⩾n^{\overline{a}-1})\to 0$. Thus,

$$\mathbb{P}\left(e_{\max }^n⩾c{\kappa }^n\right)\to 0.$$(5.31)

In order for ${\int }_0^{t_0}{\mathrm{𝟙}}_{W_t^n⩽z^{*}-\epsilon }d{T}_{21}^n(t)$ to become positive, $t_{\max }$ must be smaller than t₀ and

$$t_{\max }-{\tau }_1<e_{\max }^n.$$

It is not possible for $t_{\max }-{\tau }_1⩾e_{\max }^n$ to occur on $\{{\tau }_f⩽t_0\}$. If that were the case, server 1 would necessarily finish service of the job it was in the process of serving at time τ₁ before the workload has time to reach $z^{*}-\epsilon$. When ${\text{MODE}}^n(t)={\xi }^L$ in canonical form, server 1 can only take new class 1 jobs, regardless of the rule. Even if class 1 has no job in the queue, the nonbasic activity is not used after the possible residual job that was in service at time τ₁. In addition, by definition of $t_{\min }$, this is the last time the mode switches from upper to lower workload before τ_f. This would prevent ${\int }_0^{{\tau }_f}{\mathrm{𝟙}}_{{\widehat{W}}_t^n⩽z^{*}-\epsilon }d{T}_{21}^n(t)$ from becoming positive and is also the reason why $t_{\max }$ needs to be smaller than t₀ for τ_f to be smaller than t₀.

By definition of $t_{\max }$ and κⁿ,

$$\mathbb{P}\left(t_{\max }⩽t_0,\hspace{0.17em}{t}_{\max }-t_{\min }<{\kappa }^n\right)=0.$$

We next show that

$$\underset{n\to +\infty }{\lim }\mathbb{P}\left(t_{\max }⩽t_0,\hspace{0.17em}{\tau }_1⩾t_{\max }\right)=0.$$(5.32)

We have

$$\begin{array}{l}\mathbb{P}\left(t_{\max }⩽t_0,\hspace{0.17em}{\tau }_1⩾t_{\max }\right)=\mathbb{P}\left(t_{\max }⩽t_0,\hspace{0.17em}{\tau }_1⩾t_{\max },t_{\max }-t_{\min }⩾{\kappa }^n\right)\\ ⩽\mathbb{P}\left({\tau }_1⩾t_{\min }+{\kappa }^n\right)\\ ⩽\mathbb{P}\left({\tau }_1⩾t_{\min }+{\kappa }^n,e_{\max }^n⩽{\kappa }^n\right)+\mathbb{P}\left({\tau }_1⩾t_{\min }+{\kappa }^n,e_{\max }^n>{\kappa }^n\right)\\ ⩽\mathbb{P}\left({\tau }_1⩾t_{\min }+e_{\max }^n\right)+\mathbb{P}\left(e_{\max }^n>{\kappa }^n\right).\end{array}$$

Both terms converge to zero, the first by (5.30) and the second by (5.31).

We can now prove the lemma based on (5.32), (5.30), and (5.31). We have

$$\begin{array}{l}\mathbb{P}\left({\tau }_f⩽t_0\right)=\mathbb{P}\left({\tau }_f⩽t_0,\hspace{0.17em}{t}_{\max }⩽t_0\right)\\ =\mathbb{P}\left({\tau }_f⩽t_0,\hspace{0.17em}{t}_{\max }⩽t_0,\hspace{0.17em}{\tau }_1⩾t_{\max }\right)+\mathbb{P}\left({\tau }_f⩽t_0,\hspace{0.17em}{t}_{\max }⩽t_0,\hspace{0.17em}{\tau }_1⩽t_{\max },\hspace{0.17em}{t}_{\max }-{\tau }_1<e_{\max }^n\right)\\ ⩽\mathbb{P}\left(t_{\max }⩽t_0,{\tau }_1⩾t_{\max }\right)+\mathbb{P}\left(t_{\max }⩽t_0,\hspace{0.17em}{t}_{\max }-t_{\min }⩽2e_{\max }^n\right)+\mathbb{P}\left({\tau }_1-t_{\min }>e_{\max }^n\right)\\ ⩽\mathbb{P}\left(t_{\max }⩽t_0,{\tau }_1⩾t_{\max }\right)+\mathbb{P}\left({\kappa }^n⩽2e_{\max }^n\right)+\mathbb{P}\left(t_{\max }⩽t_0,\hspace{0.17em}{t}_{\max }-t_{\min }<{\kappa }^n\right)\\ +\mathbb{P}\left({\tau }_1-t_{\min }>e_{\max }^n\right).\end{array}$$

The first term goes to zero by (5.32), the second by (5.31), the third is zero, and the fourth goes to zero by (5.30). This completes the proof.

It remains to prove (5.30). As noted above, the proof differs by case.

Case 2(a): The current mode changes to ξ^L after the first service completion of a job at the single-activity server for ξ^H (which is server 2) at or after $t_{\min }$. Note that $t_{\min }$ must correspond to a service completion. If $t_{\min }$ corresponds to a service completion at server 2, the ${\tau }_1=t_{\min }$. If $t_{\min }$ corresponds to a service completion at server 1, then the mode will not change, and τ₁ will correspond to the next service completion at server 2. This will occur before $t_{\min }+e_{\max }^n$ if server 2 is busy (serving class 1) at $t_{\min }$. Note that, on $\{{\tau }_c^n⩾t_0\},\hspace{0.17em}{\widehat{X}}_2^n(t_{\min })<2{\widehat{\text{Θ}}}^n$, so that

$$X_1^n(t_{\min })⩾{\alpha }_1(W_{t_{\min }}^n-2{\alpha }_2^{-1}{\text{Θ}}^n)⩾{\alpha }_1(n^{1/2}{z}^{*}-1-2{\alpha }_2^{-1}{\text{Θ}}^n)⩾2,$$

so server 2 is busy at $t_{\min }$. Thus,

$$\mathbb{P}\left({\tau }_1-t_{\min }>e_{\max }^n\right)⩽\mathbb{P}\left({\tau }_c^n⩽t_0\right),$$

which converges to zero by Proposition 5.4. This proves (5.30).

Case 2(b): The current mode changes after the first service completion of a job at the single-activity server (which is server 2) at or after $t_{\min }$. Server 2 is dedicated to HPC jobs. Under $\{{\tau }_r^n⩾t_0,{\rho }^n⩽t_{\min }\}$, there are at least two HPC jobs in the system at time $t_{\min }$, so the single-activity server cannot be idling at that time. Thus,

$$\mathbb{P}\left({\tau }_1-t_{\min }>e_{\max }^n\right)⩽\mathbb{P}\left({\tau }_r^n⩽t_0\right)+\mathbb{P}\left({\rho }^n>t_{\min }\right).$$

By Lemma 5.13, $\mathbb{P}({\tau }_r^n⩽t_0)$ converges to zero. In addition,

$$\begin{array}{l}\mathbb{P}\left({\rho }^n>t_{\min }\right)=\mathbb{P}\left({\rho }^n>t_{\min },t_{\min }>\tilde{\tau }\right)+\mathbb{P}\left({\rho }^n>t_{\min },t_{\min }⩽\tilde{\tau }\right)\\ ⩽\mathbb{P}\left({\rho }^n>\tilde{\tau }\right)+\mathbb{P}\left(t_{\min }⩽\tilde{\tau }\right)\\ ⩽\mathbb{P}\left({\rho }^n>\tilde{\tau },{\tau }_c^n⩾t_0\right)+\mathbb{P}\left({\rho }^n>\tilde{\tau },{\tau }_c^n<t_0\right)+\mathbb{P}({\widehat{X}}_2^n(t_{\min })<{\alpha }_2{z}^{*}/2)\\ ⩽\mathbb{P}\left({\rho }^n>\tilde{\tau },{\tau }_c^n⩾t_0\right)+2\mathbb{P}\left({\tau }_c^n<t_0\right).\end{array}$$

where $\tilde{\tau }$ is defined in the proof of Lemma 5.12. Both terms converge to zero, the first by Lemma 5.13, and the second by Proposition 5.4. This proves (5.30).

Cases 2(c) and 2(d): The current mode changes after the first service completion or arrival of a low- or high-priority job after $t_{\min }$ so under $\{t_{\max }⩽t_0\}$,

$${\tau }_1-t_{\min }⩽e_{\max }^n,$$

Thus, (5.30) follows from Lemma 5.9. □