Dynamic Scheduling to Optimize Sojourn Time Moments and Tail Asymptotics in Queueing Systems

The optimality of shortest remaining processing time (SRPT) and its variants with respect to minimizing mean sojourn time is well known. However, higher-order statistical properties of customer sojourn times are also very important. We therefore consider alternative scheduling approaches in queueing systems with the goal of providing mean sojourn times close to those under SRPT while also providing better higher-order statistics. Our analysis includes deriving expressions for the mean, variance and tail asymptotics of the customer sojourn time distribution in these alternative queueing systems. This mathematical framework is then exploited to determine the control parameters of these alternative scheduling policies in order to optimize performance functions that combine the mean and higher-order statistics of sojourn times in a general and flexible manner. Our results show that one of the alternative scheduling policies provides the greatest flexibility with respect to optimizing these general sojourn time objective functions, and in particular can achieve the desired goal of mean sojourn times comparable to SRPT with superior higher-order statistics.

By: Yingdong Lu; Mark S. Squillante

Published in: RC23782 in 2005


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to reports@us.ibm.com .