Yingdong Lu
Abstract
It is well known that scheduling the service of customers according to the shortest remaining processing time (SRPT) policy is optimal with respect to minimizing the mean sojourn time of customers. Recent studies have further argued that SRPT does not unfairly penalize large customers in order to benefit small customers, and therefore these studies propose the use of SRPT to improve performance in various applications. However, as Schrage and Miller point out [10], the SRPT policy can raise several difficulties for a number of important reasons. Such difficulties can arise from the inability to accurately predict service times, or the complicated nature of implementing the preemptive aspect of the SRPT policy which requires keeping track of the remaining service times of all waiting customers as well as of the customer in service. Normally, preemption also incurs additional costs. and thus one might want to avoid the preemption of customers in service whose remaining service time is not much larger than that of a new arrival.
- P. Ansell, K. Glazebrook, I. Mitrani, J. Nino-Mora. A semidefinite programming approach to the optimal control of a single-server queueing system with imposed second moment constraints. J. Op. Res. Soc., 50(7):765--773, 1999.Google Scholar
Cross Ref
- E. G. Coffman, Jr., L. Kleinrock. Computer scheduling methods and their countermeasures. In Proc. AFIPS Spring Joint Computer Conf., 32:11--21, April 1968.Google ScholarDigital Library
- E. G. Coffman, Jr., I. H. Mitrani. A characterization of waiting-time performance achievable by single-server queues. Op. Res., 28(3):810--821, 1980.Google ScholarCross Ref
- M. Dacre, K. Glazebrook, J. Nino-Mora. The achievable region approach to the optimal control of stochastic systems. With discussion. J. Royal Stat. Soc., 61(4):747--791, 1999.Google ScholarCross Ref
- L. L. Fong, M. S. Squillante. Time-Function Scheduling: A general approach to controllable resource management. In Proc. Symp. Op. Sys. Prin., p. 230, Dec. 1995. Google ScholarDigital Library
- L. Kleinrock. Communication Nets: Stochastic Message Flow and Delay. McGraw-Hill, 1964. Google ScholarDigital Library
- L. Kleinrock. Queueing Systems Volume II: Computer Applications. John Wiley and Sons, 1976.Google Scholar
- Y. Lu, M. S. Squillante. Dynamic scheduling to minimize general functions of sojourn time moments in queueing systems. Tech. Rep. RC 23415, IBM Res. Div., Nov. 2004.Google Scholar
- R. D. Nelson. Invertible mapping of waiting times in a M/G/l queue with linear priorities. Unpublished Draft, June 1993.Google Scholar
- L. E. Schrage, L. W. Miller. The queue M/G/l with the shortest remaining processing time discipline. Op. Res., 14(4):670--684, 1966.Google ScholarDigital Library
- M. S. Squillante, L. L. Fong, S. Liu, S. K. Ryan. A control study of time-function scheduling: Part I. Tech. Rep. RC 19765, IBM Res. Div., Sept. 1994.Google Scholar
Index Terms
- Dynamic scheduling to optimize utility functions of sojourn time moments in queueing systems
Recommendations
Sojourn time approximations in queueing networks with feedback
This paper is motivated by the response-time analysis of distributed information systems, where transactions are handled by a sequence of front-end server and back-end server actions. We study sojourn times in an open queueing network with a single ...
Sojourn times in polling systems with various service disciplines
We consider a polling system of N queues Q"1,...,Q"N, cyclically visited by a single server. Customers arrive at these queues according to independent Poisson processes, requiring generally distributed service times. When the server visits Q"i, i=1,...,...
Sojourn time analysis for a cyclic-service tandem queueing model with general decrementing service
A sojourn time analysis is provided for a cyclic-service tandem queue with general decrementing service which operates as follows: starting once a service of queue 1 in the first stage, a single server continues serving messages in queue 1 until either ...
Comments