Maximizing Throughput in an M/G/1 Queue with Customer Abandonments

Douglas G. Down; Hayriye Ayhan; Runhua Wu

arxiv: 2606.26544 · v1 · pith:4TWF7KLL · submitted 2026-06-25 · math.OC · math.PR

Maximizing Throughput in an M/G/1 Queue with Customer Abandonments

Runhua Wu , Hayriye Ayhan , Douglas G. Down This is my paper

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel 2026-06-26 04:07 UTCgrok-4.3pith:4TWF7KLL record.json open to challenge →

classification math.OC math.PR

keywords M/G/1 queuecustomer abandonmentthroughput maximizationoptimal policySREPTErlang distributionhyperexponential distribution

0 comments

The pith

The Shortest Remaining Expected Processing Time policy maximizes the long-run average throughput in an M/G/1 queue with customer abandonments when service times are Erlang-K or hyperexponential and phases are observable.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper shows that the Shortest Remaining Expected Processing Time (SREPT) policy is optimal for maximizing throughput in a single-server queue with Poisson arrivals and exponential abandonment times. The optimality holds specifically when service times follow Erlang-K or hyperexponential distributions and the server can observe the service phase of each customer. The result is independent of the abandonment rate, meaning the policy performs best no matter how quickly customers leave. A reader would care because it gives a practical rule for server assignment that does not require knowing the abandonment rate in advance.

Core claim

When service times follow either an Erlang-K or a hyperexponential distribution and the decision maker can observe the phase of a customer's service time, the Shortest Remaining Expected Processing Time (SREPT) policy maximizes the long-run average throughput, independent of the abandonment rate.

What carries the argument

The Shortest Remaining Expected Processing Time (SREPT) policy that selects the customer with the shortest remaining expected processing time based on the observed phase.

If this is right

The policy achieves maximum throughput regardless of the rate at which customers abandon.
Optimality requires the service time distribution to be either Erlang-K or hyperexponential.
Observability of the service phase is required to implement the policy.
The result applies to the M/G/1 queue setting with exponential patience times.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Without phase observability, the optimality may not hold and a different policy could be required.
The approach might extend to other phase-type distributions if similar phase information is available.
Testing the policy in simulation with these distributions could confirm the throughput gains.

Load-bearing premise

The service times must be Erlang-K or hyperexponential and the decision maker must observe the current phase of each customer's service.

What would settle it

A simulation or calculation showing that for an Erlang-K service time with observable phases, a policy other than SREPT achieves strictly higher long-run average throughput would disprove the claim.

read the original abstract

This paper studies the problem of identifying the optimal server assignment policy in single-server queues with customer abandonment. We consider a system with Poisson arrivals and exponentially distributed patience times. We show that when service times follow either an Erlang-$K$ or a hyperexponential distribution and the decision maker can observe the phase of a customer's service time, the Shortest Remaining Expected Processing Time (SREPT) policy maximizes the long-run average throughput, independent of the abandonment rate.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

SREPT is optimal for throughput under abandonments only for Erlang-K and hyperexponential services with observable phases.

read the letter

The main thing to know is that this paper proves the Shortest Remaining Expected Processing Time policy maximizes long-run average throughput in an M/G/1 queue with Poisson arrivals and exponential patience, but only when service times are Erlang-K or hyperexponential and the server can observe the current phase of each customer. The optimality holds regardless of the abandonment rate.

What is new is the extension of earlier phase-type optimality results to include customer abandonments while keeping the policy independent of the abandonment parameter. The paper sets up the standard single-server model and uses the phase structure to derive the result for these two families.

The work is solid on its own terms. It gives a clean statement and focuses on a setting where the phase-type representation allows explicit comparison of remaining expected times. That produces a usable policy without needing to know the abandonment rate in advance.

The soft spots are exactly the ones the abstract flags. The result does not apply to general service distributions, and it requires phase observability, which is a strong assumption. Those limits are real and keep the finding from covering most practical cases. The proof likely leans on the specific Markovian structure of Erlang-K and hyperexponential distributions, so broader extensions would need different tools.

This is for researchers in stochastic scheduling who already work with phase-type services and abandonments. A reader looking for exact optimality results in that narrow slice will get something concrete. It deserves peer review because the claim is precise, the setting is standard, and the independence from the abandonment rate is a useful property even if the scope stays limited.

Referee Report

0 major / 1 minor

Summary. The manuscript claims that in an M/G/1 queue with Poisson arrivals and exponentially distributed patience times, when service times follow an Erlang-K or hyperexponential distribution and the decision maker can observe the current phase of each customer's service, the Shortest Remaining Expected Processing Time (SREPT) policy maximizes long-run average throughput; this optimality holds independently of the abandonment rate.

Significance. If the result holds under the stated conditions, it would constitute a meaningful contribution to stochastic scheduling and queueing control by identifying an optimal policy for throughput maximization in abandonment systems for a restricted but practically relevant class of phase-type distributions. The independence from the abandonment rate, if rigorously established, would be a notable strengthening of the result with potential implications for policy robustness.

minor comments (1)

The abstract would benefit from a one-sentence indication of the proof technique (e.g., sample-path comparison, dynamic programming, or index policy argument) to help readers assess the approach at a glance.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript and for recommending acceptance. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper states an optimality result for the SREPT policy restricted to Erlang-K or hyperexponential service times with observable phases. This is presented as a derived theorem under explicit distributional and observability assumptions, with no evidence of self-definitional loops, fitted inputs renamed as predictions, or load-bearing self-citations that reduce the central claim to its own inputs. The result is conditioned on the paper's own premises rather than smuggling them in via circular construction.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The claim rests on standard queueing modeling assumptions listed below; no free parameters or invented entities appear in the abstract.

axioms (3)

domain assumption Arrivals follow a Poisson process
Standard modeling choice for the M/G/1 queue stated in the abstract.
domain assumption Patience times are exponentially distributed
Given explicitly in the abstract as part of the system description.
domain assumption Service times belong to Erlang-K or hyperexponential families with observable phases
The condition required for the SREPT optimality result to hold.

pith-pipeline@v0.9.1-grok · 5602 in / 1362 out tokens · 73882 ms · 2026-06-26T04:07:55.404789+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

19 extracted references

[1]

Whittle index approach to multiserver scheduling with impatient customers and DHR service times,

Aalto, S. (2024). “Whittle index approach to multiserver scheduling with impatient customers and DHR service times,”Queueing Systems, 107:1–30

2024
[2]

On the Gittins index in the M/G/1 queue,

Aalto, S., Ayesta, U. and Righter, R. (2009). “On the Gittins index in the M/G/1 queue,”Queueing Systems63:437

2009
[3]

Dynamic control of an M/M/1 service system with adjustable arrival and service rates,

Ata, B. and Sheneorson, S. (2006). “Dynamic control of an M/M/1 service system with adjustable arrival and service rates,”Management Science, 52:1778–1791

2006
[4]

and Shimkin N

Atar R., Giat C. and Shimkin N. (2010). ”Thecµ/θrule for many-server queues with abandonment,” Operations Research, 58:1427-1439

2010
[5]

Scheduling of multi-class multi-server queueing systems with abandonments,

Ayesta, U., Jacko, P. and Novak, V. (2017). “Scheduling of multi-class multi-server queueing systems with abandonments,”Journal of Scheduling, 20:129–145. 19

2017
[6]

Kcompeting queues with customer abandonment: Optimality of a generalizedcµ- rule by the Smoothed Rate Truncation method

Bhulai, S., Blok, H., and Spieksma, F. M. (2022). “Kcompeting queues with customer abandonment: Optimality of a generalizedcµ- rule by the Smoothed Rate Truncation method”,Annals of Operations Research, 317:387–416

2022
[7]

Multiple server preemptive scheduling with impatience,

Cao, Y. (2017). “Multiple server preemptive scheduling with impatience,”Probability in the Engi- neering and Informational Sciences, 31:226–238

2017
[8]

Stochastic scheduling with abandonment: Necessary and sufficient conditions for the optimality of a strict priority policy,

Chen, G., Gayon, J., and Lemaire, P. (2022). “Stochastic scheduling with abandonment: Necessary and sufficient conditions for the optimality of a strict priority policy,”Operations Research, 71:1789- 1793

2022
[9]

SRPT scheduling discipline in many-server queues with impatient customers

Dong, J. and Ibrahim, R. (2021). “SRPT scheduling discipline in many-server queues with impatient customers”,Management Science, 67:7291-795

2021
[10]

Dynamic control of a single-server system with abandonments,

Down, D. G., Koole, G., and Lewis, M. E. (2011). “Dynamic control of a single-server system with abandonments,”Queueing Systems, 67:63–90

2011
[11]

C., Glazebrook, K., and Weber, R.Multi-armed Bandit Allocation Indices

Gittins, J. C., Glazebrook, K., and Weber, R.Multi-armed Bandit Allocation Indices. Wiley, Chich- ester, 1989

1989
[12]

SRPT for multi-server systems

Grosof, I., Scully, Z., and Harchol-Balter, M. (2018). “SRPT for multi-server systems”,Performance Evaluation, 127:154–175

2018
[13]

A survey of recent results on continuous-time Markov decision processes,

Guo, X., Hern´ andez-Lerma, O., and Prieto-Rumeau, T. (2006). “A survey of recent results on continuous-time Markov decision processes,”TOP, 14:177–261

2006
[14]

and Hern´ andez-Lerma, O.Continuous-Time Markov Decision Processes: Theory and Ap- plications, Springer, Berlin, 2009

Guo, X. and Hern´ andez-Lerma, O.Continuous-Time Markov Decision Processes: Theory and Ap- plications, Springer, Berlin, 2009

2009
[15]

Dynamic fluid-based scheduling in a multi-class abandonment queue,

Larra˜ naga, M., Ayesta, U. and Verloop, I. (2013). “Dynamic fluid-based scheduling in a multi-class abandonment queue,”Performance Evaluation, 70:841–858

2013
[16]

Puterman M L.Markov Decision Processes: Discrete Stochastic Dynamic Programming.John Wiley & Sons, 2014

2014
[17]

On extremal service disciplines in single-stage queueing systems,

Righter, R., Shanthikumar, J. G. and Yamazaki, G. (1990). “On extremal service disciplines in single-stage queueing systems,”Journal of Applied Probability, 27:409–416

1990
[18]

A proof of the optimality of the Shortest Remaining Processing Time discipline,

Schrage, L. (1968). “A proof of the optimality of the Shortest Remaining Processing Time discipline,” Operations Research, 16:687–690

1968
[19]

Simple near-optimal scheduling for the M/G/1,

Scully, Z., Harchol-Balter, M. and Scheller-Wolf, A. (2020). “Simple near-optimal scheduling for the M/G/1,”Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4:1-29. 20 Appendix Proof of Theorem 2.2 Proof.Since we setc 0 =−θ <0 andL 0 =λ+θ+µ >0, condition (i) is satisfied. Note that the reward function in our model is eitherµor 0. A...

2020

[1] [1]

Whittle index approach to multiserver scheduling with impatient customers and DHR service times,

Aalto, S. (2024). “Whittle index approach to multiserver scheduling with impatient customers and DHR service times,”Queueing Systems, 107:1–30

2024

[2] [2]

On the Gittins index in the M/G/1 queue,

Aalto, S., Ayesta, U. and Righter, R. (2009). “On the Gittins index in the M/G/1 queue,”Queueing Systems63:437

2009

[3] [3]

Dynamic control of an M/M/1 service system with adjustable arrival and service rates,

Ata, B. and Sheneorson, S. (2006). “Dynamic control of an M/M/1 service system with adjustable arrival and service rates,”Management Science, 52:1778–1791

2006

[4] [4]

and Shimkin N

Atar R., Giat C. and Shimkin N. (2010). ”Thecµ/θrule for many-server queues with abandonment,” Operations Research, 58:1427-1439

2010

[5] [5]

Scheduling of multi-class multi-server queueing systems with abandonments,

Ayesta, U., Jacko, P. and Novak, V. (2017). “Scheduling of multi-class multi-server queueing systems with abandonments,”Journal of Scheduling, 20:129–145. 19

2017

[6] [6]

Kcompeting queues with customer abandonment: Optimality of a generalizedcµ- rule by the Smoothed Rate Truncation method

Bhulai, S., Blok, H., and Spieksma, F. M. (2022). “Kcompeting queues with customer abandonment: Optimality of a generalizedcµ- rule by the Smoothed Rate Truncation method”,Annals of Operations Research, 317:387–416

2022

[7] [7]

Multiple server preemptive scheduling with impatience,

Cao, Y. (2017). “Multiple server preemptive scheduling with impatience,”Probability in the Engi- neering and Informational Sciences, 31:226–238

2017

[8] [8]

Stochastic scheduling with abandonment: Necessary and sufficient conditions for the optimality of a strict priority policy,

Chen, G., Gayon, J., and Lemaire, P. (2022). “Stochastic scheduling with abandonment: Necessary and sufficient conditions for the optimality of a strict priority policy,”Operations Research, 71:1789- 1793

2022

[9] [9]

SRPT scheduling discipline in many-server queues with impatient customers

Dong, J. and Ibrahim, R. (2021). “SRPT scheduling discipline in many-server queues with impatient customers”,Management Science, 67:7291-795

2021

[10] [10]

Dynamic control of a single-server system with abandonments,

Down, D. G., Koole, G., and Lewis, M. E. (2011). “Dynamic control of a single-server system with abandonments,”Queueing Systems, 67:63–90

2011

[11] [11]

C., Glazebrook, K., and Weber, R.Multi-armed Bandit Allocation Indices

Gittins, J. C., Glazebrook, K., and Weber, R.Multi-armed Bandit Allocation Indices. Wiley, Chich- ester, 1989

1989

[12] [12]

SRPT for multi-server systems

Grosof, I., Scully, Z., and Harchol-Balter, M. (2018). “SRPT for multi-server systems”,Performance Evaluation, 127:154–175

2018

[13] [13]

A survey of recent results on continuous-time Markov decision processes,

Guo, X., Hern´ andez-Lerma, O., and Prieto-Rumeau, T. (2006). “A survey of recent results on continuous-time Markov decision processes,”TOP, 14:177–261

2006

[14] [14]

and Hern´ andez-Lerma, O.Continuous-Time Markov Decision Processes: Theory and Ap- plications, Springer, Berlin, 2009

Guo, X. and Hern´ andez-Lerma, O.Continuous-Time Markov Decision Processes: Theory and Ap- plications, Springer, Berlin, 2009

2009

[15] [15]

Dynamic fluid-based scheduling in a multi-class abandonment queue,

Larra˜ naga, M., Ayesta, U. and Verloop, I. (2013). “Dynamic fluid-based scheduling in a multi-class abandonment queue,”Performance Evaluation, 70:841–858

2013

[16] [16]

Puterman M L.Markov Decision Processes: Discrete Stochastic Dynamic Programming.John Wiley & Sons, 2014

2014

[17] [17]

On extremal service disciplines in single-stage queueing systems,

Righter, R., Shanthikumar, J. G. and Yamazaki, G. (1990). “On extremal service disciplines in single-stage queueing systems,”Journal of Applied Probability, 27:409–416

1990

[18] [18]

A proof of the optimality of the Shortest Remaining Processing Time discipline,

Schrage, L. (1968). “A proof of the optimality of the Shortest Remaining Processing Time discipline,” Operations Research, 16:687–690

1968

[19] [19]

Simple near-optimal scheduling for the M/G/1,

Scully, Z., Harchol-Balter, M. and Scheller-Wolf, A. (2020). “Simple near-optimal scheduling for the M/G/1,”Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4:1-29. 20 Appendix Proof of Theorem 2.2 Proof.Since we setc 0 =−θ <0 andL 0 =λ+θ+µ >0, condition (i) is satisfied. Note that the reward function in our model is eitherµor 0. A...

2020