Scheduling to Minimize General Functions of the Mean and Variance of Sojourn Times in Queueing Systems

The optimality of shortest remaining processing time (SRPT) and its variants with respect to minimizing mean sojourn times are well known. Some recent studies have further argued that SRPT does not unfairly penalize large customers in order to benefit small customers, and thus have proposed the use of SRPT to improve performance in computer systems under various applications such as Web sites and databases. On the other hand, the variance of customer sojourn times is another important property of performance in these systems. We therefore consider alternative approaches to scheduling customers in queueing systems with the goal of providing mean sojourn times relatively close to those obtained under SRPT while also providing better variance properties. Our analysis includes deriving expressions for the mean and variance of customer sojourn times in these queueing systems, as well as for the parameters of the alternative scheduling policies. These results illustrate and quantify a fundamental performance tradeoff between decreasing the mean sojourn time and increasing the sojourn time variance, and vice versa. Our mathematical framework is then exploited to determine scheduling policies and their control parameters in order to optimize general functions of the mean and variance of sojourn times in queueing systems.

By: Yingdong Lu; Mark S. Squillante

Published in: RC23415 in 2004

LIMITED DISTRIBUTION NOTICE:

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.

rc23415.pdf

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