Queuing Systems: Lecture 6 Amedeo R. Odoni October 22, 2001 Lecture Outline ? A fundamental result for queuing networks ? State transition diagrams for Markovian queuing systems and networks: example ? Analysis of systems with dynamic demand and service rates ? Qualitative behavior of dynamic systems ? Reference: Sections 4.10 and 4.11 A result which is important in analyses of queuing networks Let the arrival process at a M/M/m queuing system with infinite queue capacity have parameter l. Then, under steady state conditions (l<mm) the departure process from the queuing system is also Poisson with parameter l. Implication: greatly facilitates analysis of open acyclic networks consisting of M/M/m queues with infinite queue capacities. The bad news: result holds only under exact set of conditions described above. Open acyclic network of M/M/. systems #1: m=3 (per server) M/M/2 l=4 #2: m=2 1 negative exponential server #3: m=6 1 negative exponential server P=1/3 Q=2/3 l=4/3 l=4/3 l=8/3 l=4 State transition diagrams for queuing systems and networks ? When external arrivals are Poisson and service times are negative exponential, many complex queuing systems and open acyclic queuing networks can be analyzed, even under dynamic conditions, through a judicious choice of state representation ? This involves writing and solving (often numerically) the steady-state balance equations or the Chapman-Kolmogorov first-order differential equations ? The “hypercube model” (Chapter 5 is a good example) Comparison of August Weekday Peaking Patterns 1993 vs. 1998 (3 Hour Average) 0 10 20 30 40 50 60 70 80 90 100 110 120 130 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1993 1998 Hour Operations Two common “approximations” (??) for dynamic demand profiles 1. Find the average demand per unit of time for the time interval of interest and then use steady-state formulae to compute estimates of the queuing statistics. [Problems?] 2. Subdivide the time interval of interest into periods during which demand stays roughly constant; apply the approach of 1 above to each period separately. [Problems?] Dynamic Behavior of Queues [2] 1. The dynamic behavior of a queue can be complex and difficult to predict 2. Expected delay changes non-linearly with changes in the demand rate or the capacity 3. The closer the demand rate is to capacity, the more sensitive expected delay becomes to changes in the demand rate or the capacity 4. The time when peaks in expected delay occur may lag behind the time when demand peaks 5. The expected delay at any given time depends on the “history” of the queue prior to that time 6. The variance (variability) of delay also increases when the demand rate is close to capacity The dynamic behavior of a queue; expected delay for four different levels of capacity 0 5 10 15 20 25 30 35 40 1:00 3:00 5:00 7:00 9:00 11:00 13:00 15:00 17:00 19:00 21:00 23:00 Dem R1 R2 R3 R4 Delays (mins) Demand (movements) 30 15 45 60 75 90 105 120 (R1= capacity is 80 movements per hour; R2 = 90; R3 = 100; R4 = 110) Some statistics for the dynamic queuing example Capacity (movements/hr) Maximum of expected waiting time (minutes) Expected waiting time, all movements (minutes) Utilization ratio (24 hours) Utilization ratio (6:00–21:59) 110 2 0.8 0.455 0.664 100 4 1.6 0.5 0.731 90 13 4.3 0.556 0.812 80 39 12.8 0.625 0.913 Total demand = 1200 movements per day