Threshold Policies Extend to Three-Server Queues

Queueing control has a simple intuition that is hard to prove once heterogeneous servers interact: use the fast server when possible, and send work to slower servers only after congestion is high enough. Lin and Kumar’s 1984 model with one fast and one slow server has that threshold structure. This paper proves the corresponding result for the next case, a system with one fast server and two identical slow servers, where the multi-slow-server extension had remained open.

The result is theoretical rather than computational. The authors study a nonpreemptive queue with Poisson arrivals, exponential service, one fast server, and two slower servers with equal rates. The system state can be represented as $(q,z,y)$, where $q$ is the queue length, $z \in \{0,1\}$ records whether the fast server is busy, and $y \in \{0,1,2\}$ records how many slow servers are busy. The control question is when an arriving or waiting job should be assigned to an idle slow server rather than held for the fast server.

Core Contribution

The paper’s main contribution is a proof that an optimal policy has a threshold form in the three-server system. In practical terms, for each slow-server occupancy level, once it is optimal to route a job to a slow server at a given congestion level, it remains optimal at larger congestion levels. That monotonicity is the structural statement needed to describe the optimal policy by thresholds rather than by an arbitrary state-dependent rule.

The new ingredient is not a new queueing model; it is the proof architecture. Prior two-server arguments did not carry over cleanly because two slow servers introduce an additional dimension: the proof must compare states with different numbers of busy slow servers while preserving the total population structure. The paper addresses this by strengthening the value-iteration cone with an extra convexity condition across the number of busy slow servers.

Technical Approach

The authors reduce the original control problem to a simplified post-decision state, essentially tracking the total population visible to the fast server together with the number of busy slow servers. They first show that the fast server can be treated by a reduction lemma: an optimal policy never sends a customer to an idle slow server while the fast server is idle and work is available. That removes a source of avoidable heterogeneity before the threshold argument begins.

The proof then defines a cone of value functions satisfying inequalities labeled (K1)–(K6). These inequalities encode monotonicity in total population, convexity-type relations, and the additional condition needed for the two-slow-server case. The central step is to show that the dynamic-programming operator preserves this cone. The visual proof pages show the most mechanical part of that argument: the authors enumerate possible minimizers $a(x,y) \in \{0,1,2\}$ and verify case by case that the transformed function $\bar f$ still satisfies inequalities such as

This is where the three-server setting becomes visibly more complex than the two-server setting. For $y=0$, the proof checks multiple tuples of minimizers, including cases such as $(0,0,1,2)$, $(0,1,2,2)$, and $(2,2,2,2)$; for $y=1$, fewer boundary cases remain because two slow servers are already busy. The value of the paper is partly in making that finite verification explicit rather than hiding it behind an informal monotonicity claim.

Results and Analysis

The main theorem proves optimality of a threshold policy for the average-cost problem. The route to average cost is standard but detailed: the authors first work with discounted costs, prove cone preservation for the discounted dynamic program, then pass to an average-cost optimality equation using Sennott’s framework. The appendix verifies the needed recurrence, Lyapunov, and bounded-difference assumptions. Lemma 7 then lifts the optimal policy from the reduced state space back to the original state space, showing that no admissible original policy can beat the reduced threshold policy in long-run average holding cost.

There are no simulations, charts, or numerical experiments. That is appropriate for the claim: the paper is proving a structural theorem, not estimating performance. The evidence is therefore only as strong as the mathematical verification. On that axis, the paper is careful. It exposes the finite case checks, cites the average-cost machinery used for the limiting argument, and reports that three key lemmas were also checked in Lean 4.

A separate appendix documents how GPT-5.5 Pro contributed to the proof search. The authors say the model produced the main proof ideas, including strengthening Koole’s value-iteration cone with convexity in the number of busy slow servers along fixed total population. They also document errors: early versions contained a minor algebraic mistake and informal coupling arguments, and the authors rewrote the paper for rigor and readability. That disclosure weakens any claim that the generated text itself was reliable, but it strengthens the provenance record for the final proof: the mathematical result is presented as author-verified, with partial formal verification rather than as an unexamined model output.

Caveats

The theorem resolves one carefully chosen extension: exactly one fast server and exactly two identical slow servers. It does not prove the general many-slow-server conjecture, does not handle nonidentical slow servers, and does not provide performance gains from using the threshold representation in computation. The authors’ own GPT interaction report also makes clear that the discovery process produced flawed drafts before the final argument stabilized. The contribution is best read as a resolved base case and a possible proof template for larger systems, not as a completed theory of heterogeneous multi-server routing.