Queuing Systems: Lecture 6 Amedeo odoni October 22. 2001
Queuing Systems: Lecture 6 Amedeo R. Odoni October 22, 2001
Lecture outline A fundamental result for queuing networks State transition diagrams for Markovian ueuing 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
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/Mm queuing system with infinite queue capacity have parameter n. Then, under steady state conditions(<mu) the departure process from the queuing system is also Poisson with parameterλ 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
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 #2:=2 A=43 1 negative omental server P=1/3 =4#1:=3(pel A=43 server) M/M/2 Q=2/3 #3:=6 1 negative 入=4 =8/3 exponential server
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 udicious 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)
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) Operations 110 口1993■1998 100 900 40 01234567891011121314151617181920212223 Hour
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?
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 [21 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
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 Delays(mins) ( movements) 35 25 75 15 s Dem鲁R1R2 R1= capacity is 80 movements per hour; R2= 90; R3=100: R4=110)
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 Maximum of Expected waiting Utilization Utilization (movements/hr) expected time all movements ratio waiting time (minutes (24 hours)(6:0021:59) (minutes) 110 0.8 0455 0.664 0.5 0.731 13 4.3 0.556 0.812 80 39 12.8 6250913 Total demand =1200 movements per day
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
