Research Article
Optimal scheduling of jobs with a DHR tail in the M/G/1 queue
@INPROCEEDINGS{10.4108/ICST.VALUETOOLS2008.4335, author={Samuli Aalto and Urtzi Ayesta}, title={Optimal scheduling of jobs with a DHR tail in the M/G/1 queue}, proceedings={3rd International ICST Conference on Performance Evaluation Methodologies and Tools}, publisher={ICST}, proceedings_a={VALUETOOLS}, year={2010}, month={5}, keywords={M/G/1 scheduling mean delay Pareto distribution Gittins index}, doi={10.4108/ICST.VALUETOOLS2008.4335} }- Samuli Aalto
Urtzi Ayesta
Year: 2010
Optimal scheduling of jobs with a DHR tail in the M/G/1 queue
VALUETOOLS
ICST
DOI: 10.4108/ICST.VALUETOOLS2008.4335
Abstract
We consider the mean delay optimization in the M/G/1 queue for jobs with a service time distribution that has a tail with decreasing 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 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 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 priority to the jobs with attained service less than some fixed threshold θ. These priority jobs are served in the FCFS manner. If there are no jobs with attained service less than θ, priority is given to the job with least amount of attained service.