08 Queueing Models - fu-berlin.de

1 Chapter 8 Chapter 8 Queueing Dr. Mesut G ne Ch. 8 Queueing ModelsContents Characteristics of Queueing Systems Queueing Notation Kendall NotationQg Long-run Measures of Performance of Queueing Systems Steady-state Behavior of Infinite-Population MarkovianModels Steady-state Behavior of Finite-Population Models Networks of Dr. Mesut G ne Ch. 8 Queueing ModelsPurpose Simulation is often used in the analysis of Queueing Models . A simple but typical Queueing modelServerWaiting lineCalling 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 utilization, length of waiting lines, and delays of customers For relatively simple systems: compute mathematically For relatively simple systems: compute mathematically For realistic Models of complex systems: simulation is usually Dr.

2 Mesut G ne Ch. 8 Queueing ModelsOutline Discuss some well-known Models Not development of Queueing theory, for this see other class!pqgy, We will deal with General characteristics of queues Meanings and relationshipsof important performance measures Estimation of mean measuresof performance Effect of varying input parametersEffect of varying input parameters Mathematical solutions of some basicqueueing Dr. Mesut G ne Ch. 8 Queueing ModelsCharacteristics of Queueing SystemsCharacteristics of Queueing Dr. Mesut G ne Ch. 8 Queueing ModelsCharacteristics of Queueing Systems Key elements of Queueing systems Customer: refers to anything that arrives at a facility and requires service, , people, machines, trucks, emails, packets, frames. Server: refers to any resource that provides the requested service, , repairpersons, machines, runways at airport, host, switch, router, disk drive, deskPeopleReceptionistHospitalPatientsNu rsesAitAi lRAirportAirplanesRunwayProduction lineCasesCase-packerRoad networkCarsTraffic lightGroceryShoppersCheckout stationComputerJobsCPU, disk, CDNt Dr.

3 Mesut G ne Ch. 8 Queueing ModelsNetworkPacketsRouterCalling Population Calling population: the population of potential customers, may be assumed to be finiteor infinite. Finite population model: if arrival rate depends on the number of customers being served and waiting, , model of one corporate jet, if it is being repaired, the repair arrival rate becomes lti dl if i l t i t ff td b th nn1 Infinite population model: if arrival rate is not affected by the number of customers being served and waiting, , systems with large population of potential customers. Dr. Mesut G ne Ch. 8 Queueing ModelsSystem Capacity System Capacity: a limit on the number of customers that may be in the waiting line or system. Limited capacity, , an automatic car wash only has room for 10 cars to wait in line to enter the mechanism. If system is full no customers are accepted anymoreIf system is full no customers are accepted anymoreServerWaiting line Unlimited capacity, , concert ticket sales with no limit on the number of people allowed to wait to purchase Dr.

4 Mesut G ne Ch. 8 Queueing ModelsServerWaiting lineArrival Process For infinite-populationmodels: In terms of interarrival times of successive customers. Arrival types: Random arrivals: interarrival times usually characterized by a probability distribution. Most important model: Poisson arrival process (with rate ), where a time represents the interarrival time between customer n-1and customer n, and is exponentially distributed (with mean 1/ ).py() Scheduled arrivals: interarrival times can be constant or constant plus or minus a small random amount to represent early or late Example: patients to a physician or scheduled airline flight arrivals to an airport At least one customer is assumed to always be present, At least one customer is assumed to always be present, so the server is never idle, , sufficient raw material for a Dr. Mesut G ne Ch. 8 Queueing ModelsArrival Process For finite-populationmodels: Customer is pendingwhen the customer is outside the Queueing pgqgsystem, , machine-repair problem: a machine is pending when it is operating, it becomes not pending the instant it demands service from the Runtimeof a customer is the length of time from departure from the Queueing system until that customer s next arrival to the queue, , machine-repair problem, machines are customers q,g,pp,and a runtime is time to failure (TTF).

5 Let A1(i),A2(i), ..be the successive runtimes of customer i, and S1(i),S2(i)be the corresponding successive system Dr. Mesut G ne Ch. 8 Queueing ModelsQueue Behavior and Queue Discipline Queue behavior: the actions of customers while in a queue 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 Jockey: move from one line to a shorter line Queue discipline: the logical ordering of customers in a Queue discipline: the logical ordering of customers in a queue that determines which customer is chosen for service when a server becomes free, for example:Fi tifi tt (FIFO) First-in-first-out (FIFO) Last-in-first-out (LIFO) Service in random order (SIRO)() Shortest processing time first (SPT) Service according to priority (PR) Dr.

6 Mesut G ne Ch. 8 Queueing ModelsService 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 independent and identically distributed (IID) random variables, , Exponential, Weibull, Gamma, Lognormal, and Truncated normal distribution. A Queueing system consists of a number of service centers and A Queueing system consists of a number of service centers and interconnected queues. Each service center consists of some number of servers (c) working in parallel upon getting to the head of the line a customer takes the in parallel, upon getting to the head of the line, a customer takes the 1stavailable Dr. Mesut G ne Ch. 8 Queueing ModelsQueuing 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) Dr.

7 Mesut G ne Ch. 8 Queueing ModelsQueuing System: Example 1 Wait for one of the three clerks: Batch service (a server serving several customers Batch service (a server serving several customers simultaneously), or customer requires several servers Dr. Mesut G ne Ch. 8 Queueing ModelsQueuing System: Example Dr. Mesut G ne Ch. 8 Queueing ModelsQueuing System: Example 2 Candy production line Three machines separated by bufferspy Buffers have capacity of 1000 candiesAssumption:Allways sufficient supply of raw Dr. Mesut G ne Ch. 8 Queueing ModelsQueueingNotationThe Kendall Dr. Mesut G ne Ch. 8 Queueing ModelsQueueing Notation: Kendall Notation A notation system for parallel server queues: A/B/c/N/K Arepresents the interarrival-time distribution Brepresents the service-time distribution Brepresents the servicetime distribution crepresents the number of parallel servers Nrepresents the system capacity Krepresents the size of the calling populationpoagpopuao N, Kare usually dropped, if they are infinity Common symbols for Aand B MMarkov, exponential distribution,p DConstant, deterministic EkErlang distribution of order k HHyperexponential distribution GGeneral, arbitrary Examples M/M/1/ / same as M/M/1:Single-server with unlimited capacity and call-l ti I ti l d i ti ti ll di t ib t dpopulation.)

8 Interarrival and service times are exponentially distributed 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 service discipline FIFOProf. Dr. Mesut G ne Ch. 8 Queueing ModelsQueueing Notation General performance measures of Queueing systems: Pnsteady-state probability of having ncustomers in system P(t)probability of ncustomers in system at time t Pn(t)probability of ncustomers in system at time t arrival rate eeffective arrival rate service rate of one server service rate of one server server utilization Aninterarrival time between customers n-1and n Snservice time of the n-th arriving customerng Wntotal time spent in system by the n-th customer WnQtotal time spent in the waiting line by customer n L(t)the number of customers in system at time t LQ(t)the number of customers in queue at time t Llong-run time-average number of customers in system LQlong-run time-average number of customers in queueQ Wlong-run average time spent in system per customer wQlong-run average time spent in queue per Dr.

9 Mesut G ne Ch. 8 Queueing ModelsLong-run Measures of Performance of Queueing SystemsQueueing Dr. Mesut G ne Ch. 8 Queueing ModelsLong-run Measures of Performance of Queueing Systems Primary long-run measures of performance are Llong-run time-average number of customers in system LQlong-run time-average number of customers in queue Wlong-run average time spent in system per customer wQlong-run average time spent in queue per customerQ server utilization Other measures of interest are Long-run proportion of customers who are delayed longer than ttime unitst0time units Long-run proportion of customers turned away because of capacity constraints Long-run proportion of time the waiting line contains more than Dr. Mesut G ne Ch. 8 Queueing ModelsLong-run Measures of Performance of Queueing Systems Goal of this section Major measures of performance for a general G/G/c/N/Kjp gqueueing system How these measures can be estimated from simulation runs Two types of estimators Sample average Sample average Time-integrated sample Dr.

10 Mesut G ne Ch. 8 Queueing ModelsTime-Average Number in System LNumber of customers in the Dr. Mesut G ne Ch. 8 Queueing ModelsTime-Average Number in System L Consider a Queueing system over a period of time T Let Tidenote the total time during [0,T ]in which the system dlhhdbcontained exactly icustomers, the time-weighted-averagenumber in the system is defined by: 1 iTiiTL Consider the total area under the function is L(t),then, == ==00iiiiTiiTTL(),, == TidttLTiTTL0)(11 The long-run time-average number of customers in system, with probability 1: =iTT00probability 1: )(1 0 LdttLTLTT = Dr. Mesut G ne Ch. 8 Queueing ModelsTime-Average Number in System LNumber of customers in the Dr. Mesut G ne Ch. 8 Queueing ModelsTime-Average Number in System L The time-weighted-average number in queue is:TQ 11 G/G/1/N/Kexample: consider the results from the Queueing system (NQTTQiQiQLdttLTiTTL == = 00)(11 G/G/1/N/Kexample: consider the results from the Queueing system (N 4, K 3).)