Skip to Main content Skip to Navigation
Conference papers

Control and optimization of single-server queues: the Gittins index approach revisited

Abstract : We consider the optimal scheduling problem for a single-server queue. We allow preemptions, and our purpose is to minimize the mean sojourn time. The optimal non-anticipating discipline is known to be the Gittins index policy, which, however, is de ned in an implicit way. Until now, its general behaviour in this speci c problem has been characterized only in a few special cases. In this presentation, we shed light on the properties of the Gittins index. Then we apply the properties to give as complete a characterization as possible for the Gittins index policy. It turns out that, in the static case without arrivals, the optimal policy always belongs to the family of Multi-Level-Processor-Sharing (MLPS) disciplines. For the dynamic case with Poisson arrivals (i.e. for the M/G/1 queue), the optimal policy is generally more complicated. However, we give new results that characterize the optimal policy even in this dynamic case.
Document type :
Conference papers
Complete list of metadata
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Wednesday, June 1, 2011 - 1:41:52 PM
Last modification on : Monday, January 13, 2020 - 5:28:01 PM


  • HAL Id : inria-00597565, version 1



Samuli Aalto. Control and optimization of single-server queues: the Gittins index approach revisited. NET-COOP 2010 - 4th Workshop on Network Control and Optimization, Nov 2010, Ghent, Belgium. ⟨inria-00597565⟩



Record views