Scheduling jobs with unknown size distribution in a M/G/1 queue: the shifted empirical Gittins

Nicolas Gast, Bruno Gaujal and Adrien Obrecht1. Univ. Grenoble Alpes, Inria, CNRS, LIG, F-38000 Grenoble, France.2. ENS de Lyon, Lyon, France · 2026

Read Scheduling jobs with unknown size distribution in a M/G/1 queue: the shifted empirical Gittins by Nicolas Gast, Bruno Gaujal and Adrien Obrecht1. Univ. Grenoble Alpes, Inria, CNRS, LIG, F-38000 Grenoble, France.2. ENS de Lyon, Lyon, France (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-24703.txt.

Introduction

Nicolas Gast, Bruno Gaujal, and Adrien Obrecht tackle job scheduling in a single server queue. Jobs arrive as a Poisson process and their sizes follow an unknown distribution. One server switches between jobs instantly, and the goal is the lowest expected response time. The celebrated Gittins index policy is optimal when the size distribution is known. Here it is not. The scheduler must learn the indices from samples of past job sizes instead.

Gast and colleagues discretise the bounded range of job sizes. Each sample is then shifted to the nearest grid point on its right. They prove the Gittins index of this shifted empirical distribution stays close to the true one. That closeness makes the resulting index policy asymptotically optimal as the sample count grows. Numerical comparisons with rival approaches confirm the method is efficient in practice. The construction is called the shifted empirical Gittins policy.

Catalog record

CREATORNicolas Gast, Bruno Gaujal and Adrien Obrecht1. Univ. Grenoble Alpes, Inria, CNRS, LIG, F-38000 Grenoble, France.2. ENS de Lyon, Lyon, France
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE38 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.24703

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Scheduling jobs with unknown size distribution in a M/G/1 queue: the shifted empirical Gittins Nicolas Gast, Bruno Gaujal and Adrien Obrecht1. Univ. Grenoble Alpes, Inria, CNRS, LIG, F-38000 Grenoble, France.2. ENS de Lyon, Lyon, France Abstract In this paper we consider a M/G/1 queue for which we want to minimize the expected response time. We show how to compute indices from n n samples of the job size distribution such that the corresponding index policy is asymptotically optimal as n n grows. This construction is based on a discretization of the bounded support of the job size distribution and a shift of the samples to their nearest discrete point to the right. We show that the Gittins index of the empirical distribution of these shifted samples is close to the Gittins index of the original distribution. This translates to the asymptotic optimality of the corresponding index policy for minimizing the expected response time. Numerical comparison with other approaches further confirm the efficiency of our approach. 1 Introduction In this paper, we focus on the problem of scheduling jobs in a M/G/1 queue to minimize their mean response time under the following conditions. • All jobs have the same size distribution (technical conditions on the distribution will be discussed later), • jobs arrive according to a Poisson process, • jobs are executed by a single server that can switch from one job to another instantaneously. This problem has drawn a lot of interest recently for several reasons. Indeed, the solutions under different information levels on the job sizes are quite elegant and they are enlightening on what features are crucial to obtain small response times. • In the clairvoyant case (jobs announce their size when they arrive in the queue), the optimal scheduling policy is SRPT (Smallest Remaining Processing Time) (see [ 5 ] for a proof). • In the non-clairvoyant case , (the size of the job is only revealed at completion time), the optimal scheduling policy is the famous Gittins index policy (see [ 6 ] for a detailed proof) when the distribution of the job sizes is known in advance. • In this paper, we consider the non clairoyant black box case : The size of the job is only known at completion time and the distribution of the job sizes is also unknown. Our approach to solve this problem is of the “ explore then commit ” type: We first observe n samples of job sizes and infer a scheduling policy that becomes asymptotically optimal as the number of samples n goes to infinity. The main challenge comes from the fact that the empirical distribution induced by n samples is made of n atoms all this equal probability. This is quite distinct from the actual distribution of jobs when it is continuous w.r.t. the Lebesgue measure. To overcome this difficulty, one may infer an empirical density from the n samples, for example using a Gaussian kernel (see [ 4 ] for example) and compute the Gittins indexes for this estimated density. Unfortunately, the special shape of the Gittins indexes is highly sensitive to the distribution and this direct approach is not very efficient, as seen in our numerical tests (Section 6 ). In this paper, we use a different approach by introducing a transformation on the samples that we call the “right shift” that is compatible with the way index policies work and this is a key ingredient in the proof of our main result, namely asymptotic optimality of the learned index policy. When finalizing this manuscript, we found that the paper [ 3 ] has just been published. This paper provides a convergence analysis of the empirical Gittins policy without the need to resort to a shifted index. 2 Problem description We consider jobs that arrive in an online fashion on a queue with a single processing node, with an associated execution time (denoted X_{i} for job number i ). At each given point, the processor can execute a single job at speed one. Once a job i has been executed for X_{i} units of time, it is considered finished and leaves the system. We denote by T_{i} the response time of job i , namely the difference between its completion time and its arrival time. Our goal will to minimize the expected mean response time of the jobs. We also suppose that jobs arrive following a Poisson arrival process of rate \lambda and that their size X follows a distribution \varphi . We denote by f the probability density function (PDF), when it exists, by F the cumulative distribution function (CDF) and by \bar{F} the complementary CDF ( \bar{F}:=1-F ) of the job size. The processor works at speed one and can only execute one job at a time. The job being currently executed is called the active job. The age a of a job is the total amount of time the processor has been executing the job. The set of ages of a job is partitioned into two sets, \mathcal{X}_{\mbox{\tiny Pre}} and \mathcal{X}_{\mbox{\tiny NonPre}} , where the job can be preempted and cannot be preempted, respectively. 1 Gittins Index, Gittins index policy. The Gittins index function at age x of a job with size measure \varphi and remaining probability function \bar{F} is \nu(x):=\sup_{y>x}\frac{\mathbb{P}(X\leqslant y|X>x)}{\mathbb{E}(\min(X,y)-x|X>x)}=\sup_{y>x}\frac{\int_{x}^{y}d\varphi(u)}{\int_{x}^{y}\bar{F}(u)du}. (1) The corresponding Gittins index policy works as follows: Whenever the age x of the current active job is preemptable ( x\in\mathcal{X}_{\mbox{\tiny Pre}} ), the Gittins index policy activates one job with the maximal current Gittins index. The Gittins index function is right-continuous, but may not be continuous. Note that when \varphi contains an atom (say at age x_{0} ,) then \lim_{x\to x_{0},x<x_{0}}\nu(x)=+\infty , and \lim_{x\to x_{0},x>x_{0}}\nu(x)=\nu(x_{0}) . The Gittins index policy is known to be optimal for minimizing the expected response time of the jobs when the only information available on the jobs is their ages. Several versions of this result exist in the litterature. The most recent and general proof is given in [ 6 ] . This result is very strong: for any job in the queue, the Gittins index of a job is a function that only depends on its age (and not on the other jobs, nor on the preemption set) and yet, it completely characterizes which job to schedule first in an optimal fashion. However, the indices can only be computed when the distribution \varphi is known. In this work we show how to define an approximate value of the Gittins indices while only having samples from \varphi . 2.1 Contributiuon and positioning In this paper, we propose a way to estimate the Gittins index function based on n independent job samples and show that the corresponding Gittins index policy becomes optimal when n goes to infinity. We will leverage the definition of Gittins index to construct an ad hoc estimated distribution function and ad hoc estimated indices that make the corresponding policy close to the Gittins index policy. Our approach works in two stages: we first fix the set of ages where jobs can be preempted as \mathcal{X}_{\mbox{\tiny Pre}}^{\Delta,\varepsilon}:=\{\frac{i}{\Delta}<1-\varepsilon,i\in\mathbb{N},\} , where \Delta\in\mathbb{N} is a free parameter and \varepsilon\in(0,1) . Therefore, in our first framework, the scheduling decisions are reexamined every 1/\Delta units of

Read the complete text