Introduction to Queuing and Simulation.ppt

1、1,Introduction to Queuing and Simulation,Chapter 6Business Process Modeling, Simulation and Design,2,Overview (I),What is queuing/ queuing theory? Why is it an important tool? Examples of different queuing systems Components of a queuing system The exponential distribution & queuing Stochastic proce

2、sses Some definitions The Poisson process Terminology and notation Littles formula Birth and Death Processes,3,Overview (II),Important queuing models with FIFO discipline The M/M/1 model The M/M/c model The M/M/c/K model (limited queuing capacity) The M/M/c/N model (limited calling population) Prior

3、ity-discipline queuing models Application of Queuing Theory to system design and decision making,4,Overview (III),Simulation What is that? Why is it an important tool? Building a simulation model Discrete event simulation Structure of a BPD simulation project Model verification and validation Exampl

4、e Simulation of a M/M/1 Queue,5,Mathematical analysis of queues and waiting times in stochastic systems. Used extensively to analyze production and service processes exhibiting random variability in market demand (arrival times) and service times. Queues arise when the short term demand for service

5、exceeds the capacity Most often caused by random variation in service times and the times between customer arrivals. If long term demand for service capacity the queue will explode!,What is Queuing Theory?,6,Capacity problems are very common in industry and one of the main drivers of process redesig

6、n Need to balance the cost of increased capacity against the gains of increased productivity and service Queuing and waiting time analysis is particularly important in service systems Large costs of waiting and of lost sales due to waitingPrototype Example ER at County Hospital Patients arrive by am

7、bulance or by their own accord One doctor is always on duty More and more patients seeks help longer waiting times Question: Should another MD position be instated?,Why is Queuing Analysis Important?,7,A Cost/Capacity Tradeoff Model,8,Commercial Queuing Systems Commercial organizations serving exter

8、nal customers Ex. Dentist, bank, ATM, gas stations, plumber, garage Transportation service systems Vehicles are customers or servers Ex. Vehicles waiting at toll stations and traffic lights, trucks or ships waiting to be loaded, taxi cabs, fire engines, elevators, buses Business-internal service sys

9、tems Customers receiving service are internal to the organization providing the service Ex. Inspection stations, conveyor belts, computer support Social service systems Ex. Judicial process, the ER at a hospital, waiting lists for organ transplants or student dorm rooms ,Examples of Real World Queui

10、ng Systems?,9,Components of a Basic Queuing Process,Calling Population,Queue,Service Mechanism,Input Source,The Queuing System,Jobs,Arrival Process,Queue Configuration,Queue Discipline,Served Jobs,Service Process,leave the system,10,The calling population The population from which customers/jobs ori

11、ginate The size can be finite or infinite (the latter is most common) Can be homogeneous (only one type of customers/ jobs) or heterogeneous (several different kinds of customers/jobs) The Arrival Process Determines how, when and where customer/jobs arrive to the system Important characteristic is t

12、he customers/jobs inter-arrival times To correctly specify the arrival process requires data collection of interarrival times and statistical analysis.,Components of a Basic Queuing Process (II),11,The queue configuration Specifies the number of queues Single or multiple lines to a number of service

13、 stations Their location Their effect on customer behavior Balking and reneging Their maximum size (# of jobs the queue can hold) Distinction between infinite and finite capacity,Components of a Basic Queuing Process (III),12,Example Two Queue Configurations,13,The service provided can be differenti

14、ated Ex. Supermarket express lanes Labor specialization possible Customer has more flexibility Balking behavior may be deterred Several medium-length lines are less intimidating than one very long line,Guarantees fairness FIFO applied to all arrivals No customer anxiety regarding choice of queue Avo

15、ids “cutting in” problems The most efficient set up for minimizing time in the queue Jockeying (line switching) is avoided,Multiple v.s. Single Customer Queue Configuration,Multiple Line Advantages,Single Line Advantages,14,The Service Mechanism Can involve one or several service facilities with one

16、 or several parallel service channels (servers) - Specification is required The service provided by a server is characterized by its service time Specification is required and typically involves data gathering and statistical analysis. Most analytical queuing models are based on the assumption of ex

17、ponentially distributed service times, with some generalizations. The queue discipline Specifies the order by which jobs in the queue are being served. Most commonly used principle is FIFO. Other rules are, for example, LIFO, SPT, EDD Can entail prioritization based on customer type.,Components of a

18、 Basic Queuing Process (IV),15,Concealing the queue from arriving customers Ex. Restaurants divert people to the bar or use pagers, amusement parks require people to buy tickets outside the park, banks broadcast news on TV at various stations along the queue, casinos snake night club queues through

19、slot machine areas. Use the customer as a resource Ex. Patient filling out medical history form while waiting for physician Making the customers wait comfortable and distracting their attention Ex. Complementary drinks at restaurants, computer games, internet stations, food courts, shops, etc. at ai

20、rports Explain reason for the wait Provide pessimistic estimates of the remaining wait time Wait seems shorter if a time estimate is given. Be fair and open about the queuing disciplines used,Mitigating Effects of Long Queues,16,A Commonly Seen Queuing Model (I),C C C C,Customers (C),C S = Server C

21、S C S,Customer =C,The Queuing System,The Queue,The Service Facility,17,Service times as well as interarrival times are assumed independent and identically distributed If not otherwise specified Commonly used notation principle: A/B/C A = The interarrival time distribution B = The service time distri

22、bution C = The number of parallel servers Commonly used distributions M = Markovian (exponential) - Memoryless D = Deterministic distribution G = General distribution Example: M/M/c Queuing system with exponentially distributed service and inter-arrival times and c servers,A Commonly Seen Queuing Mo

23、del (II),18,The most commonly used queuing models are based on the assumption of exponentially distributed service times and interarrival times.Definition: A stochastic (or random) variable Texp( ), i.e., is exponentially distributed with parameter , if its frequency function is:,The Exponential Dis

24、tribution and Queuing, The Cumulative Distribution Function is: The mean = ET = 1/ The Variance = VarT = 1/ 2,19,The Exponential Distribution,Time between arrivals,Mean= ET=1/,Probability density,t,fT(t),20,Property 1: fT(t) is strictly decreasing in t P(0Tt) P(t T t+t) for all t, t0Implications Man

25、y realizations of T (i.e.,values of t) will be small; between zero and the mean Not suitable for describing the service time of standardized operations when all times should be centered around the mean Ex. Machine processing time in manufacturing Often reasonable in service situations when different

26、 customers require different types of service Often a reasonable description of the time between customer arrivals,Properties of the Exp-distribution (I),21,Property 2: Lack of memory P(Tt+t | Tt) = P(T t) for all t, t0Implications It does not matter when the last customer arrived, (or how long serv

27、ice time the last job required) the distribution of the time until the next one arrives (or the distribution of the next service time) is always the same. Usually a fair assumption for interarrival times For service times, this can be more questionable. However, it is definitely reasonable if differ

28、ent customers/jobs require different service,Properties of the Exp-distribution (II),22,Property 3: The minimum of independent exponentially distributed random variables is exponentially distributedAssume that T1, T2, , Tn represent n independent and exponentially distributed stochastic variables wi

29、th parameters 1, 2, , n.Let U=min T1, T2, , Tn Implications Arrivals with exponentially distributed interarrival times from n different input sources with arrival intensities 1, 2, , n can be treated as a homogeneous process with exponentially distributed interarrival times of intensity = 1+ 2+ n. S

30、ervice facilities with n occupied servers in parallel and service intensities 1, 2, , ncan be treated as one server with service intensity = 1+2+n,Properties of the Exp-distribution (III),23,Relationship to the Poisson distribution and the Poisson ProcessLet X(t) be the number of events occurring in

31、 the interval 0,t. If the time between consecutive events is T and Texp() X(t)Po(t) X(t), t0 constitutes a Poisson Process,Properties of the Exp-distribution (IV),24,Definition: A stochastic process in continuous time is a family X(t) of stochastic variables defined over a continuous set of t-values

32、.Example: The number of phone calls connected through a switch board Definition: A stochastic process X(t) is said to have independent increments if for all disjoint intervals (ti, ti+hi) the differences Xi(ti+hi)Xi(ti) are mutually independent.,Stochastic Processes in Continuous Time,25,The standar

33、d assumption in many queuing models is that the arrival process is PoissonTwo equivalent definitions of the Poisson Process The times between arrivals are independent, identically distributed and exponential X(t) is a Poisson process with arrival rate .,The Poisson Process,26,Poisson processes can b

34、e aggregated or disaggregated and the resulting processes are also Poisson processesa) Aggregation of N Poisson processes with intensities 1, 2, , n renders a new Poisson process with intensity = 1+ 2+ n.b) Disaggregating a Poisson process X(t)Po(t) into N sub-processes X1(t), X2(t), , , X3(t) (for

35、example N customer types) where Xi(t) Po(it) can be done if For every arrival the probability of belonging to sub-process i = pi p1+ p2+ pN = 1, and i = pi ,Properties of the Poisson Process,27,Illustration Disaggregating a Poisson Process,X(t)Po(t),p1,p2,pN,28,The state of the system = the number o

36、f customers in the system Queue length = (The state of the system) (number of customers being served)N(t) = Number of customers/jobs in the system at time t Pn(t) = The probability that at time t, there are n customers/jobs in the system. n = Average arrival intensity (= # arrivals per time unit) at

37、 n customers/jobs in the system n = Average service intensity for the system when there are n customers/jobs in it. (Note, the total service intensity for all occupied servers) = The utilization factor for the service facility. (= The expected fraction of the time that the service facility is being

38、used),Terminology and Notation,29,Example Service Utilization Factor,Consider an M/M/1 queue with arrival rate = and service intensity = = Expected capacity demand per time unit = Expected capacity per time unit,Similarly if there are c servers in parallel, i.e., an M/M/c system but the expected cap

39、acity per time unit is then c*,30,Steady State condition Enough time has passed for the system state to be independent of the initial state as well as the elapsed time The probability distribution of the state of the system remains the same over time (is stationary). Transient condition Prevalent wh

40、en a queuing system has recently begun operations The state of the system is greatly affected by the initial state and by the time elapsed since operations started The probability distribution of the state of the system changes with time,Queuing Theory Focus on Steady State,With few exceptions Queui

41、ng Theory has focused on analyzing steady state behavior,31,Transient and Steady State Conditions,Illustration of transient and steady-state conditions N(t) = number of customers in the system at time t, EN(t) = represents the expected number of customers in the system.,32,Pn = The probability that

42、there are exactly n customers/jobs in the system (in steady state, i.e., when t) L = Expected number of customers in the system (in steady state) Lq = Expected number of customers in the queue (in steady state) W = Expected time a job spends in the system Wq= Expected time a job spends in the queue,

43、Notation For Steady State Analysis,33,Assume that n = and n = for all nAssume that n is dependent on n,Littles Formula Revisited,34,The foundation of many of the most commonly used queuing models Birth equivalent to the arrival of a customer or job Death equivalent to the departure of a served custo

44、mer or jobAssumptions Given N(t)=n, The time until the next birth (TB) is exponentially distributed with parameter n (Customers arrive according to a Po-process) The remaining service time (TD) is exponentially distributed with parameter n TB & TD are mutually independent stochastic variables and st

45、ate transitions occur through exactly one Birth (n n+1) or one Death (n n1),Birth-and-Death Processes,35,A Birth-and-Death Process Rate Diagram,0,1,n-1,n,= State n, i.e., the case of n customers/jobs in the system,Excellent tool for describing the mechanics of a Birth-and-Death process,36,Assumption

46、s - the Basic Queuing Process Infinite Calling Populations Independence between arrivals The arrival process is Poisson with an expected arrival rate Independent of the number of customers currently in the system The queue configuration is a single queue with possibly infinite length No reneging or

47、balking The queue discipline is FIFO The service mechanism consists of a single server with exponentially distributed service times = expected service rate when the server is busy,The M/M/1 - model,37,Situation Patients arrive according to a Poisson process with intensity ( the time between arrivals

48、 is exp() distributed. The service time (the doctors examination and treatment time of a patient) follows an exponential distribution with mean 1/ (=exp() distributed) The ER can be modeled as an M/M/c system where c=the number of doctors,Example ER at County Hospital,Data gathering = 2 patients per

49、 hour = 3 patients per hour Questions Should the capacity be increased from 1 to 2 doctors? How are the characteristics of the system (, Wq, W, Lq and L) affected by an increase in service capacity?,38,Interpretation To be in the queue = to be in the waiting room To be in the system = to be in the ER (waiting or under treatment)Is it warranted to hire a second doctor ?,