REVIEW 2 major objections 5 minor 31 references
Optimal scheduling of critically loaded multiclass GI/M/n+M queues in an alternating renewal environment
T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read This paper proves that, in the Halfin-Whitt regime, the optimal scheduling value of a multiclass many-server queue with renewal arrivals and service interruptions converges to the optimal value of a limiting compound-Poisson…
desk verdict A genuinely new FCLT and asymptotic optimality for multiclass queues with renewal arrivals and service interruptions, but the ergodic proof has a flagged gap in Lemma 5.2 that needs closing. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Three mechanisms carry the argument. First, the non-Markovian queueing process is augmented with the age processes of the renewal interarrival times and of the down state, which makes the state Markov; convergence of the generators to the generator of the limiting jump diffusion is proved with test functions $\varphi_n[f]$ built from residual-life functions $\eta_i^n$ and $\kappa_i^n$. Second, long-run average moment bounds for the diffusion-scaled processes are obtained from Foster-Lyapunov inequalities for this augmented process under a modified priority policy, using Lyapunov functions with renewal residual-life corrections. Third, asymptotic optimality is assembled from a lower bound via convergence of mean empirical measures to ergodic occupation measures and an upper bound via a spatial-truncation, concatenated scheduling policy that implements an $\epsilon$-optimal control of the limit inside a compact set and the modified priority policy outside.
What would settle it
Take interarrival times with finite moments of all orders but unbounded mean residual life, for instance a Weibull distribution with shape $1/2$ scaled to mean $1$, run the diffusion-scaled system under the modified priority policy, and check whether the long-run average moment bound (4.19) still holds; if $\sup_n \limsup_{T\to\infty} \frac{1}{T}E\int_0^T |\hat X^n(s)|^\kappa\,ds$ diverges, then Theorem 4.1, and with it Theorem 3.3, fails in that case.
Extended reading notes
Core claim
The central claim is Theorem 3.2 and Theorem 3.3. Under the Halfin-Whitt assumptions and the bounded mean residual life condition, if the initial scaled state $\hat X^n(0)$ converges to $x$, then the optimal discounted value $\hat V_\alpha^n(\hat X^n(0))$ converges to $V_\alpha(x)$, and the optimal ergodic cost $\hat\rho_n(\hat X^n(0))$ converges to $\rho^*$, where $V_\alpha$ and $\rho^*$ are the optimal values of the controlled jump diffusion $$dX_t = b(X_t,U_t)dt + \Sigma dW_t + \$\lambda$ dL_t$$ with drift $$b(x,u)=\ell - M(x-\langle e,x\rangle^+ u)-\langle e,x\rangle^+ \Gamma u,$$ diffusion coefficient $\Sigma=\operatorname{diag}(\sqrt{\lambda_i(1+c_{a,i}^2)})$, and $L$ a compound Poisson process representing accumulated downtime. The paper establishes that scheduling policies for the original queue can be chosen so that their performance approaches the optimum of this limiting control problem, for both discounted and ergodic criteria.
Load-bearing premise
The load-bearing premise is Assumption 3.2(ii), the bounded mean residual life condition (3.10): the mean residual life of each interarrival time and of the downtime variable is bounded by a constant over all horizons, and without it the paper provides no alternative bound, so the ergodic asymptotic optimality theorem would not be established.
Editorial extensions
If this is right
- The optimal cost of the original scheduling problem is asymptotically computed by solving the HJB equation of the limiting jump diffusion; stationary Markov optimal controls of the limit induce asymptotically optimal scheduling policies for the queue.
- Non-exponential renewal arrivals enter the limit only through their squared coefficients of variation, so higher-order interarrival distribution details are washed out in the Halfin-Whitt scaling.
- Asymptotically negligible service interruptions add an independent compound-Poisson noise term to the limiting dynamics, so their effect on optimal cost can be quantified and priced into the limiting control problem.
- A concrete modified priority policy yields uniform long-run average moment bounds; outside a compact set, running this policy and inside it following the limit's $\epsilon$-optimal control achieves cost arbitrarily close to $\rho^*$ for large $n$.
Reading between the lines
- My inference: the same augmented-generator scheme should extend to other regenerative environments, such as Markov-modulated up-down cycles whose rates depend on $n$, with the jump-diffusion limit's Lévy measure changed accordingly, provided a bounded residual-life condition holds.
- My inference: the bounded mean residual life condition could plausibly be relaxed to polynomial growth of residual-life functions at the cost of higher-degree Lyapunov functions, suggesting a threshold effect where heavy-tailed interarrival or downtime distributions eventually destroy uniform moment bounds under fixed priority policies.
- My inference: one could numerically test convergence rates by comparing finite-$n$ costs under the policy induced by the limit HJB against the predicted value, although the paper does not quantify the rate of convergence.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies a sequence of multiclass GI/M/n+M queues with renewal arrivals, exponential services and abandonments, and an alternating renewal (up-down) environment, in the Halfin-Whitt regime. The authors prove a functional central limit theorem showing that diffusion-scaled state processes under non-anticipative work-conserving policies converge to a controlled compound-Poisson jump diffusion. They then study the infinite-horizon discounted and long-run average (ergodic) scheduling problems and claim asymptotic optimality: the optimal values of the queueing models converge to the optimal values of the limiting jump-diffusion control problem. The main technical tool is an augmented Markovian model that includes the age processes of the renewal arrivals and the residual/age process of the down state; generator convergence for this augmented model, together with Foster-Lyapunov moment bounds, is used in place of the usual martingale arguments for mean empirical measures. The discounted result is proved in the style of Atar-Mandelbaum-Reiman, while the ergodic result is proved through lower and upper bounds, with the lower bound relying on a uniform moment estimate for arbitrary admissible Markov policies.
Significance. If the results are correct, this is a substantial contribution: it appears to be the first asymptotic-optimality result for ergodic control of multiclass many-server queues with general renewal arrivals, and the first treatment of optimal scheduling control in an alternating-renewal service-interruption environment at this scaling. The augmented-generator method, the construction of the approximate test functions in (5.12), and the Foster-Lyapunov estimates are nontrivial and likely to be reusable. The discounted theorem and the FCLT are developed in detail and look sound. However, the ergodic lower bound depends on Lemma 5.2, whose proof explicitly treats only the case I0=empty and asserts the nonempty case without calculation. Since the assumptions allow zero-abandonment classes, this is a load-bearing gap, not a cosmetic omission. The central ergodic theorem is therefore not fully established as written.
major comments (2)
- [Appendix B, Proof of Lemma 5.2, final paragraph] The proof of Lemma 5.2 explicitly treats only the case I0=empty; after equation (B.23) it says "We may show that the result also holds when I0 is nonempty by repeating the above argument and applying Lemma B.2," with no accompanying calculation. This is a load-bearing gap. Lemma 5.2 supplies the uniform moment bound (5.11) that is used in Section 5.3.1 to pass from mean empirical measures to ergodic occupation measures of the limiting diffusion, and hence to prove the lower bound (5.10) of Theorem 3.3. Since Assumption 2.1 only requires gamma_d>0, the case I0 nonempty is allowed by the theorem's hypotheses. The omitted case is exactly where the modified priority policy of Definition 4.1 and the special Lyapunov terms for I0 in (4.17) are needed; for i in I0 the abandonment term gamma_i q_i vanishes, so the estimate (B.20) for the polynomial part over arbitrary policies does not follow from the given argument. The sentence "repeating the above argument" does not constitute a proof, and no analogue of (B.23) is displayed for I0 nonempty.
- [Section 5.3.1, Theorem 5.3 and proof of (5.10)] Theorem 5.3 is stated for any sequence of policies satisfying (5.11), but the only mechanism in the paper for verifying (5.11) in the lower-bound argument is Lemma 5.2. Consequently the gap described above also invalidates Theorem 5.3 for sequences of policies when zero-abandonment classes are present. The proof of (5.10) takes an arbitrary sequence with sup_n J_hat(X_hat^n(0), z_n) < infinity, applies Lemma 5.2 and Theorem 5.3, and concludes that the limit of the mean empirical measures is in G. Without a complete Lemma 5.2, the lower bound, and hence the equality in Theorem 3.3, is not established in the parameter region I0 nonempty. The authors should either supply the missing calculation or state Theorem 3.3 under the stronger assumption gamma_i>0 for all i and discuss what fails in the general case.
minor comments (5)
- [Assumption 3.2(ii), equation (3.10)] The bounded mean residual life condition is written as a displayed quotient whose denominator 1-F(t) can be zero when the distribution has bounded support; please state explicitly that the inequality is required only where the denominator is positive, or interpret the condition through the usual limiting convention.
- [Definition 4.1] The formula for the modified priority policy uses the denominator sum_{i in I0} rho_i; when I0 is empty this expression is undefined. Please add a convention, for example that the first block of the definition is vacuous when I0 is empty.
- [Appendix B, around (B.16)] There is a duplicated phrase "by by Assumptions 2.1 and 2.2" in the sentence following (B.16); please correct the typographical error.
- [Lemma 5.5] The proof of Lemma 5.5 is delegated to [5, Lemma 7.2] with the sentence "the proof of this lemma is the same as that of Lemma 7.2 in [5]." Given that the present model has renewal age processes and compound-Poisson jumps, the transfer is not completely immediate; please spell out how the age-process terms and the jump operator are handled, or state which estimates in Sections 5.3.1 and 4 make the proof identical.
- [Section 1.2, Notation] The notation O(g) is used both for a function space and for a generic member of that space; this can confuse an inequality such as "= O(1/sqrt(n))(||x||+||q||)". It would be clearer to write explicit constants or use a distinct symbol for the space.
Circularity Check
No circular derivation: the ergodic and discounted asymptotic-optimality theorems do not reduce by construction to their inputs; the load-bearing same-author citations are independent structural results, and the only flagged gap (Lemma 5.2 I0 case) is an omitted proof, not circularity.
full rationale
The derivation chain is not circular. The FCLT and weak convergence (Theorem 3.1) are proved in Appendix A from Assumptions 2.1 and 2.2; the limiting controlled process (3.3), (3.4) is the weak limit of the queueing dynamics, not an input. The optimal-control theory for this limit is taken from the same-authors companion paper [17] and from [24], but those are general structural results for controlled jump diffusions whose hypotheses (e.g., E[(d1)^(m+1)] and exponential ergodicity via Proposition 4.1) are verified here; they do not assume the queueing asymptotic-optimality theorem. The discounted result (Theorem 3.2) is proved by a standard Atar-Mandelbaum-Reiman lower/upper bound argument with the moment estimate of Lemma 5.1 and the HJB characterization imported from [17]; no fitted quantity is renamed as a prediction. The ergodic result (Theorem 3.3) uses Lemma 5.2 for uniform moment bounds and Theorem 5.3 to characterize limits of mean empirical measures as ergodic occupation measures; the upper bound uses epsilon-optimal controls from [17]. None of these steps equates the target value function or optimal cost with an input by construction. The proof of Lemma 5.2 in Appendix B explicitly proves only the I0-empty case and then states: 'We may show that the result also holds when I0 is nonempty by repeating the above argument and applying Lemma B.2.' This is an omitted proof or rigor gap affecting the completeness of the ergodic lower bound for a legitimate case, but it is not circularity: the claimed bound is not assumed as an input. The same-author citations are load-bearing but independent; under the stated rules they do not raise the circularity score.
Assumptions & free parameters
free parameters (1)
- running cost exponent m =
m > 1 for the ergodic theorem; m >= 1 for the discounted theorem
assumptions (5)
- domain assumption Halfin-Whitt scaling of parameters (Assumption 2.1)
- domain assumption Exponentially distributed up times and scaled down times (Assumption 2.2)
- domain assumption Moment and mean-residual-life conditions (Assumptions 3.1 and 3.2)
- standard math Foster-Lyapunov and Harris recurrence criteria of Meyn-Tweedie [20, Theorem 4.2]
- domain assumption Known ergodic-control theory for the limiting jump diffusion (Theorems 5.1 and 5.2 from [17])
Cite this review
Pith. "Pith review of Optimal scheduling of critically loaded multiclass GI/M/n+M queues in an alternating renewal environment." pith.science (2026). https://pith.science/paper/DYBPAST6
@misc{pith2026190806329,
author = {Pith},
title = {Pith review of: Optimal scheduling of critically loaded multiclass GI/M/n+M queues in an alternating renewal environment},
year = {2026},
howpublished = {\url{https://pith.science/paper/DYBPAST6}},
note = {Machine review of arXiv:1908.06329}
}
read the original abstract
In this paper, we study optimal control problems for multiclass GI/M/n+M queues in an alternating renewal (up-down) random environment in the Halfin-Whitt regime. Assuming that the downtimes are asymptotically negligible and only the service processes are affected, we show that the limits of the diffusion-scaled state processes under non-anticipative, preemptive, work-conserving scheduling policies, are controlled jump diffusions driven by a compound Poisson jump process. We establish the asymptotic optimality of the infinite-horizon discounted and long-run average (ergodic) problems for the queueing dynamics. Since the process counting the number of customers in each class is not Markov, the usual martingale arguments for convergence of mean empirical measures cannot be applied. We surmount this obstacle by demonstrating the convergence of the generators of an augmented Markovian model which incorporates the age processes of the renewal interarrival times and downtimes. We also establish long-run average moment bounds of the diffusion-scaled queueing processes under some (modified) priority scheduling policies. This is accomplished via Foster-Lyapunov equations for the augmented Markovian model.
Reference graph
Works this paper leans on
-
[17]
Ergodic control of diffusions with compound Poisson jumps under a general structural hypothesis
A. Arapostathis, G. Pang, and Y. Zheng, Ergodic control of diffusions with compound Poisson jumps und er a gen- eral structural hypothesis, ArXiv e-prints 1908.01068 (2019), available at https://arxiv.org/abs/1908.01068
work page Pith review arXiv 2019
-
[1]
R. Atar, A. Mandelbaum, and M. I. Reiman, Scheduling a multi class queue with many exponential server s: asymptotic optimality in heavy traffic , Ann. Appl. Probab. 14 (2004), no. 3, 1084–1134. MR 2071417
work page 2004
-
[2]
R. Atar, Scheduling control for queueing systems with many servers: asymptotic optimality in heavy traffic , Ann. Appl. Probab. 15 (2005), no. 4, 2606–2650. MR 2187306
work page 2005
-
[3]
R. Atar, A. Mandelbaum, and G. Shaikhet, Simplified control problems for multiclass many-server que ueing systems, Math. Oper. Res. 34 (2009), no. 4, 795–812. MR 2573496
work page 2009
-
[4]
A. Arapostathis, A. Biswas, and G. Pang, Ergodic control of multi-class M/M/N + M queues in the Halfin-Whitt regime, Ann. Appl. Probab. 25 (2015), no. 6, 3511–3570. MR 3404643
work page 2015
-
[5]
A. Arapostathis and G. Pang, Infinite-horizon average optimality of the N-network in the Halfin-Whitt regime , Math. Oper. Res. 43 (2018), no. 3, 838–866. MR 3846075
work page 2018
-
[6]
A. Arapostathis and G. Pang, Infinite horizon asymptotic average optimality for large-s cale parallel server net- works, Stochastic Process. Appl. 129 (2019), no. 1, 283–322. MR 3906999
work page 2019
-
[7]
A. Budhiraja, A. Ghosh, and X. Liu, Scheduling control for Markov-modulated single-server mu lticlass queueing systems in heavy traffic , Queueing Syst. 78 (2014), no. 1, 57–97. MR 3238008
work page 2014
Show all 31 references
-
[8]
Kumar, M
R. Kumar, M. E. Lewis, and H. Topaloglu, Dynamic service rate control for a single-server queue with Markov- modulated arrivals, Naval Res. Logist. 60 (2013), no. 8, 661–677. MR 3146992
2013
-
[9]
L. Xia, Q. He, and A. S. Alfa, Optimal control of state-dependent service rates in a MAP/M /1 queue , IEEE Trans. Automat. Control 62 (2017), no. 10, 4965–4979. MR 3708873
2017
-
[10]
Arapostathis, A
A. Arapostathis, A. Das, G. Pang, and Y. Zheng, Optimal control of Markov-modulated multiclass many-serv er queues, Stochastic Systems 9 (2019), no. 2, 155–181
2019
-
[11]
H. M. Jansen, M. Mandjes, K. De Turck, and S. Wittevronge l, Diffusion limits for networks of Markov-modulated infinite-server queues , ArXiv e-prints 1712.04251 (2017), available at https://arxiv.org/abs/1712.04251
2017 arXiv
-
[12]
Pang and W
G. Pang and W. Whitt, Service interruptions in large-scale service systems , Management Science 55 (2009), no. 9, 1499–1512
2009
-
[13]
Pang and W
G. Pang and W. Whitt, Heavy-traffic limits for many-server queues with service int erruptions, Queueing Syst. 61 (2009), no. 2-3, 167–202. MR 2485887
2009
-
[14]
H. Lu, G. Pang, and Y. Zhou, G/GI/N (+GI) queues with service interruptions in the Halfin-Whitt regim e, Math. Methods Oper. Res. 83 (2016), no. 1, 127–160. MR 3464192
2016
-
[15]
Lu and G
H. Lu and G. Pang, Heavy-traffic limits for an infinite-server fork-join queuei ng system with dependent and disruptive services , Queueing Syst. 85 (2017), no. 1-2, 67–115. MR 3604118
2017
-
[16]
Pang and Y
G. Pang and Y. Zhou, G/G/ ∞ queues with renewal alternating interruptions , Adv. in Appl. Probab. 48 (2016), no. 3, 812–831. MR 3568893
2016
-
[18]
R. Atar, C. Giat, and N. Shimkin, On the asymptotic optimality of the cµ/θ rule under ergodic cost , Queueing Syst. 67 (2011), no. 2, 127–144. MR 2771197
2011
-
[19]
Konstantopoulos and G
T. Konstantopoulos and G. Last, On the use of Lyapunov function methods in renewal theory , Stochastic Process. Appl. 79 (1999), no. 1, 165–178. MR 1670534
1999
-
[20]
S. P. Meyn and R. L. Tweedie, Stability of Markovian processes. III. Foster-Lyapunov cr iteria for continuous-time processes, Adv. in Appl. Probab. 25 (1993), no. 3, 518–548. MR 1234295 32 ARI ARAPOSTATHIS, GUODONG PANG, AND YI ZHENG
1993
-
[21]
Billingsley, Convergence of probability measures, Second, Wiley Series in Probability and Statistics: Proba bility and Statistics, John Wiley & Sons, Inc., New York, 1999
P. Billingsley, Convergence of probability measures, Second, Wiley Series in Probability and Statistics: Proba bility and Statistics, John Wiley & Sons, Inc., New York, 1999. A Wil ey-Interscience Publication. MR 1700749
1999
-
[22]
Whitt, Stochastic-process limits, Springer Series in Operations Research, Springer-Verlag , New York, 2002
W. Whitt, Stochastic-process limits, Springer Series in Operations Research, Springer-Verlag , New York, 2002. An introduction to stochastic-process limits and their app lication to queues. MR 1876437
2002
-
[23]
J. G. Dai, On positive Harris recurrence of multiclass queueing netwo rks: a unified approach via fluid limit models , Ann. Appl. Probab. 5 (1995), no. 1, 49–77. MR 1325041
1995
-
[24]
Arapostathis, G
A. Arapostathis, G. Pang, and N. Sandri´ c, Ergodicity of a L´ evy-driven SDE arising from multiclass ma ny-server queues, Ann. Appl. Probab. 29 (2019), no. 2, 1070–1126. MR 3910024
2019
-
[25]
Arapostathis, H
A. Arapostathis, H. Hmedi, G. Pang, and N. Sandri´ c, Uniform polynomial rates of convergence for a class of L´ evy-driven controlled SDEs arising in multiclass many-s erver queues (G. Yin and Q. Zhang, eds.), Modeling, Stochastic Control, Optimization, and Applications. The I...
2019
-
[26]
M. H. A. Davis, Piecewise-deterministic Markov processes: a general clas s of nondiffusion stochastic models , J. Roy. Statist. Soc. Ser. B 46 (1984), no. 3, 353–388. With discussion. MR 790622
1984
-
[27]
S. M. Ross, Stochastic processes, Second, John Wiley & Sons, Inc., New York, 1996. MR 1373653
1996
-
[28]
Arapostathis, L
A. Arapostathis, L. Caffarelli, G. Pang, and Y. Zheng, Ergodic control of a class of jump diffusions with finite L´ evy measures and rough kernels, SIAM J. Control Optim. 57 (2019), no. 2, 1516–1540. MR 3942851
2019
-
[29]
E. V. Krichagina and M. I. Taksar, Diffusion approximation for GI/G/ 1 controlled queues, Queueing Systems Theory Appl. 12 (1992), no. 3-4, 333–367. MR 1200872
1992
-
[30]
G. Pang, R. Talreja, and W. Whitt, Martingale proofs of many-server heavy-traffic limits for Ma rkovian queues , Probab. Surv. 4 (2007), 193–267. MR 2368951
2007
-
[31]
D. L. Iglehart and W. Whitt, The equivalence of functional central limit theorems for co unting processes and associated partial sums , Ann. Math. Statist. 42 (1971), 1372–1378. MR 0310941
1971
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.