Sharp ratios of SERPT and M-SERPT to the Gittins policy for two-point job sizes
In the M/G/1 queue with unknown job sizes, the Gittins policy minimizes the mean response time, and the simpler policy M-SERPT (monotonic shortest expected remaining processing time) is known to be within a factor 5 of it. We determine the supremum of this ratio when the job size takes two values and ties in rank are broken in first-come first-served (FCFS) order. Over all two-point laws and all loads below one, the supremum of the ratio of the mean response time of M-SERPT to that of Gittins is C₂ = 1.06017342…, an algebraic number defined through the root in (0,1) of t⁵ + 4t⁴ − 20t³ + 12t² + 16t − 8. It is approached at a load of about 0.686, as the larger of the two sizes decreases to the largest value at which FCFS order is optimal, and it is not attained. For SERPT (shortest expected remaining processing time) the corresponding supremum is C₂ˢ = (7 − 2√2)/4 = 1.04289…. Both results rest on an exact formula for the excess of the mean response time over that of Gittins.
Authors
- Yitzchak Shmalo (ORCID: https://orcid.org/0000-0002-2886-3049)
Institutions
- Hebrew University of Jerusalem (IL)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-21
- DOI
- https://doi.org/10.5281/zenodo.24409477
- Primary Topic
- Advanced Queuing Theory Analysis
- Type
- preprint