Optimal scheduling of service requirements with a DHR tail in the M/G/1 queue

Samuli Aalto (1) , Urtzi Ayesta (2)

1 TKK - TKK Helsinki University of Technology
2 LAAS - Laboratoire d'analyse et d'architecture des systèmes

We consider the mean delay optimization in the M/G/1 queue for service time distributions that have a tail with decresing hazard rate (DHR). If the DHR property is valid for the whole distribution, then it is known that the Foreground-Background (FB) discipline, which gives full priority to the job with least amount of attained service, is optimal among nonanticipating scheduling disciplines. However, FB may fail to be optimal if the DHR property is valid only for the tail of the distribution. An important example is the Pareto distribution bounded away from zero. In this paper we show that for a wide class of service time distributions with a DHR tail (including the Pareto distribution), the optimal nonanticipating discipline is a combination of FCFS and FB disciplines, which gives full priority to the jobs with attained service less than some fixed threshold $\theta^*$. These priority jobs are served in the FCFS manner. If there are no jobs with attained service less than $\theta^*$, the full priority is given to the job with least amount of attained service.

Mots clés: Gittins index:M/G/1:scheduling

Domaines: Réseaux et télécommunications [cs.NI]

Samuli Aalto, Urtzi Ayesta. Optimal scheduling of service requirements with a DHR tail in the M/G/1 queue. 2007. ⟨hal-00166642⟩