Queuing Systems: Lecture 4 Amedeo R. Odoni October 22, 2001 Quiz #1: October 29 ? Open book, 85 minutes (start 10:30) ? Chapter 4 coverage: Sections 4.1through 4.7 (inclusive); Section 4.9 (skim through 4.9.4) ? Review Problem Set 3 ? Review some old quizzes A few additional items ? A simpler (than in the book) derivation of the expression for L for M/G/1 systems is provided in a note on the website; it assumes FIFO service ? A derivation of expression (4.113) in the book for M/M/1 queuing systems with preemptive priorities and two classes of customers is provided in another note on the website ? We shall skip Section 4.8 in the book except for a brief discussion at end of this lecture; you may wish to skim through the section Lecture Outline ? Introduction to systems with priorities ? Representation of a priority queuing system ? The M/G/1 non-preemptive priority system ? An important optimization theorem ? … and an important corollary ? Brief mention of other priority systems ? Bounds for G/G/1 systems ? A numerical example Background and observations ? W, L, Wq and Lq are not affected as long as the queue discipline does not give priority to certain classes of customers ? WFIFO = WSIRO = WLIFO (what about the corresponding variances?) ? Things may change, however, in systems where customers are assigned to various priority classes, if different classes have different service-time characteristics ? Preemptive vs. non-preemptive priority systems ? Preemptive-resume vs. preemptive-repeat A queuing system with r priority classes x x x x x x x x x x x x Service Facility 1 2 k-1 k k+1 r l1 l2 lk-1 lk lk+1 lr M/G/1 system with non-preemptive priorities: background ? r classes of customers; class 1 is highest priority, class r is lowest ? Poisson arrivals for each class k; rate lk ? General service times, Sk , for each class; fSk(s); E[Sk]=1/mk; E[Sk2] ? FIFO service for each class ? Infinite queue capacity for each class ? Define: rk = lk /mk ? Assume for now that: r = r1 + r2 +….+ rr <1 Expected time in queue of customer of class k who has just arrived at system ∑∑ ? == ?+?+= 1 11 0 11 k i i i k i qi i qk MLWW mm W0 = expected remaining time in service of the customer who occupies the server when the new customer (from class k) arrives Lqi = expected no. of customers of class i who are already waiting in queue at the instant when the newly arrived customer (from class k) arrives Mi = expected number of customers of class i who will arrive while the newly arrived customer (from class k) is waiting in queue Expressions for the constituent parts 2 ][ ][2 ][)|( 22 0 ii i i SE SE SEiW ?= ?= m è ∑∑∑ === ?=??=?= r i iir i iiir i i SESEiWW 1 2 1 2 1 00 2 ][ 2 ][)|( lmrr (1) qiiqi WL ?= l (2) qkii WM ?= l (3) [random incidence, see (2.66)] A closed-form expression ∑∑ ? == ?+?+= 1 11 0 k i iqk k i qiiqk WWWW rr rkfor WW W k i i k i qii qk ,......,2,1 1 1 1 1 0 = ? ?+ = ∑ ∑ ? = = r r ∑ =? ==??= k i ik kk qk awhererkforaa WW 11 0 ,......,2,1 )1)(1( r è (4) [from (1), (2) and (3)] and solving (4) recursively, for k=1, k=2,….., we obtain (5): A generalization ? Let p be an integer between 1 and r such that r1 + r2 +….+ rp <1 while r1 + r2 +….+ rp + rp+1 ? 1 ? Then customers in classes 1 through p experience steady-state conditions, while those in p+1 through r suffer unbounded in-system (or waiting) times ? Customers in classes 1 through p occupy the server a fraction rk of the time each (k = 1, 2, …, p); customers in class p+1 occupy the server a fraction 1- ap ;and the other classes do not have any access ? The expression (5) for Wqk can be modified accordingly by writing the correct expression for W0 in the numerator Generalized expression pkforaa SE SEa SE SE W kk p i p pp i ii qk ≤?? ? ??+ ? ? = ? = + +∑ )1)(1( ][2 ][)1( ][2 ][ 1 1 1 2 12r pkWqk >∞= Minimizing total expected cost ck = cost per unit of time that a customer of class k spends in the queuing system (waiting or being served) ? Suppose we wish to minimize the expected cost (per unit of time) of the total time that all customers spend in the system: ∑ ∑∑ = == ??+?=?= r i r i qiiiii r i ii WccLcC 1 11 lr ? For each class k compute the ratio kk k kk c SE cf m?== ][ (6) Optimization theorem and corollary ? Theorem: To minimize (6), priorities should be assigned according to the ratios fk : the higher the ratio, the higher the priority of the class. ? Corollary: To minimize average time in the system for all customers, priorities should be assigned according to the expected service times for each customer class: the shorter the expected service time, the higher the priority of the class. Cost inflow and outflow in a priority queuing system c(t) ck c k t1 t2 Cost inflow Cost outflow Cost ($) Time Other priority systems ? Simple closed-form results also exist for several other types of priority systems; examples include: _ Non-preemptive M/M/m queuing systems with r classes of customers and all classes of customers having the same service rate m _ Preemptive M/M/1 queuing systems with r classes of customers and all classes of customers having the same service rate m (see below expression for Wk) ∑ =? ==??= k i ik kk k awhererkforaaW 11 ,......,2,1)1)(1( )1( rm A general upper bound for G/G/1 systems ? A number of bounds have been obtained for more general cases (see Section 4.9) ? A good example is an upper bound for the waiting time at G/G/1 systems: (7) where X and S are, respectively, the r.v.’s denoting inter- arrival times and service times ? Under some fairly general conditions, such bounds can be tightened and perform extremely well )1()1(2 )( 22 <?? +?≤ rrssl SXqW Better bounds for a (not so) special case ? For G/G/1 systems whose inter-arrival times have the property that for all non-negative values of t0, l 1]|[ 00 ≤>? tXtXE it has been shown that: )1()1(2 )(21 22 <?? +?=≤≤+? rrssllr SXq BWB (what does this mean, intuitively?) ? Note that the upper and lower bounds in (8) differ by, at most, 1/l and that the percent difference between the upper and lower bounds decreases as r increases! (8)