Queuing Systems: Lecture 4 Amedeo odoni October 22. 2001
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
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 rovided 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
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/ 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
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, Waand la are not affected as long as the queue discipline does not give priority to certain classes of customers WEIFOWSIRO= 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
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 XX xX x 2 2 人k1 ervice Facility XXX Xk+ XX
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/ 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 k General service times, Sk, for each class fs(s); ElSa]=1/uKs E[SK2 FIFO service for each class Infinite queue capacity for each class Define: Pk Assume for now that: P=P1+p2+. t pr<1
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[Sk 2] • 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 k-1 Wak=Wot Lo:+ =1i Wo=expected remaining time in service of the customer who occupies the server when the new customer(from class k) arrives e9=expected no of customers of class who are already waiting queue at the instant when the newly arrived customer(from class arrives M;= expected number of customers of class i who will arrive while the newly arrived customer(from class k) is waiting in queue
Expected time in queue of customer of class k who has just arrived at system å å - = = = + × + × 1 1 1 0 1 1 k i i i k i qi i Wqk W L M m m 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 (W01a)=ES71_,E% 2·E[S [random incidence, see(2.66) W0=∑p;(01)=∑ p;:·ES]、4:E Lqi=ni Wqi W
Expressions for the constituent parts 2 [ ] 2 [ ] [ ] ( | ) 2 2 0 i i i i E S E S E S W i × = × = m Ë å å å = = = × = × × = × = r i i i r i i i i r i i E S E S W W i 1 2 1 2 1 0 0 2 [ ] 2 [ ] ( | ) r m l r (1) Lqi i Wqi = l × (2) Mi i Wqk = l × (3) [random incidence, see (2.66)]
A closed-form expression Wk=W0+∑PHq+y:∑P[rom(1,2)nd(3 W+∑;Wq fork=1,2……,r(4 and solving(4) recursⅳey,fork=1,k=2……, we obtain(5)} W rk=1,2,…, where ak=∑p k-1 k
A closed-form expression å å - = = = + × + × 1 1 1 0 k i qk i k i Wqk W ri Wqi W r for k r W W W k i i k i i qi qk 1, 2,......, 1 1 1 1 0 = - + × = å å - = = r r å - = = = - - = k i k i k k qk for k r where a a a W W 1 1 0 1, 2,......, (1 )(1 ) r Ë (4) [from (1), (2) and (3)] and solving (4) recursively, for k=1, k=2,….., we obtain (5):