$γ$-CounterBoost: Optimizing response time tails using job type information only
2026-06-01 • Performance
Performance
AI summaryⓘ
The authors study how to schedule jobs in a queue when only partial information about job sizes is available, specifically knowing job types but not exact arrival times. They build on a known policy called γ-Boost, which uses job size information to prioritize jobs and minimize the chance of long waits. Here, they introduce a new policy called γ-CounterBoost that works when there are two or more job types and no arrival time data. They prove that γ-CounterBoost minimizes the tail of the response time distribution better than a wide range of other scheduling methods, extending prior results that only applied to two job types.
M/G/1 queuescheduling policyresponse time tailγ-Boost policypartial job size informationjob typesNudge-M policyγ-CounterBoost policylight-tailed distribution
Authors
Nils Charlet, Benny Van Houdt
Abstract
In a recent paper the $γ$-Boost scheduling policy was shown to minimize the tail of the response time distribution in a light-tailed M/G/1-queue. This policy schedules jobs using a boosted arrival time, defined as the arrival time of a job minus its boost, where the boost of a job depends on its exact job size. The $γ$-Boost policy can also be used when only partial job size information is available, such as the type of an incoming job. In such case the boost $b_i$ of a job depends solely on its type $i$ and $γ$-Boost was shown to optimize the tail among all boost policies, where a boost policy is fully determined by the $b_i$ values. In the partial information setting $γ$-Boost relies on two types of information: job types and arrival times. This paper focuses on the problem of minimizing the tail in a light-tailed M/G/1-queue in the partial job size information setting when the scheduler only makes use of the job types and {\it does not exploit arrival times}. Prior work showed that in case of $2$ job types the so-called Nudge-$M$ policy minimizes the tail in a large class of scheduling policies. In this paper we introduce the $γ$-CounterBoost policy in the partial information setting with $d \geq 2$ job types and prove that it minimizes the tail in an even broader class of scheduling policies called Contextual CounterBoost policies. The $γ$-CounterBoost policy reduces to the Nudge-$M$ policy in case of $d=2$ job types.