Question? Leave a message!




Simulation of Queuing Systems

Simulation of Queuing Systems
Queuing Queuing System System By Prof. S. Shaky ya 1Simulation of Queuing Systems Introduction  Waiting line queues are one of the most important areas, where the technique of simulation has been extensively employed.  The The w waiting aiting lines lines or or queues queues are are a a common common s site ite iin n r real eal life life.  People at railway ticket window, vehicles at a petrol pump or at a traffic signal, workers at a tool crib, products at a machining center center, television television sets sets at at a a r repair epair s shop hop are are a a ffew ew examples examples of of waiting lines. 2Simulation of Queuing Systems  The The waiting waiting line line situations situations arise, arise, either either because, because, There is too much demand on the service facility so that the customers or entities have no wait for getting service, or There is too less demand, in which case the service f facilit ility h have tto wait it ffor t th he ent titi ities  The objective in the analysis of queuing situations is to to balance balance tthe he waiting waiting ttime ime and and idle idle time time, so so as as to to keep the total cost at minimum. 3Simulation of Queuing Systems  The The queuing queuing ttheory heory iits ts development development to to an an engineer A.K.Earlang, who in 1920, studied waiting line queues of telephone calls in CCh openhagen, D Denmark k.  The problem was that during the busy period, t telleph hone operattors were unabl ble tto h handl dle the calls, there was too much waiting time, which which r resulted esulted in in customer customer dissatisfaction dissatisfaction. 4State Variables queue customer server State:  InTheAir: number of aircraft either landing or waiting to land  OnTheGround: number of landed aircraft 5  RunwayFree: Boolean, true if runway availableDiscrete Event Simulation Computation example: example: air air ttraf rafffic ic at at an an airport airport events: aircraft arrival, landing, departure arrival schedules processed event 8:00 departure arrival current event schedules 9:15 9:30 landed landed unprocessed event 8:05 simulation time  Events that have been scheduled, but have not been simulated simulated (processed) (processed) yet yet a are re stored stored in in a a pending pending event list 6  Events are processed in time stamp order; whyQueuing System  Elements Elements of of Queuing Queuing Systems Systems 7Queuing System  Population of Customers or calling source can be considered considered either either limited limited (closed (closed systems) systems) or or unlimited unlimited (open systems).  Unlimited population represents a theoretical model of systems systems w with ith a a large large number number of of possible possible c customers ustomers (a (a bank on a busy street, a motorway petrol station).  Example of a limited population may be a number of processes processes tto o b be e r run un (served) (served) by by a a c computer omputer or or a a c certain ertain number of machines to be repaired by a service man.  It is necessary to take the term "customer" very generally.  Customers Customers m may ay be be people people, m machines achines of of various various nature nature, computer processes, telephone calls, etc. 8Queuing System  Arrival Arrival defines defines the the way way customers customers enter enter the the system.  Mostly Mostly the the a arrivals rrivals are are r random andom with with r random andom intervals between two adjacent arrivals.  Typically Typically the the a arrival rrival iis s described described b by y a a random random distribution of intervals also called Arrival Pattern Pattern. 9Queuing System  Queue or waiting line represents a certain number of customers waiting for service (of course the queue may be empty).  Typ ypically y the customer being g served is considered not to be in the queue. Sometimes the customers form a queue literally (people waiting in a line for a bank teller) ).  Sometimes the queue is an abstraction (planes waiting for a runway to land).  There There are are two two important important properties properties of of a a queue: queue: Maximum Size and Queuing Discipline. 10Queuing System  Maximum Maximum Q Queue ueue Size Size (also (also c called alled System System capacity) is the maximum number of customers that may wait in the queue (plus the one(s) being served) d).  Queue is always limited, but some theoretical models models a assume ssume an an unlimited unlimited queue queue length length.  If the queue length is limited, some customers are forced forced to to renounce renounce w without ithout being being served served 11Applications of Queuing Theory  Telecommunications  Traffic control  Determining the sequence of computer operations  Predicting computer performance  Health services (eg. control of hospital bed assignments)  Ai Airport t ttraffi ffic, aiirlliine ttiick kett salles  Layout of manufacturing systems. 12Example application of queuing theory  In In many many retail retail stores stores and and banks banks  multiple line/multiple checkout system  a qqg ueuing sy ystem where customers wait for the next available cashier  We can prove using queuing theory that : throughput improves increases when queues are used instead of separate lines 13Example application of queuing theory 14Queuing theory for studying networks  View View network network a as s c collections ollections o of f q queues ueues  FIFO datastructures  Queuinggy theory p provides p probabilistic analysis of these queues  Examples:  Average length  Average waiting time  Probability queue is at a certain length  Probability a packet will be lost 15Model Queuing System Queuing System Server Queue Queuing System Server System  Use Queuing models to  Describe the behavior of queuing systems  Evaluate system performance 16System Configuration Servers C Customers Single Queue Configuration 17Characteristics of queuing systems  Arrival Arrival P Process rocess  The distribution that determines how the tasks arrives in the sy ystem.  Service Process  The The distribution distribution that that determines determines the the task task processing time  Number of Servers  Total number of servers available to process the tasks 18Queuing System  Queuing Discipline represents the way the queue is organized (r (rules les o of f iinserting nserting and and r remo emoviing ng c cus stomers tomers to/from to/from the the q que eue e) ). There are these ways: 1) FIFO (First In First Out) also called FCFS (First Come First Serve) ) orderlyyq queue. 2) LIFO (Last In First Out) also called LCFS (Last Come First Serve) stack. 3) SIRO (Serve In Random Order). 4) Priority Queue, that may be viewed as a number of queues for various priorities. 5) Many other more complex queuing methods that typically change the the customer customer’s s position position iin n tthe he queue queue according according to to the the time time spent spent already in the queue, expected service duration, and/or priority. These methods are typical for computer multiaccess systems 19Queuing System  Most qqp uantitative parameters ( (like averag ge q queue length, average time spent in the system) do not depend on the queuing discipline.  That That’s s w why hy most most models models e either ither do do not not take take the the queuing discipline into account at all or assume the normal FIFO queue.  In fact the only parameter that depends on the queuing discipline is the variance (or standard deviation) deviation) of of the the w waiting aiting time time. There There is is t this his important important rule (that may be used for example to verify results of a simulation experiment): 20Queuing System  The two extreme values of the waiting time variance are for the FIFO FIFO q que eue e (minim (minimum) m) and and the the LIFO LIFO q que eue e (ma (maxim imum) m).  Theoretical models (without priorities) assume only one queue.  This is not considered as a limiting factor because practical systems systems with with m more ore queues queues (bank (bank with with s several everal tellers tellers with with separate queues) may be viewed as a system with one queue, because the customers always select the shortest queue.  Of course, it is assumed that the customers leave after being served d.  Systems with more queues (and more servers) where the customers may be served more times are called Queuing Networks. Networks. 21Queuing System  Service represents some activity that takes time and that the customers are waiting for. Again take it very generally generally.  It may be a real service carried on persons or machines, but it may be a CPU time slice, connection created df for a telleph hone call ll, b beiing sh hot d down ffor an enemy plane, etc. Typically a service takes random time.  Theoretical models are based on random distribution of service duration also called Service Pattern.  Another Another i important mportant parameter parameter is is the the number number of of servers. Systems with one server only are called Single Channel Systems, systems with more servers are call lled d M Multi lti Ch Channel l S Syst tems 22Queuing System  Outp put repy presents the way customers leave the system.  Output is mostly ignored by theoretical models, but sometimes sometimes the the customers customers lleaving eaving tthe he server server enter enter the queue again ("round robin" timesharing systems).  Queuing Theory is a collection of mathematical models of various queuing systems that take as inputs inputs parameters parameters of of the the above above e elements lements and and that that provide quantitative parameters describing the system performance 23Analysis of M/M/1 queue  Given: Given: •: Arrival rate of jobs (packets on input link) •:: Service Service rate rate of of the the server server (output (output link) link)  Solve:  L: L: average average number number in in queuing queuing system system  L average number in the queue q  W: W: average average waiting waiting ttime ime iin n w whole hole system system  W average waiting time in the queue q 24M/M/1 queue model L L L q   1 W q W 25Kendall Notation 1/2/3(/4/5/6)  Six Six parameters parameters iin n s shorthand horthand  First three typically used, unless specified 1. Arrival Distribution 2. Service Distribution 3. Number of servers 4. Total Capacity (infinite if not specified) 5. Population Size (infinite) 6. Service Discipline (FCFS/FIFO) 26Kendall Classification of Queuing Systems  The The Kendall Kendall classifi classification cation o of f queuing queuing system systems s (1953) (1953) exi exists sts in in several several modifications.  The most comprehensive classification uses 6 symbols: A/B/s/q/c/p where: where:  A is the arrival pattern (distribution of intervals between arrivals).  B is the service pattern (distribution of service duration).  s is the number of servers.  q iis th the queuiing di disciipli line (FIFO (FIFO, LIFO LIFO, ...) ). O Omitt itted d f for FIFO FIFO or if if not t specified.  c is the system capacity. Omitted for unlimited queues.  p is the population size (number of possible customers). Omitted for open system systems s. 27Kendall Classification of Queuing Systems These symbols are used for arrival and service patterns:  M is the Poisson (Markovian) process with exponential distribution of intervals or service duration respectively.  Em is the Erlang distribution of intervals or service duration.  D is the symbol for deterministic (known) arrivals and constant service duration.  G is a general (any) distribution.  GI is a g( general (any)y) distribution with indep pendent random values. 28Kendall Classification of Queuing Systems Examples:  D/M/1 = Deterministic (known) input, one exponential server, one unlimited FIFO or unspq pecified queue,, unlimited customer p pop pulation.  M/G/3/20 = Poisson input, three servers with any distribution, maximum number of customers 20, unlimited unlimited customer customer population. population.  D/M/1/LIFO/10/50 = Deterministic arrivals, one exponential server, queue is a stack of the maximum maximum s size ize 9 9, total total number number of of customers customers 5 50 0. 29Simulation Simulation of of Queuing Queuing Systems Systems Measures of system performance  The performance of a queuing system can be evaluated in terms of a number of response parameters, however the the following following ffour our are are generally generally employed. employed. 1. Average number of customers in the queue or in the system 2. Average waiting time of the customers in the queue or in the system 3 3. System System utilization utilization 4. The cost of the waiting time idle time 30Simulation of Queuing Systems Measures of system performance  The knowledge of average number of customers in the queue or in the system helps to determine the space requiirementts of f th the waiti iting entiti tities. Al Also ttoo long a waiting line may discourage the prospectus customers, customers, while while no no queue queue may may s suggest uggest tthat hat service service offered is not of good quality to attract customers.  The knowledge of average waiting time in the queue is necessary for determining the cost of waiting in the queue. 31Simulation of Queuing Systems Sy ystem Utilization  System Utilization that is the percentage capacity utilized reflects that extent to which the facility is busy rather than idle.  System utilization factor (s) is the ratio of average arrival rate (λ) to the average service rate (µ). S= λ/µg µ in the case of a single server model S= λ/µn in the case of a “n” server model  The system utilization can be increased by increasing the the arrival arrival r rate ate w which hich amounts amounts t to o iincreasing ncreasing tthe he average average queue length as well as the average waiting time, as shown in fig 1. Under the normal circumstances 100 system utilization is not a realistic goal. 32System Utilization 33 Fig 1Time Oriented Simulation A factoryg y has large number of semiautomatic machines.On 50 of the working days none of the machines fail. On 30of the days one machines fails and on 20of the days two machines fail. The maintenance staff on the average puts 65 of the machines in order in one day, 30 in two days and remaining 5 in three days. Simulate the syyy stem for 30 days duration and estimate the average length of queue, average waiting time and server loading that is the fraction of time for which server is busy. 34Time Oriented Simulation Solution: Th The giiven systtem iis a siinglle server queuiing mod dell. Th The ffaiillure off th the machines in the factory generates arrivals, while the maintenance staff is the service facility. There is no limit on the capacity of the system in other words on the length of waiting line. The population of machines is very large and can be taken as infinite. Arrival pattern: On 50of the days arrival=0 OO n 30off the days arrival=1 On 20of the days arrival=2 Expected arrival rate=0.5+1.3+2.2=0.7 per day. SSi ervice pattttern: 65 machines in 1 day 30 machines in 2 days 5 5 machines machines in in 3 3 d da ays s 35Time Oriented Simulation Average service time: 1.65+2.3+3.05=1.4 days E Expectted d serviice ratte=1/1 1/1.4 4=0 0.714 714 machi hines per d day The expected arrival rate is slightly less than the expected service rate and hence the system can reach a steady state. For the purpose of gg generating the arrivals p per day y and the services comp pleted p per day the given discrete distributions will be used. Random numbers between 0 and 1 will be used to generate the arrivals as under. 0.0r=0.5 Arrivals=0 0.5r=0.8 Arrivals=1 0.8r=1.0Arrivals=2 Si Simil ilarlly, rand dom numb bers b bettween 0 0 and d 1 1 will ill b be used d ffor generating the service times ( ST) 0.0r=0.65ST=1day 0 0.65r=0 65r=0.95ST=2days 95ST=2days 0.95r=1.0 ST=3 days 36Time Oriented Simulation  In the timeoriented simulation, the timer is advanced in fixed steps of time and at each step the system is scanned and updated.  The time is kept very small, so that not many events occur during this this time time.  All the events occurring during this small time interval are assumed to occur at the end of the interval.  At start of the simulation, the syyy stem that is the maintenance facility can assumed to be empty, with no machine waiting for repair.  On day 1, there is no machine in the repair facility.  On day 2 there are 2 arrivals, the queue is made 2.  Since service facility is idle, one arrival is put on service and queue becomes 1.  Server idle time becomes 1 day and the waiting time of customers is is also also 1 1 day day. Timer Timer is is advanced advanced by by one one day day.  The service time, ST is decreased by one and when ST becomes zero facility becomes idle.  Arrivals are g, generated which come out to be 1, it is added to the queue. 37Time Oriented Simulation  Facility is checked, which is idle at this time.  One customer is drawn from the queue, its service time is generated.  Idle time and waiting time are updated. The process is continued till th the end d off siimullati tion.  The following statistics can be determined. Machine failures( arrivals) during 30 days=21 Arrivals per day=21/30=0.7 Waiting time of customer=40 days Waiting time per customer=40/21=1.9 days Average length of the queue=1.9 Server idle time=4 days=4/30 100=13.33 Server loading( g=( 304) )/30=0.87 3839Simulation on queuing system Tutorial In a manufacturing g sy ystem p parts are being g made at a rate of one every 6 minutes. They are two types A and B and are mixed randomly with about 10 percent of type type B B. A A separate separate inspector inspector is is assigned assigned to to examine examine each type of parts. The inspection of a part takes a mean time of 4 minutes with a standard deviation of 2 miinutes , b but part B B tak kes a mean tiime 20 20 miinutes and d a standard deviation of 10 minutes. Both inspectors rejject about 10 of the p parts they y insp pect. Simulate the system for total of 50 type A parts accepted and determine , idle time of inspectors and average time a part part spends spends in in system system. 40