Scheduling control for queueing systems with many servers: asymptotic optimality in heavy traffic

Rami Atar

REVIEW

Scheduling control for queueing systems with many servers: asymptotic optimality in heavy traffic

Rami Atar

Probability · Submitted 23 Feb 2006 · 14 references

Pith's verdict: Solid extension of the single-station result to treelike multistation systems, with a real but bounded caveat: the lower bound only covers jointly work-conserving policies.

T0 · AI review

How this review was made: An AI referee (deepseek-v4-flash) read the paper on August 28, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 2 major objections · 3 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv IDmath/0602526 (version 1)

Pith ID66XBFLNN, Pith's permanent record of this paper and its review

CitationRami Atar. "Scheduling control for queueing systems with many servers: asymptotic optimality in heavy traffic." arXiv:math/0602526 (2006). https://pith.science/paper/66XBFLNN

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

The main news: this paper proves that for treelike multistation many-server queues in the Halfin–Whitt regime, the diffusion control value V is asymptotically attained by preemptive policies, and also by explicitly constructed nonpreemptive policies. The tracking mechanism that keeps the nonpreemptive activity counts close to the diffusion feedback is genuinely new, and the treelike condition as a sufficient condition for preemptive/nonpreemptive equivalence is a real step beyond the single-station case. The four-part Theorem 2 is cleanly stated, the assumptions are explicit, and the proof strategy (tightness, large-time estimates, the K_n lemma) is coherent.

What I like: the paper is honest about what it does and does not prove. The lower bound in Theorem 2(i) is established for jointly work-conserving admissible policies, and the construction p* is within that class. The upper bounds for p* and p' are the hard part, and the estimates look believable even though several lemmas are deferred to the author's prior papers with 'proof is similar' language. That deferral is normal for this literature, and the cited papers are real, published results.

The soft spot, as your stress-test note says, is the gap between the abstract and the theorem. The abstract says 'the value function for the preemptive problem converges to V,' but the theorem only proves liminf ≥ V for jointly work-conserving policies. Arbitrary admissible preemptive policies that are not jointly work-conserving might in principle beat V, and the proof does not rule that out because the M^n term need not vanish. I think this is a scope limitation rather than an error: the theorem is precise, and the possibly suboptimal non-jointly-work-conserving policies are not the ones the paper cares about. Still, the abstract overreaches, and the discussion would be cleaner if the restriction were stated there.

A second, minor issue: the heuristic non-equivalence counterexample with nonbasic activities is explicitly attributed to a private communication and is not fully rigorous, so the necessity of the treelike condition is plausible but not proven. That is fine for a paper whose main thrust is sufficiency.

The paper deserves a serious referee and, assuming the deferred proofs check out, publication. The results are significant for applied probability and queueing theory, and the construction is genuinely useful. I would recommend accepting after the authors either soften the abstract or add a sentence clarifying that the value-function convergence is within the jointly work-conserving class. The math looks sound to me; the citation pattern is appropriate rather than inflated.

Referee report

Significance

If the result holds, it is a substantial contribution: it extends the single-station asymptotic optimality results of Atar-Mandelbaum-Reiman to multistation treelike networks, gives constructive asymptotically optimal policies, and exhibits a dimension reduction from a pre-limit state dimension of order 2I+J-1 to the diffusion state dimension I. The assumptions are stated with care, and the heuristic discussion in Section 2.7 honestly indicates why nonbasic activities break the simplification. The overall proof strategy is coherent and the reliance on previously published results is explicit, though several key lemmas (Lemma 6 and Lemma 7) are deferred with statements such as 'proof is identical' or 'proof is very similar' to [3]. The central concern is that the abstract and the discussion after Theorem 2 claim convergence of the preemptive value function and asymptotic equivalence of the two problems, whereas the theorem's lower bound is proved only within the class of jointly work-conserving preemptive policies and no matching lower bound is proved for nonpreemptive policies. This is a scope issue rather than an internal inconsistency, but it affects the central narrative.

Major objections (2)

[Section 2.6, Theorem 2(i), Lemma 7, Eq. (65)] The lower bound liminf cost >= V(x) is proved only for sequences of jointly work-conserving admissible P-SCPs. For an arbitrary admissible P-SCP, the process M^n defined in (61) need not vanish, so the extra drift term integral_0^t M^n(s) G^n(u^n(s),v^n(s)) ds in (65) is not controlled. Since Assumption 2 does not impose monotonicity of L that would rule out a beneficial effect of this drift, the proof does not exclude a non-work-conserving preemptive policy with liminf cost below V(x). Consequently, the abstract's statement that 'the value function for the preemptive problem converges to V' is not established for the preemptive problem as defined in Definition 1(i). The theorem as stated is internally precise, but the abstract and the paragraph following Theorem 2 overstate the scope; either the claims should be restricted to the jointly work-conserving class, or an additional argument must show that joint work conservation is without loss of generality for the value function.
[Section 2.6, Theorem 2(iii)-(iv), paragraph after Theorem 2] The claimed asymptotic equivalence of the preemptive and nonpreemptive versions, and the sentence that items (i), (iii) and (iv) 'establish similar consequences for the nonpreemptive problem', are not supported by the stated results. Items (iii) and (iv) are upper bounds (limsup <= V(x)) for specific constructed N-SCP sequences. They do not provide a lower bound for arbitrary admissible N-SCPs. Since N-SCPs need not be jointly work-conserving (the tracking rule (58) enforces only local work conservation), item (i) does not supply the missing lower bound. The paper therefore establishes achievability of V by nonpreemptive policies, but not that the value function of the nonpreemptive problem converges to V. This needs to be stated explicitly, or a lower bound for the nonpreemptive problem must be proved.

Minor objections (3)

[Title and front matter] The title as displayed in the arXiv source contains typographical errors ('SER VERS', 'HEA VY'); these should be corrected in any revision.
[Section 3.1, Lemma 6 and Lemma 7] The proofs of Lemma 6 and Lemma 7 are deferred with 'proof identical' and 'proof very similar' to [3]. Since these lemmas are central to Theorem 2, the paper would be easier to verify if the required adaptations were sketched, particularly the role of Proposition 2 and the treatment of Assumption 3(iii) in Lemma 7.
[Section 2.6, after Theorem 2] The sentence 'Items (i), (iii) and (iv) establish similar consequences for the nonpreemptive problem' is ambiguous because item (i) is a lower bound for jointly work-conserving preemptive policies only, not for nonpreemptive policies; please rephrase to state exactly which consequence (upper achievability versus full asymptotic optimality) is being claimed.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

In a treelike multiclass queueing system in heavy traffic, the preemptive and nonpreemptive scheduling problems share a single asymptotic value function: the value V of an associated diffusion control problem, and nonpreemptive policies…

The reading

In a multiclass queueing system with many servers, the paper proves that under a 'treelike' structural condition the optimal discounted cost of preemptive scheduling and the optimal discounted cost of nonpreemptive scheduling both converge, as the system is scaled into heavy traffic, to the same value $V(x)$: the value of an $I$-dimensional diffusion control problem. The condition, that every class–station activity is basic, forces the class–station graph to be a tree; when it holds, the apparently harder nonpreemptive problem is asymptotically equivalent to the preemptive one. The paper constructs explicit scheduling policies for both versions that asymptotically achieve $V(x)$, with the nonpreemptive construction relying on a tracking mechanism rather than direct control of activity populations. This matters because it identifies exactly when the complex, high-dimensional scheduling problem can be reduced to solving a Hamilton–Jacobi–Bellman equation, and it gives a practical route to near-optimal policies in large service systems.

What carries the argument

The argument is carried by the optimal feedback function $h^*$ for the diffusion control problem, obtained in the companion analysis as the unique solution of the Hamilton–Jacobi–Bellman equation $\mathcal{L} f + H(x,Df)-\gamma f=0$ with $H(x,p)=\inf_{u\in\mathcal{U}}[b(x,u)\cdot p+L(x,u)]$. The preemptive policy $p^*$ simply rounds the desired activity populations $n^{1/2}\check{\Psi}^n$ into integer counts, which is legitimate while the state stays near the static fluid point. The nonpreemptive policy $p'$ uses a tracking mechanism: it continuously compares the actual activity population $\hat{\Psi}^n_{ij}$ with the desired $\check{\Psi}^n_{ij}$, declares overpopulated activities blocked, and routes new work only through unblocked activities; the core difficulty is proving the deviation $J^n=\|\hat{Y}^n-\check{Y}^n\|+\|\hat{Z}^n-\check{Z}^n\|$ converges to zero on compact time intervals. The map $G$, which solves the flow-balance equations $\sum_j\psi_{ij}=\alpha_i$, $\sum_i\psi_{ij}=\beta_j$, $\psi_{ij}=0$ for nonactivities, is the algebraic object that translates state and control into activity populations and exists uniquely precisely because the class–station graph is a tree.

Extended reading notes

Core claim

On the paper's own terms, the central claim is Theorem 2. Under Assumptions 1–3 (treelike all-basic structure, continuity and growth of the cost, and either a structural or boundedness condition on the model), with initial conditions $n^{-1/2}(X^{0,n}-nx^*)\to x$: (i) every jointly work-conserving admissible preemptive policy has limiting cost at least $V(x)$; (ii) the constructed preemptive policy $p^*$ has limiting cost at most $V(x)$; (iii) the constructed nonpreemptive policy $p'$ also has limiting cost at most $V(x)$ when the optimal feedback $h^*$ is locally Hölder away from the hyperplane $e\cdot\xi=0$; and (iv) under convexity of $L$ in the control variable, a sequence of nonpreemptive policies $p''$ obtained by smoothing $h^*$ achieves the same bound without the Hölder condition. Therefore both the preemptive and nonpreemptive value functions converge to $V$, the nonpreemptive problem is asymptotically equivalent to the preemptive problem, and asymptotically optimal nonpreemptive policies exist in treelike systems.

Load-bearing premise

The load-bearing premise is Assumption 1: every class–station activity is basic, which forces the class–station graph to be a tree; if even one activity carries only $O(\sqrt{n})$ customers, the tracking mechanism cannot change its population in $o(1)$ time and the preemptive and nonpreemptive limits are expected to differ.

Editorial extensions

If this is right

The diffusion control problem is the correct asymptotic description of both scheduling versions in treelike systems, so optimal policy design can be done on the $I$-dimensional diffusion level rather than the original queueing system.
Because nonpreemptive policies can be built from the HJB feedback function, service interruptions are not needed for asymptotic optimality in treelike systems.
The dimension reduction is from $2I+J-1$ (the Markovian nonpreemptive state) to $I$, the dimension of the HJB equation, making numerical solution feasible in cases where the original problem would not be.
If the cost is convex in the control, the nonpreemptive construction works by smoothing the feedback function, so the local Hölder condition on $h^*$ can be bypassed in that case.
In systems with nonbasic activities the equivalence is not expected: the preemptive limit is simpler, while the nonpreemptive limit can be different, as the two-station example in the paper illustrates.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The lower bound is proved only for jointly work-conserving preemptive policies; if a non-work-conserving preemptive policy could idle servers strategically to reduce cost, the true preemptive value would be below $V$, which would make the policy class part of the result rather than a technical convenience.
The tracking mechanism should transfer to finite-server systems with general renewal arrivals and state-dependent costs whose primitives satisfy a functional central limit theorem and moment bounds, because the proof uses only those ingredients plus the tree structure.
One testable engineering extension is to replace the idealized instantaneous routing by small but nonzero transfer times; the theorem suggests the performance gap should vanish as transfer times shrink relative to $n^{-1/2}$ fluctuations, a statement not proved here.

Original abstract

A multiclass queueing system is considered, with heterogeneous service stations, each consisting of many servers with identical capabilities. An optimal control problem is formulated, where the control corresponds to scheduling and routing, and the cost is a cumulative discounted functional of the system's state. We examine two versions of the problem: ``nonpreemptive,'' where service is uninterruptible, and ``preemptive,'' where service to a customer can be interrupted and then resumed, possibly at a different station. We study the problem in the asymptotic heavy traffic regime proposed by Halfin and Whitt, in which the arrival rates and the number of servers at each station grow without bound. The two versions of the problem are not, in general, asymptotically equivalent in this regime, with the preemptive version showing an asymptotic behavior that is, in a sense, much simpler. Under appropriate assumptions on the structure of the system we show: (i) The value function for the preemptive problem converges to $V$, the value of a related diffusion control problem. (ii) The two versions of the problem are asymptotically equivalent, and in particular nonpreemptive policies can be constructed that asymptotically achieve the value $V$. The construction of these policies is based on a Hamilton--Jacobi--Bellman equation associated with $V$.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 6,395 input tokens.

What the abstract itself states, as probabilities: claims first 0.03 · states limitation 0.68 · human participants 0.02 · controlled comparison 0.11 · randomized assignment 0.01 · states quantitative result 0.08 · compares with prior results 0.31 · mentions code or data availability 0.01.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

A multiclass queueing system is considered, with heterogeneous service stations, each consisting of many servers with identical capabilities. An optimal control problem is formulated, where the control corresponds to scheduling and routing, and the cost is a cumulative discounted functional of the system's state. We examine two versions of the problem: ``nonpreemptive,'' where service is uninterruptible, and ``preemptive,'' where service to a customer can be interrupted and then resumed, possibly at a different station. We study the problem in the asymptotic heavy traffic regime proposed by Halfin and Whitt, in which the arrival rates and the number of servers at each station grow without bound. The two versions of the problem are not, in general, asymptotically equivalent in this regime, with the preemptive version showing an asymptotic behavior that is, in a sense, much simpler. Under appropriate assumptions on the structure of the system we show: (i) The value function for the preemptive problem converges to $V$, the value of a related diffusion control problem. (ii) The two versions of the problem are asymptotically equivalent, and in particular nonpreemptive policies can be constructed that asymptotically achieve the value $V$. The construction of these policies is based on a Hamilton--Jacobi--Bellman equation associated with $V$.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	A multiclass queueing system is considered, with heterogeneous service stations, each consisting of many servers with identical capabilities.	background 0.98	0.13	0.02	asserted 0.98
s1	An optimal control problem is formulated, where the control corresponds to scheduling and routing, and the cost is a cumulative discounted functional of the system's state.	contribution 0.39	0.79	0.03	asserted 0.98
s2	We examine two versions of the problem: ``nonpreemptive,'' where service is uninterruptible, and ``preemptive,'' where service to a customer can be interrupted and then resumed, possibly at a different station.	background 0.43	0.35	0.03	asserted 0.90
s3	We study the problem in the asymptotic heavy traffic regime proposed by Halfin and Whitt, in which the arrival rates and the number of servers at each station grow without bound.	method 0.46	0.28	0.03	asserted 0.93
s4	The two versions of the problem are not, in general, asymptotically equivalent in this regime, with the preemptive version showing an asymptotic behavior that is, in a sense, much simpler.	result 0.96	0.74	0.14	asserted 0.98
s5	Under appropriate assumptions on the structure of the system we show: (i) The value function for the preemptive problem converges to $V$, the value of a related diffusion control problem.	result 0.99	0.93	0.24	asserted 1.00
s6	(ii) The two versions of the problem are asymptotically equivalent, and in particular nonpreemptive policies can be constructed that asymptotically achieve the value $V$.	result 0.99	0.93	0.65	asserted 1.00
s7	The construction of these policies is based on a Hamilton--Jacobi--Bellman equation associated with $V$.	method 0.98	0.89	0.07	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures

**Figure 1.** (a) A system with four classes and three stations. (b) The corresponding graph T

**Figure 2.** An example with three activities

**Figure 3.** (a) A class-1 customer waiting in the queue, no free servers in station A and one free server in station B. (b) A class-2 customer moved from station A to station B and the class-1 customer moved from the queue to station A. cost on average. The argument is valid if µ2A ≤ max(µ1A, µ2B). Arguing by coupling and assuming the system starts at the described state as time zero, let ˆπ move a class-2 customer, C2, from station A to station B and let it move the class-1 customer waiting in the queue, C1, into station A, until, at time τ , there is an arrival or a service in one of the…

Figures reproduced from arXiv:math/0602526 by the authors.

References

Works cited (14)

[3]

Atar, R., Mandelbaum, A. and Reiman, M. (2004). Scheduling a multi-class queue with many exponential servers: Asymptotic optimalit y in heavy-traﬃc. Ann. Appl. Probab. 14 1084–1134. MR2071417

View on Pith 2004
[1]

Ata, B. and Kumar, S. (2005). Heavy traﬃc analysis of open processing networks with complete resource pooling: Asymptotic optimality of d iscrete review policies. Ann. Appl. Probab. 15 331–391. MR2115046

View on Pith 2005
[2]

Atar, R. (2005). A diﬀusion model of scheduling control in queueing s ystems with many servers. Ann. Appl. Probab. 15 820–852. MR2114991

View on Pith 2005
[4]

Bell, S. L. and Williams, R. J. (2001). Dynamic scheduling of a system with two parallel servers in heavy traﬃc with resource pooling: A symptotic opti- mality of a threshold policy. Ann. Appl. Probab. 11 608–649. MR1865018

View on Pith 2001
[5]

Billingsley, P. (1999). Convergence of Probability Measures, 2nd ed. Wiley, New York. MR1700749

View on Pith 1999
[6]

Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes. Characterization and Convergence. Wiley, New York. MR838085

View on Pith 1986
[7]

Gans, N., Koole, G. and Mandelbaum, A. (2003). Telephone call centers: Tu- torial, review and research prospects. Manufacturing and Service Operations Management 5 79–141

View on Pith 2003
[8]

Halfin, S. and Whitt, W. (1981). Heavy-traﬃc limits for queues with many exponential servers. Oper. Res. 29 567–588. MR629195

View on Pith 1981
[9]

Harrison, J. M. (2000). Brownian models of open processing networks: Canon - ical representation of workload. Ann. Appl. Probab. 10 75–103. MR1765204

View on Pith 2000
[10]

Harrison, J. M. and L´opez, M. J. (1999). Heavy traﬃc resource pooling in parallel-server systems. Queueing Systems Theory Appl. 33 339–368. MR1742575

View on Pith 1999
[11]

Karatzas, I. and Shreve, S. E. (1991). Brownian Motion and Stochastic Cal- culus, 2nd ed. Springer, New York. MR1121940

View on Pith 1991
[12]

Mandelbaum, A. and Reiman, M. I. Private communication

View on Pith
[13]

Mandelbaum, A. and Stolyar, A. L. (2004). Scheduling ﬂexible servers with convex delay costs: Heavy traﬃc optimality of the generaliz ed cµ rule. Oper. Res. 52 836–855. MR2104141

View on Pith 2004
[14]

Williams, R. J. (2000). On dynamic scheduling of a parallel server system wi th complete resource pooling. In Analysis of Communication Networks : Call Centres, Traﬃc and Performance . Fields Inst. Commun. 28 49–71. Amer. Math. Soc., Providence, RI. MR1788708 Department of Electrical Engineering Technion–Israel Institute of Technology Haifa 32000 Israel e...

View on Pith 2000

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [3]

Atar, R., Mandelbaum, A. and Reiman, M. (2004). Scheduling a multi-class queue with many exponential servers: Asymptotic optimalit y in heavy-traﬃc. Ann. Appl. Probab. 14 1084–1134. MR2071417

View on Pith 2004

[2] [1]

Ata, B. and Kumar, S. (2005). Heavy traﬃc analysis of open processing networks with complete resource pooling: Asymptotic optimality of d iscrete review policies. Ann. Appl. Probab. 15 331–391. MR2115046

View on Pith 2005

[3] [2]

Atar, R. (2005). A diﬀusion model of scheduling control in queueing s ystems with many servers. Ann. Appl. Probab. 15 820–852. MR2114991

View on Pith 2005

[4] [4]

Bell, S. L. and Williams, R. J. (2001). Dynamic scheduling of a system with two parallel servers in heavy traﬃc with resource pooling: A symptotic opti- mality of a threshold policy. Ann. Appl. Probab. 11 608–649. MR1865018

View on Pith 2001

[5] [5]

Billingsley, P. (1999). Convergence of Probability Measures, 2nd ed. Wiley, New York. MR1700749

View on Pith 1999

[6] [6]

Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes. Characterization and Convergence. Wiley, New York. MR838085

View on Pith 1986

[7] [7]

Gans, N., Koole, G. and Mandelbaum, A. (2003). Telephone call centers: Tu- torial, review and research prospects. Manufacturing and Service Operations Management 5 79–141

View on Pith 2003

[8] [8]

Halfin, S. and Whitt, W. (1981). Heavy-traﬃc limits for queues with many exponential servers. Oper. Res. 29 567–588. MR629195

View on Pith 1981

[9] [9]

Harrison, J. M. (2000). Brownian models of open processing networks: Canon - ical representation of workload. Ann. Appl. Probab. 10 75–103. MR1765204

View on Pith 2000

[10] [10]

Harrison, J. M. and L´opez, M. J. (1999). Heavy traﬃc resource pooling in parallel-server systems. Queueing Systems Theory Appl. 33 339–368. MR1742575

View on Pith 1999

[11] [11]

Karatzas, I. and Shreve, S. E. (1991). Brownian Motion and Stochastic Cal- culus, 2nd ed. Springer, New York. MR1121940

View on Pith 1991

[12] [12]

Mandelbaum, A. and Reiman, M. I. Private communication

View on Pith

[13] [13]

Mandelbaum, A. and Stolyar, A. L. (2004). Scheduling ﬂexible servers with convex delay costs: Heavy traﬃc optimality of the generaliz ed cµ rule. Oper. Res. 52 836–855. MR2104141

View on Pith 2004

[14] [14]

Williams, R. J. (2000). On dynamic scheduling of a parallel server system wi th complete resource pooling. In Analysis of Communication Networks : Call Centres, Traﬃc and Performance . Fields Inst. Commun. 28 49–71. Amer. Math. Soc., Providence, RI. MR1788708 Department of Electrical Engineering Technion–Israel Institute of Technology Haifa 32000 Israel e...

View on Pith 2000