Review of Queuing ModelsOutlineQueuing ApplicationsQueue RepresentationService time/rateLittle’s LawNotations: A/B/mOutlineCounting Process vs. Interarrival TimesMarkovian Arrival ProcessMarkovian Arrival ProcessProperties of a Poisson ProcessMarkovian Arrival ProcessMarkovian Arrival ProcessExampleExample cont’dOutlineM/M/1 QueueM/M/1 Balance EquationsM/M/1: Solving the Balance EquationsPerformance AnalysisExampleExample (cont’d)Example (cont’d)M/M/1 Further AnalysisM/M/k QueueM/M/k Steady-State ProbabilitiesM/M/k ExampleM/M/k ExampleOutlineM/G/1 QueueM/G/k Queue -- ApproximationM/G/ QueueM/G/k/k QueueM/G/k/k Queue: Loss ProbabilityExampleExample cont’dGI/G/k Queue -- ApproximationGI/G/k Network of QueuesConclusions©2005 Guillaume RoelsReview of Queuing ModelsRecitation, Apr. 1stGuillaume Roels15.763J Manufacturing System and Supply Chain Designhttp://michael.toren.net/slides/ipqueue/slide001.html©2005 Guillaume RoelsOutline• Overview, Notations, Little’s Law• Counting Process vs. Interarrival Times– Memoryless Process• Markovian Queues– M/M/1–M/M/k• General Queues–M/G/1– M/G/k–M/G/∞– M/G/k/k– GI/G/k©2005 Guillaume RoelsQueuing ApplicationsSituation Customers ServerBank Customers TellersAirport Airplanes RunawayTelephone Calls Switches, routers©2005 Guillaume RoelsQueue RepresentationSystemL: expected number of people in the systemW: expected time spent in the systemQ: expected number of people in queueD: expected time spent in queueServerArrival Rate λService Rate µQueue©2005 Guillaume RoelsService time/rate• Service rate: µ (Customers/minute)• Average service time: 1/µ (Minutes/cust.)• Service Process is equivalent to Departure Process only if the queue is always nonempty.Customers in systemtime©2005 Guillaume RoelsLittle’s Law•L=λW (system view)or•Q=λD (waiting line view)Also, W=D+1/µTherefore, compute one quantity (say, L), and get the three others (W, D, Q) for free!Time spent in the systemTime spent in the queueService Time©2005 Guillaume RoelsNotations: A/B/m• A: Arrival Process– M: Memoryless (or Markovian or Poisson)– G: General• B: Service Process– M: Memoryless– G: General• m: Number of servers• Also: A/B/m/k if system has capacity k©2005 Guillaume RoelsOutline• Overview, Notations, Little’s Law• Counting Process vs. Interarrival Times– Memoryless Process• Markovian Queues– M/M/1–M/M/k• General Queues–M/G/1– M/G/k–M/G/∞– M/G/k/k– GI/G/k©2005 Guillaume RoelsCounting Process vs. Interarrival TimesMarkovian Process (M)Number of arrivalsInterarrival Time is Exponentially DistributedTime between Customer 2’s arrival and Customer 3’s arrivalAt time t,N(t)=3N(t) is a Poisson Processttime©2005 Guillaume RoelsMarkovian Arrival Process• Poisson Counting Process (λ=5)• Counts the number of people that have arrived in a time interval t (Discrete Distribution)• Memoryless: the number of people who arrive in [t, t+s] is independent of the number of people who have arrived in [0,t]00.020.040.060.080.10.120.140.160.180.20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20©2005 Guillaume RoelsMarkovian Arrival Process• P(N(t)=n)=exp(-λt)(λt)n/n!• E[N(t)]=λt; Var[N(t)]= λt• Excel: =POISSON(n,λ,0)• When λt>20, very close to a Normal distribution©2005 Guillaume RoelsProperties of a Poisson Process• Merging two Poisson processes, with rates λ1and λ2gives rise to a Poisson process with rare λ1+λ2.• Randomly splitting a Poisson process with rate λ, according to probabilities p and (1-p), gives rise to two Poisson processes with rates λp and λ(1−p).λ1λ2λ1+λ2p1-pλλpλ(1-p)©2005 Guillaume RoelsMarkovian Arrival Process• Exponential Interarrival times (λ=5)• Time between two arrivals; time between now and the next arrival (Continuous Distribution)• Memoryless: the time between now and the next arrival is independent of when was the last arrival! 012345600.20.40.60.811.21.41.61.82©2005 Guillaume RoelsMarkovian Arrival Process•P(T≤t)=1-exp(-λt); t>0•E[T]=1/λ; Var[T]=(1/λ)2Coeff. Of Var=1 (highly random)• Excel: =EXPONDIST(t,λ,1)©2005 Guillaume RoelsExampleThe number of glasses of beer ordered per hour at Dick’s Pub follows a Poisson distribution, with an average of 30 beers per hour being ordered.1. Find the probability that exactly 10 beers are ordered between 10 PM and 10:30PM.Poisson with parameter (1/2)(30)=15.Probability that 10 beers are ordered in 1/2 hour is 048.!10151015=−eExample from Winston, Operations Research, Applications and Algorithms (1993)©2005 Guillaume RoelsExample cont’d2. Find the mean and standard deviation of the number of beers ordered between 9 PM and 1 AM.λ=30 beers per hour; t=4 hours.Mean=4(30)=120 beersStandard Deviation=(120)1/2=10.953. Find the probability that the time between two consecutive orders is between 1 and 3 minutes.X=time between successive ordersX is exponential with rate 30/60=0.5 beers/min.∫=−==≤≤−−−315.15.05.038.)5.0()31( eedteXPt©2005 Guillaume RoelsOutline• Overview, Notations, Little’s Law• Counting Process vs. Interarrival Times– Memoryless Process• Markovian Queues– M/M/1–M/M/k• General Queues–M/G/1– M/G/k–M/G/∞– M/G/k/k– GI/G/k©2005 Guillaume RoelsM/M/1 Queue0 321…λλλλµµµµ• Memoryless Queuing System: • State of the system: number of people in the system• Utilization Rate ρ=λ/µ (<1)©2005 Guillaume RoelsM/M/1 Balance Equations• In steady state, the rate of entry into a state must equal the rate of entry out of a state, if ρ<1.0 321…λλλλµµµµλΠ1+µΠ3=(λ+µ)Π2©2005 Guillaume RoelsM/M/1: Solving the Balance EquationsΠi=(λ/µ)iΠ0=ρiΠ0 • SolutionΠ0=1-ρΠi= (1-ρ)ρiGeometric distribution10=Π∑∞=ii012024681012140.050.0.150.0.25©2005 Guillaume RoelsPerformance Analysis)1(0ρρ−=Π=∑∞=iiiL)1(ρλρλ−==LW)1()1()1(201ρρ−=−−=Π−=∑∞=PLiQii)1(2ρλρλ−==QD01234567891012345678910©2005 Guillaume RoelsExampleAn average of 10 cars per hour arrive at a single-server drive-in teller. Assume the average service time for each customer is 4 minutes, and both interarrival times and service times are exponential. M/M/1 with λ=10 cars/hour and µ=15 cars/hour.Answer the following questions:1. What is the probability that the teller is idle?Π0=1−ρ=1−2/3=1/3Example from Winston, Operations Research, Applications and Algorithms (1993)©2005