Question? Leave a message!

Simulation of Queuing Systems

Simulation of Queuing Systems
Dr.MasonHanks Profile Pic
Published Date:23-07-2017
Website URL
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; why?Queuing 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 data-structures  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 multi-access 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): 20