Queuing Systems: Lecture 1 Amedeo R. Odoni October 10, 2001 Topics in Queuing Theory 9. Introduction to Queues; Little’s Law; M/M/1 10. Markovian Birth-and-Death Queues 11. The M/G/1 Queue and Extensions 12. Priority Queues; State Representations 13. Congestion Pricing 14. Dynamic Behavior of Queues 15. Hypercube Queuing Model 16. The Queue Inference Engine; Psychology of Queues Lecture Outline ? Introduction to queuing systems ? Conceptual representation of queuing systems ? Codes for queuing models ? Terminology and notation ? Little’s Law and basic relationships ? Birth-and-death processes ? The M/M/1 queuing system ? State transition diagrams ? Steady-state probabilities Queues ? Queuing Theory is the branch of operations research concerned with waiting lines (delays/congestion) ? A queuing system consists of a user source, a queue and a service facility with one or more identical parallel servers ? A queuing network is a set of interconnected queuing systems ? Fundamental parameters of a queuing system: Demand rate Capacity (service rate) Demand inter-arrival times Service times Queue capacity and discipline (finite vs. infinite; FIFO/FCFS, SIRO, LIFO, priorities) Myriad details (feedback effects, “jockeying”, etc.) A Generic Queuing System Source of users/ customers C C C C C C Queue C C C C C C C Servers Size of user source Arrivals process Queue discipline and Queue capacity Service process Number of servers Arrival point at the system Departure point from the system Queuing network consisting of five queuing systems In Queueing system 1 Queueing system 5 Point where users make a choice Point where users merge + Queueing system 4 Queueing system 2 Queueing system 3 Out Applications of Queuing Theory ? Some familiar queues: _ Airport check-in _ Automated Teller Machines (ATMs) _ Fast food restaurants _ On hold on an 800 phone line _ Urban intersection _ Toll booths _ Aircraft in a holding pattern _ Calls to the police or to utility companies ? Level-of-service (LOS) standards ? Economic analyses involving trade-offs among operating costs, capital investments and LOS Queuing Models Can Be Essential in Analysis of Capital Investments Cost Airport Capacity Cost of building the capacity Total cost Cost of losses due to waiting “Optimal” capacity Optimal cost Strengths and Weaknesses of Queuing Theory ? Queuing models necessarily involve approximations and simplification of reality ? Results give a sense of order of magnitude, changes relative to a baseline, promising directions in which to move ? Closed-form results essentially limited to “steady state” conditions and derived primarily (but not solely) for birth-and-death systems and “phase” systems ? Some useful bounds for more general systems at steady state ? Numerical solutions increasingly viable for dynamic systems A Code for Queuing Models: A/B/m ? Some standard code letters for A and B: _ M: Negative exponential (M stands for memoryless) _ D: Deterministic _ Ek:kth-order Erlang distribution _ G: General distribution ? Model covered in this lecture: M/M/1 C C C C C C C C C C S S S S Service facility QueueCustomers Queueing System – / – / – Distribution of interarrival time Distribution of service time Number of servers Terminology and Notation ? State of system: number of customers in queuing system ? Queue length: number of customers waiting for service ? N(t) = number of customers in queueing system at time t ? Pn(t) = probability that N(t) is equal to n ? ln: mean arrival rate of new customer when N(t) = n ? mn: mean (combined) service rate when N(t) = n Terminology and Notation (2) ? Transient state: state of system at t depends on state of system at t = 0 or on t ? Steady state: system is independent of initial state and t ? m: number of servers (parallel service channels) ? If ln and the service rate per busy server are constant, then ln=l, mn= min (nm, mm) ? Expected interarrival time = 1/l ? Expected service time = 1/m ? Unknowns: _ L = expected number of users in queuing system _ Lq = expected number of users in queue _ W = expected time in queuing system per user (W = E(w)) _ Wq = expected waiting time in queue per user (Wq = E(wq)) ? 4 unknowns We need 4 equations Some Expected Values of Interest at Steady State ? Given: _ l = arrival rate _ m = service rate per service channel Little’s Law Time Number of users t N(t) A(t) A(t): cumulative arrivals to the system C(t) C(t): cumulative service completions in the system T TT TT T WTA dttN T TA T dttN L ?=?== ∫∫ l)( )()()( 00 Relationships among L, Lq, W, Wq ? Four unknowns: L, W, Lq, Wq ? Need 4 equations. We have the following 3 equations: _ L = lW (Little’s law) _ Lq = lWq _ W = Wq + ? If we know any one of the four expected values, we can determine the three others ? The determination of L may be hard or easy depending on the type of queuing system at hand ? m 1 system) in the are customers y that probabilit :( 0 nPnPL n n n∑ ∞ = = Birth-and-Death Queuing Systems 1. m parallel, identical servers. 2. Infinite queue capacity. 3. Whenever n users are in system (in queue plus in service) arrivals are Poisson at rate of ln per unit of time. 4. Whenever n users are in system, service completions are Poisson at rate of mn per unit of time. 5. FCFS discipline. M/M/1: Observing State Transition Diagram from Two Points 10 P?P m= ? From point 1: 0 1 2 n-1 n+1n… l m l l l l l l m m m m m m 201)( PPP mlml +=+ ? From point 2: 0 1 2 n-1 n+1n… l m l l l l l l m m m m m m 10 P?P m= 21 PP ml = 1+= nn PP ml 11)( +? +=+ nnn PPP mlml M/M/1: Derivation of P0 and Pn 00 2 201 ,,, PPPPPP n n ??? ? ??? ?= ??? ? ??? ?== m l m l m l L ∑ ∑∑ ∞ = ∞ = ∞ = ??? ? ??? ? =?=?? ? ? ??? ??= 0 0 0 0 0 1 1 ,1 n n n nn n PPP m lm l )1(1 111 then , 00 <?=??==?? ? ? ??? ?= ∞∞ = ∞ = ∑∑ rrrrrmlmlr Q n n n n )1(and 11 0 0 rrr r ?=?== ∑∞ = n n n n PP Step 1: Step 2: Step 3: Step 4: M/M/1: Derivation of L, W, Wq, and Lq lm l ml ml r r rrr rrrrrrrr rrrrrrr ?=?=?=??? ? ??? ? ??= ??? ? ??? ? ??=?? ?? ? ??= ?=?=?==? ∑ ∑∑∑∑ ∞ = ∞ = ? ∞ = ∞ = ∞ = 1)1()1( 1)1( 1 1)1()1( )1( )1( )1( 2 0 1 1 000 d d d d nnnnPL n n n n n n n n n n lmllm l l ?=??==? 11LW )( 111 lmm l mlmm ?=??=?=? WWq )()( 2 lmm l lmm lll ?=??==? qq WL