08 Queueing Models - Fu-berlin.de
Chapter 8Queueing ModelsProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.1
Contents Characteristics of Queueing SystemsQueueingQg Notation – Kendall NotationLong-run Measures of Performance of Queueing SystemsSteady-state Behavior of Infinite-Population MarkovianModels Steady-state Behavior of Finite-Population Models Networks of QueuesProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.2
Purpose Simulation is often used in the analysis of queueing models. A simple but typical queueing modelCalling populationWaiting lineServer Queueing models provide the analyst with a powerful tool for designing and evaluating the performance of queueing systems.Typical measures of system performance Server utilization, length of waiting lines, and delays of customers For relatively simple systems: compute mathematically For realistic models of complex systems: simulation is usuallyrequiredProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.3
Outline Discuss some well-known models Not developmentpof qqueueingg theory,y, for this see other class! We will deal with General characteristics of queues Meanings and relationships of important performancemeasures Estimation of mean measures of performance Effect of varying input parameters Mathematical solutions of some basic queueing modelsProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.4
Characteristics of Queueing SystemsProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.5
Characteristics of Queueing Systems Key elements of queueing systems Customer: refers to anything that arrives at a facility and requiresservice, e.g., people, machines, trucks, emails, packets, frames. Server: refers to any resource that provides the requested service,e.g., repairpersons, machines, runways at airport, host, switch,router, disk drive, algorithm.SystemyCustomersServerReception orttAi lAirplanesRRunwayProduction lineCasesCase-packerRoad networkCarsTraffic lightGroceryShoppersCheckout stationComputerJobsCPU, disk, CDN tNetworkkP k tPacketsR tRouterProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.6
Calling Population Calling population: the population of potential customers, maybe assumed to be finite or infinite. Finite population model: if arrival rate depends on the number ofcustomers being served and waiting, e.g., model of one corporatejet, if it is being repaired, the repair arrival rate becomes zero.nnn-11 InfiniteI fi it populationl timodel:d l if arrivali l ratet iis nott affectedff t d bby thethnumber of customers being served and waiting, e.g., systems withlarge population of potential customers. Prof. Dr. Mesut Güneş Ch. 8 Queueing Models8.7
System Capacity System Capacity: a limit on the number of customers thatmay be in the waiting line or system. Limited capacity, e.g., an automatic car wash only has room for 10cars to wait in line to enter the mechanism. If system is full no customers are accepted anymoreWaiting lineServer Unlimited capacity, e.g., concert ticket sales with no limit on thenumber of people allowed to wait to purchase tickets.Waiting lineProf. Dr. Mesut Güneş Ch. 8 Queueing ModelsServer8.8
Arrival Process For infinite-population models: In terms of interarrival times of successive customers. Arrival types: Random arrivals: interarrival times usually characterized by aprobability distribution. Most important model: Poisson arrival process (with rate λ), wherea time represents the interarrival time between customer n-1 andcustomer n, and is exponentiallypy distributed (with(mean 1/λ)). Scheduled arrivals: interarrival times can be constant orconstant plus or minus a small random amount to representy or late arrivals.early Example: patients to a physician or scheduled airline flight arrivalsto an airport At least one customer is assumed to always be present,so the server is never idle, e.g., sufficient raw material fora machine.Prof. Dr. Mesut Güneş Ch. 8 Queueing Models8.9
Arrival Process For finite-population models: Customer is ppendingg when the customer is outside the qqueueinggsystem, e.g., machine-repair problem: a machine is “pending”when it is operating, it becomes “not pending” the instant itdemands service from the repairman.p Runtime of a customer is the length of time from departure fromthe queueing system until that customer’s next arrival to thequeue,, e.g.,qg , machine-repairpproblem,, machines are customerspand a runtime is time to failure (TTF). Let A1(i), A2(i), be the successive runtimes of customer i, and S1(i),pg successive systemytimes:S2(i) be the correspondingProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.10
Queue Behavior and Queue Discipline Queue behavior: the actions of customers while in aqueue waiting for service to begin, for example: Balk: leave when they see that the line is too long Renege: leave after being in the line when its moving too slowly Jockey: move from one line to a shorter line Queue discipline: the logical ordering of customers in aqueue that determines which customer is chosen forservice when a server becomes free, for example: First-in-first-outFi t i fi tt (FIFO) Last-in-first-out (LIFO) Service in random order (SIRO)() Shortest processing time first (SPT) Service according to priority (PR)Prof. Dr. Mesut Güneş Ch. 8 Queueing Models8.11
Service Times and Service Mechanism Service times of successive arrivals are denoted by S1, S2, S3. May be constant or random. {S1, S2, S3, } is usually characterized as a sequence of independentand identically distributed (IID) random variables, e.g., Exponential, Weibull, Gamma, Lognormal, and Truncated normaldistribution. A queueing system consists of a number of service centers andinterconnected queues. Each service center consists of some number of servers (c) workingin parallel,parallel upon getting to the head of the lineline, a customer takes the1st available server.Prof. Dr. Mesut Güneş Ch. 8 Queueing Models8.12
Queuing System: Example 1 Example: consider a discount warehouse where customers may serve themselves before paying at the cashier (service center 1) or served by a clerk (service center 2)Prof. Dr. Mesut Güneş Ch. 8 Queueing Models8.13
Queuing System: Example 1 Wait for one of the three clerks: Batch service (a server serving several customerssimultaneously), or customer requires several serverssimultaneously.Prof. Dr. Mesut Güneş Ch. 8 Queueing Models8.14
Queuing System: Example 1Prof. Dr. Mesut Güneş Ch. 8 Queueing Models8.15
Queuing System: Example 2 Candy production line Three machines separatedpbyy buffers Buffers have capacity of 1000 candiesAssumption:Allwayssufficient supply ofraw material.Prof. Dr. Mesut Güneş Ch. 8 Queueing Models8.16
Queueing NotationThe Kendall NotationProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.17
Queueing Notation: Kendall Notation A notation system for parallel server queues: A/B/c/N/K ABcNKN, Krepresents the interarrival-time distributionrepresents the serviceservice-timetime distributionrepresents the number of parallel serversrepresents the system capacityrepresentspthe size oof the callinga g populationpopu a oare usually dropped, if they are infinity MDEkHGMarkov,, exponentialpdistributionConstant, deterministicErlang distribution of order kHyperexponential distributionGeneral, arbitrary Common symbols for A and B Examples M/M/1/ / same as M/M/1: Single-server with unlimited capacity and callpopulation.l tiIInterarrivalti l andd servicei titimes are exponentiallyti ll didistributedt ib t d G/G/1/5/5: Single-server with capacity 5 and call-population 5. M/M/5/20/1500/FIFO: Five parallel server with capacity 20, call-population 1500,and service discipline FIFOProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.18
Queueing Notation General performance measures of queueing systems: te probability of having n customers in systemprobability of n customers in system at time tarrival rateeffective arrival rateservice rate of one serverserver utilizationinterarrival time between customers n-1 and nservice time of the n-th arrivingg customertotal time spent in system by the n-th customertotal time spent in the waiting line by customer nthe number of customers in system at time tthe number of customers in queue at time tlong-run time-average number of customers in systemlong-run time-average number of customers in queuelong-run average time spent in system per customerlong-run average time spent in queue per customerProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.19
Long-run Measures of Performance ofQueueing SystemsProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.20
Long-run Measures of Performance of QueueingSystems Primary long-run measures of performance are LLQWwQlong-runlong-runlong-runlong-runtime-average number of customers in systemtime-average number of customers in queueaverage time spent in system per customeraverage time spent in queue per customerρserver utilization Other measures of interest are Long-run proportion of customers who are delayed longer thant0 time units Long-run proportion of customers turned away because ofcapacity constraints Long-run proportion of time the waiting line contains morethan k0 customersProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.21
Long-run Measures of Performance of QueueingSystems Goal of this section Majorj measures of pperformance for a ggeneral G/G/c/N/Kqueueing system How these measures can be estimated from simulation runs Two types of estimators Sample average Time-integrated sample averageProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.22
Time-Average Number in System LNumber ofcustomers in thesystemyTimeProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.23
Time-Average Number in System L Consider a queueing system over a period of time T Let Ti denote the total time during [0,T ] in which the systemcontainedd exactlyl i customers, theh time-weighted-averageh dnumberb inthe system is defined by:1Lˆ T i 0 iTi T i i T i 0 Consider the total area under the function is L(t),( ), then,,1Lˆ T 1iTi Ti 0 T L(t )dt0 The long-run time-average number of customers in system, withprobability 1:1ˆL TProf. Dr. Mesut Güneş Ch. 8 Queueing Models T0L(t )dt T L 8.24
Time-Average Number in System LNumber ofcustomers in thesystemyTimeProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.25
Time-Average Number in System L The time-weighted-average number in queue is: 11QˆLQ iTi TT i 0 T0LQ (t )dt T LQ G/G/1/N/K example: consider the results from the queueing system (N 4, K 3).Lˆ [0(3) 1(12) 2(4) 3(1)] / 20 23 / 20 1.15 customersProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.26
Time-Average Number in System Lif L(t) 0 0,LQ (t ) L(t ) 1, if L(t) 1Prof. Dr. Mesut Güneş Ch. 8 Queueing Models0(15) 1(4) 2(1) 0.3 customersLˆQ 208.27
Average Time Spent in System Per Customer w The average time spent in system per customer, called theaverage system time, is:1wˆ NN Wi 1iwhere W1, W2, , WN are the individual times that each of the Ncustomers spend in the system during [0,T]. For stable systems:wˆ w as N If the system under consideration is the queue alone:1ˆwQ NProf. Dr. Mesut Güneş Ch. 8 Queueing ModelsNQW i N wQi 18.28
Average Time Spent in System Per Customer w G/G/1/N/K example (cont.): The averageg systemytime is (Wi Di – Ai)wˆ W1 W2 . W5 2 (8 3) (10 5) (14 7) (20 16) 4.6 time units55 The average queuing time isA4A3A1D1A2Prof. Dr. Mesut Güneş Ch. 8 Queueing Models0 0 3 3 0wˆ Q 1.2 time units5D2D3D4A5D58.29
The Conservation Equation orLittle’sLittles LawProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.30
The Conservation Equation:Little’s Law One of the most common theorems in queueing theory Mean number of customers in system Conservation equation (a.k.a. Little’s law)ArrivalsBlack BoxDeparturesaverage number in system arrival rate average system timeProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.31
The Conservation Equation:Little’s Law Conservation equation (a.k.a. Little’s law)Average # insystemLˆ λˆwˆAverageSystem timeA i l rateArrivalL λw as T and N Holds for almost all qqueueingg systemsyor subsystemsy(regardless( gofthe number of servers, the queue discipline, or other specialcircumstances).p ((cont.):) On average,g , one arrival everyy 4 time G/G/1/N/K exampleunits and each arrival spends 4.6 time units in the system. Hence, atan arbitrary point in time, there are (1/4)(4.6) 1.15 customerspresent on average.Prof. Dr. Mesut Güneş Ch. 8 Queueing Models8.32
Server Utilization Definition: the proportion of time that a server is busy. Observed server utilization, ,ρ̂ is defined over a specified timeintervall [0,T ]. Long-run server utilization is ρ.ywith long-rungstability:y For systemsρˆ ρ as T Prof. Dr. Mesut Güneş Ch. 8 Queueing Models8.33
Server Utilization For G/G/1/ / queues: Any single-server queueing system with average arrival rate λ customers per time unit, average service time E(S) 1/μ time units, and infinite queue capacity and calling population.population Conservation equation, L λw, can be applied. For a stable system, the average arrival rate to the server, λs,must be identical to λ. The average number of customers in the server is:1ˆLs TProf. Dr. Mesut Güneş Ch. 8 Queueing ModelsTT T() L(t ) L (t ) dt Q00T8.34
Server Utilization In general, for a single-server queue:Lˆs ρˆ T Ls ρ andρ λ E (s) For a single-server stable queue:λμρ λ 1μ For an unstable queue (λ μ),) longlong-runrun server utilization is 1.1Prof. Dr. Mesut Güneş Ch. 8 Queueing Models8.35
Server Utilization For G/G/c/ / queues: A system with c identical servers in parallel. If an arriving customer finds more than one server idle, thecustomer chooses a server without favoring any particularserver.server For systems in statistical equilibrium, the average number ofbusy servers, Ls, is:LS λE ( S ) λμ Clearly 0 LS c The long-runlong run average server utilization is:Lsλρ , where λ cμ for stable systemsccμProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.36
Server Utilization and System Performance System performance varies widely for a given utilization ρ. For example, a D/D/1 queue where E(A) 1/λ and E(S) 1/μ,where:L ρ λ/μ, w E(S) 1/μ, LQ WQ 0 By varying λ and μ, server utilization can assume any valuebetween 0 and 1. InI general,l variabilityi bilit off iinterarrivalti l andd servicei titimes causeslines to fluctuate in length.Prof. Dr. Mesut Güneş Ch. 8 Queueing Models8.37
Server Utilization and System Performance Example: A physician whoschedules patients every 10minutes and spends Si minuteswith the i-thi th patient: 9 minutes with probability 0.9Si 12 minutes with probability 0.1 Consider the system issimulated with service times:S1 9, S2 12, S3 9, S4 9, S5 9,. The system becomes: Arrivals are deterministic:A1 A2 λ-11 10 Services are stochastic E(Si) 99.33 min V(S0) 0.81 min2 σ 0.9 min On average, the physician'sutilization isρ λ/μμ 0.93 1Prof. Dr. Mesut Güneş Ch. 8 Queueing Models The occurrence of arelatively long service time(S2 12) causes a waiting lineto form temporarily.8.38
Costs in Queueing Problems Costs can be associated with various aspects of the waiting lineor servers: System incurs a cost for each customer in the queuequeue, say at a rate of 10 per hour per customer.WjQ is the time The average cost per customer is:N 10 W jQj 1N customer j spendsin queue 10 wˆ Q If λ̂ customers per hour arrive (on average), the average cost perhour is:ˆ10 L ˆ customer 10 wˆ Q Q 10 λˆ wˆ Q λ hour customer hour Server may also impose costs on the system, if a group of c parallelservers (1 c ) have utilization ρ, each server imposes a cost of 5 per hour while busy. TheTh ttotalt l server costt is:i 5 c ρProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.39
Steady-state Behavior of InfinitePopulation Markovian ModelsProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.40
Steady-State Behavior of Markovian Models Markovian models: Exponential-distributed arrival process (mean arrival rate 1/λ). Service times may be exponentially (M) or arbitrary (G) distributed. Queue discipline is FIFO. A queueing system is in statistical equilibrium if the probability thatthe system is in a given state is not time dependent:P ( L(t ) n) Pn (t ) Pn Mathematical models in this chapter can be used to obtainapproximate results even when the model assumptions do not strictlyhold, as a rough guide. Simulation can be used for more refined analysis, more faithfulrepresentation for complex systems.Prof. Dr. Mesut Güneş Ch. 8 Queueing Models8.41
Steady-State Behavior of Markovian Models Properties of processes with statistical equilibrium The state of statistical equilibriumqis reached from anyy startinggstate. The process remains in statistical equilibrium once it hasreached it.itProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.42
Steady-State Behavior of Markovian Models For the simple model studied in this chapter, the steadystate parameter, L, the time-average number ofcustomers in the system is: L nPnn 0 Apply Little’sLittle s equationequation, LL λ w, to the whole system and to thequeue alone:w Lλ,wQ w 1μ,LQ λwQ G/G/c/ / example: to have a statistical equilibrium, anecessary and sufficient condition is:ρ Prof. Dr. Mesut Güneş Ch. 8 Queueing Modelsλ 1cμ8.43
M/G/1 Queues Single-server queues with Poisson arrivals and unlimited capacity. Suppose service times have mean 1/μ and variance σ 2 and ρ λ / μ 1,the steady-state parameters of M/G/1 queue:λρ μP0 1 ρρ 2 (1 σ 2 μ 2 )L ρ 2(1 ρ )The particulardistribution is notknown!λ (1 / μ 2 σ 2 )w 2(1 ρ )μ1ρ 2 (1 σ 2 μ 2 )LQ 2(1 ρ )λ (1 / μ 2 σ 2 )wQ 2(1 ρ )Prof. Dr. Mesut Güneş Ch. 8 Queueing ModelsρP0LwLQwQserver utilizationprobability of empty systemlong-run time-average number of customers in systemlong-run average time spent in system per customerlong-run time-average number of customers in queuelong-run average time spent in queue per customer8.44
M/G/1 Queues There are no simple expressions for the steady-state probabilities P0, P1, P2 , L – LQ ρ is the time-average number of customers beingserved.Average length of queue,queue LQ, can be rewritten as:ρ2λ2σ 2LQ 2(1 ρ ) 2(1 ρ ) If λ and μ are held constant, LQ depends on the variability, σ 2, of theservice times.Prof. Dr. Mesut Güneş Ch. 8 Queueing Models8.45
M/G/1 Queues Example: Two workers competing for a job, Able claims to be fasterthan Baker on average, but Baker claims to be more consistent, Poisson arrivals at rate λ 2 per hour (1/30 per minute). Able: 1/μ 24 minutes and σ 2 202 400 minutes2:(1 / 30) 2 [24 2 400]LQ 2.711 customers2(1 4 / 5) The proportion of arrivals who find Able idle and thus experience no delay isP0 1-ρ 1/5 20%. Baker: 1/μ 25 minutes and σ 2 22 4 minutes2:(1 / 30) 2 [25 2 4]LQ 2.097 customers2(1 5 / 6) The proportion of arrivals who find Baker idle and thus experience no delay isP0 1-ρ 1/6 16.7%. Although working faster on average, Able’s greater service variability resultsin an average queue length about 30% greater than Baker’s.Prof. Dr. Mesut Güneş Ch. 8 Queueing Models8.46
M/M/1 Queues Suppose the service times in an M/G/1 queue are exponentiallydistributed with mean 1/μ, then the variance is σ 2 1/μ2. M/M/1 queue is a useful approximate model when service timeshave standard deviation approximately equal to their means. The steadysteady-statestate parameters0,35ρ 0,30λμ0,250,20Pn (1 ρ )ρ nL M/M/1 Queue Pnλμ λ P0 1 ρρ1 ρ11w μ λ μ (1 ρ )λ2ρ2 LQ μ (μ λ ) 1 ρλρ wQ μ (μ λ ) μ (1 ρ )Prof. Dr. Mesut Güneş Ch. 8 Queueing Models0,150,100,050 000,001 3 5 7 9 11 13 15 17 19 21ρP0LwLQwQserver utilizationprobability of empty systemlong-run time-average number of customers in systemlong-run average time spent in system per customerlong-run time-average number of customers in queuelong-run average time spent in queue per customer8.47
M/M/1 Queues Single-chair unisex hair-styling shop Interarrival and service times are exponentiallydistributed λ 2 customers/hour and µ 3 customers/hourρ λ 2 μ 3L 13P0 1 ρ 121 2 4P2 3 3 27P 4 1 Pn n 0Prof. Dr. Mesut Güneş Ch. 8 Queueing Modelsμ λL 2 2 Customers3 22 1 hourλ 211 2wQ w 1 hourhμ3 3w 1 2 2P1 3 3 93λ1681 λ244LQ Customersμ ( μ λ ) 3(3 2) 3λ 4 2L LQ 2 Customersμ 3 38.48
M/M/1 Queues Example: M/M/1 queuewith service rate μ 10customers per hour.λρLw Consider how L and w increaseas arrival rate, λ, increasesfrom 5 to 8.64 by incrementsof 20% Increase in average systemtime (w) and average numberi systemint(L) isi highlyhi hlnonlinear as a function of ρ.67.28.64100.51.00.601.500.722.570.8646.3501 0.20.250.360.730 0.9120L18 w16Number oof Customers If λ/μ 1, waiting lines tend tocontinually grow in length5141210864200.50.60.70.8rhoProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.49
Effect of Utilization and Service Variability For almost all queues, if lines are too long, they can be reduced by decreasing server utilization (ρ) or by decreasingthe service time variability (σ2).A measure of the variability of a distribution: coefficientffoff variation (cv):(cv) 2 V (X )[E ( X )]2 The larger cv is, the more variable is the distribution relative to itsexpected value For exponential service times with rate µ E(X) 1/µ V(X) 1/µ2 cv 1Prof. Dr. Mesut Güneş Ch. 8 Queueing Models8.50
Effect of Utilization and Service Variability Consider LQ for anyFor any M/G/1(cv)2 σ2/(1/µ)2 σ2µ2M/G/1 qqueue:ρ 2 (1 σ 2 μ 2 )LQ 2(1 ρ ) ρ 2 1 (cv) 2 1 ρ 2 LQ for M/M/1queue Corrects the M/M/1formula to account for anon-exponential servicetime dist’nProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.51
Multiserver Queue: M/M/c M/M/c/ / queue: c servers operating in parallel Arrival process is poisson with rate λ Each server has an independent and identical exponential servicetime distribution, with mean 1/μ.q, the offered load (λ/μμ) must satisfyy To achieve statistical equilibrium,λ/μ c, where λ/(cµ) ρ is the server utilization.Calling populationλ1Waiting line2cProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.52
Multiserver Queue: M/M/c The steady-state parameters for M/M/cρ Probability thatall servers arebusyλcμ c 1 (λ / μ ) n λ c 1 cμ P0 n 0 n! μ c! cμ λ (cρ ) c P0P ( L ( ) c ) c!(1 ρ )L cρ w 1(cρ ) c 1 P0ρ P ( L ( ) c ) cρ 21 ρc(c!)(1 ρ )Lλρ P (L ( ) c )LQ 1 ρL LQ cρProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.53
Multiserver Queue: M/M/cProbability of empty systemlog scale on y axisProf. Dr. Mesut Güneş Ch. 8 Queueing ModelsProbability of empty system8.54
Multiserver Queue: M/M/cProbability of empty systemProf. Dr. Mesut Güneş Ch. 8 Queueing ModelsNumber of customers in system8.55
Multiserver Queue: Common Models Other common multiserver queueing models ρ 2 1 (cv) 2 LQ 2 1 ρ LQ for M/M/1queueCorrects the M/M/1formula M/G/c/ : general service times and c parallel server. Theparameters can be approximatedpppfrom those of the M/M/c/ / model. M/G/ : general service times and infinite number of servers. M/M/c/N/ : service times are exponentially distributed at rate μ andc servers where the total system capacity is N c customer. Whenan arrival occurs and the system is full, that arrival is turnedaway.Prof. Dr. Mesut Güneş Ch. 8 Queueing Models8.56
Multiserver Queue: M/G/ M/G/ : general service times and infinite number of servers customer is its own server service capacity far exceeds service demand when we want to know how many servers are required so thatcustomers are rarely delayedPn e λμP0 e λμw ( λμ ) nn!, n 0,1, K1μwQ 0λL μLQ 0Prof. Dr. Mesut Güneş Ch. 8 Queueing Models8.57
Multiserver Queue: M/G/ How many users can be logged in simultaneously in a computersystem Customers log on with rate λ 500 per hour Stay connected in average for 1/µ 180 minutes 3 hours For planning purposes it is pretended that the simultaneous logged inusers is infinite Expected number of simultaneous users LλL 500 3 1500μ To ensure providing adequate capacity 95% of the time, the numberof parallel users c has to be restrictede 1500 (1500) nP ( L( ) c) Pn 0.95n!n 0n 0cc The capacity c 1564 simultaneous users satisfies this requirementProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.58
Multiserver Queue with Limited Capacity M/M/c/N/ : service times are exponentially distributed at rate μ andc servers where the total system capacity is N c customer When an arrival occurs and the system is fullfull, that arrival is turned away Effective arrival rate λe is defined as the mean number of arrivals pertime unit who enter and remain in the systemλa μλρ cμ 1P0PNLQλec a n a c N n c 1 ρ n!c!n c 1 n 1 aN P0c!c N cP0 a c ρ 1 ρ N c ( N c) ρ N c (1 ρ )c!(1 ρ ) λ (1 PN )wQ ()LQλew wQ 1μ(1 - PN) probabilityb bilit thatth t acustomer will find aspace and be able toenter the systemL λe wProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.59
Multiserver Queue with Limited CapacitySingle-chair unisex hair-styling shop (again!) Space only for 3 customers: one in service and two waitingFirst compute P0P0 1 2 2 3 2 n 1 1 3 3 n 2 3 0.415 P(system is full)PN P32 3() 3 P21!10 8 0.12365 Average of the queueLQ 0.431 Effective arrival rate λe 2 1 8 114 1.754 65 65Prof. Dr. Mesut Güneş Ch. 8 Queueing Models Queue timewQ LQλe 28 0.246114 System time, time in shopw wQ 1μ 66 0.579114 Expected number of customersin shopL λe w 66 1.01565 Probability of busy shop1 P0 λe 0.585μ8.60
Steady-state Behavior of Finite-PopulationModelsProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.61
Steady-State Behavior of Finite-PopulationModels In practical problems calling population is finite When the calling population is small, the presence of one or more customersin the system has a strong effect on the distribution of future arrivals. Consider a finite-calling population model with K customers (M/M/c/K/K) The time between the end of one service visit and the next call for service isexponentially distributed with mean 1/λ. Service times are also exponentially distributed with mean 1/µ. c parallel servers and system capacity is K.K CustomersMean runtime1/λ1Waiting line with capacity K-c2cProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.62
Steady-State Behavior of Finite-PopulationModels Some of the steady-state probabilities of M/M/c/K/K : c 1 K λ n KK!P0 n c n 0 n μ n c ( K n)!c!c K λ n P0 , n μPn K! ( K n)!c!c n c KL nPn ,n 0 λ μ n 1n 0,1,., c 1n λ , μ w L / λe ,n c, c 1,.Kρ λecμwhere λe is the long run effective arrival rate of customers to queue (or entering/exiting service)Kλe ( K n)λPnn 0Prof. Dr. Mesut Güneş Ch. 8 Queueing Models8.63
Steady-State Behavior of Finite-PopulationModels Example: two workers who are responsible for 10 millingmachines. Machines run on the average for 20 minutes, then require anaverage 5-minute service period, both times exponentiallydistributed: λ 1/20 and μ 1/5. All of the performance measures depend on P0: 1n 2 1 10 5 n 1010! 5 P0 0.065n 2 n20(10 n)!2!220 n 0 n 2 Then, we can obtain the other Pn, and can compute theexpected number of machines in system:10L nPn 3.17 machinesn 0 The average number of running machines:K L 10 3.17 6.83 machinesProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.64
Networks of QueuesProf. Dr. Mesut Güneş Ch. 8 Queueing Models8.65
Networks of Queues No simple notation for networks of queues Two typesyp of networks of queuesq Open queueing network External arrivals and departures Numberb off customers in system varies over time Closed queueing network No external arrivals and departures Number of customers in system is constantOutInProf. Dr. Mesut Güneş Ch. 8 Queueing ModelsOutIn8.66
Networks of Queues Many systems are modeled as networks of single queues Customers departing from one queue may be routed toanotherhλiIniλj λipijjOut The followingg results assume a stable systemywith infinitecalling population and no limit on system capacity: Provided that no customers are created or destroyed in the queue,then the departure rate out of a queue is the same as the arrival rateinto the queue, over the long run. If customers arrive to queue i at rate λi, and a fraction 0 pij 1 ofthem are routed to queue j upon departure, then the arrival rateffromqueue i tot queue j isi λj λi pij over theth longlrun.Prof. Dr. Mesut Güneş Ch. 8 Queueing Models8.67
Networks of Queues The overall arrival rate into queue j:λj aj λ piijall iArrival ratefrom outsidethe networkSum of arrival ratesffromotherth queues ininetwork If queue j has cj parallel servers, each working at rate μj, thenthe long-run utilization of each server is: (where ρj 1 for stablequeue).λρj jcjμ j If arrivals from outside the network form a Poisson process with rateaj for each queue j, and if there are cj identical servers deliveringexponentiallyi ll didist
Purpose Simulation is often used in the analysis of queueing models. A simple but typical queueing model Waiting line Server Calling population Queueing models provide the analyst with a powerful tool for designing and evaluating the performance of queueing systems. Typical measures of system performance Server util
802.16 networks was conducted in [7], [8] by combining link-layer queueing with physical-layer transmission. A vacation queueing model was adopted in [9] to analyze the link-layer queueing performance of OFDM-TDMA systems with round-robin scheduling. A queueing model for OFDMA systems was used in [10] to design a scheduling scheme that balances
Ice Machine Part List for SN Series CounterTop Models SN012A SN020A Updated: 7/12 Der Link zu den Manitowoc Nuggeteisbereiter im Online Shop Kälte-Berlin Ihr Manitowoc Fachhändler: Kälte-Berlin Am Pfarracker 41 12209 Berlin Fon: 49 30 74 10 40 22 Fax: 49 30 74 10 40 21 Mail: info@kaelte-berlin.de Internet: www.kaelte-berlin.com
Components of a Queueing Model The calling population Finite or infinite (often approx. “very large”) Infinite pool: arrival rate not affected by the number of customers who have left the calling population and joined the queueing system. Finite pool: can affect arrival proce
of Queueing Theory Applied to Emergency Care. Here is a picture of the participants at our meeting on October 25, 2012. Figure 1. Emergency Care/Queueing Seminar: (Left to Right) Jed Keesling, Trent Register, Joshua Hurwitz, Jean Larson, James Maissen, Hayriye Gulbu-dak, Evan Milliken,
have faded. But our lack of completeness is also explained by the time constraints of this survey. Queueing applications are abundant in Canada. The diverse areas where queueing analysis has been applied include: ship-ping and canals, grocery store checkout line count estimation, vehic
theory to construct the dynamic system of screening system in this paper. Queueing theory is the mathematical study of waiting lines [23]. In queueing theory, a model is constructed so that queue length
the understanding of teletra c, queueing theory fundamentals and related queueing behavior of telecommunications networks and systems. These concepts and ideas form a strong base for the more mathematically inclined students who can follow up with the extensive literature on
Advanced Engineering Mathematics 6. Laplace transforms 21 Ex.8. Advanced Engineering Mathematics 6. Laplace transforms 22 Shifted data problem an initial value problem with initial conditions refer to some later constant instead of t 0. For example, y” ay‘ by r(t), y(t1) k1, y‘(t1) k2. Ex.9. step 1.
