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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Sharp ratios of SERPT and M-SERPT to the Gittins policy for two-point job sizes

Yitzchak Shmalo
Zenodo (CERN European Organization for Nuclear Research)
Advanced Queuing Theory Analysis
preprint

Sharp ratios of SERPT and M-SERPT to the Gittins policy for two-point job sizes

Yitzchak Shmalo
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Hebrew University of Jerusalem (IL)
Advanced Queuing Theory Analysis
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon