Queuing theory 3
Authors: Ebru Vurgun, Damla Yigitoglu and Özlem Özyurt
It is a common phenomenon in everyday life to see a large number of persons waiting in front of a booking counter, in a railway station or in a theatre or in a ration shop to have some service carried out. This waiting problem leads the Danish engineer A.K. (Agner Krarup) Erlang, who worked for the Copenhagen Telephone Exchange to find a solution. He developed in 1903 the Queuing theory. Queuing theory analyze the shared facility needs to be accesed for service by a large number of jobs or customers. Examples for the queuing theory are waiting lines in cafeterias, hospitals, banks, airports and so on. In the following you can find more detailled informations for this topic.
In computer science, queueing theory is the study of queues as a technique for managing processes and objects in a computer. A queue can be studied in terms of: the source of each queued item, how frequently items arrive on the queue, how long they can or should wait, whether some items should jump ahead in the queue, how multiple queues might be formed and managed, and the rules by which items are enqueued and dequeued.
The queues that a computer manages are sometimes viewed as being in stacks. In most systems, an item is always added to the top of a stack. A process that handles queued items from the bottom of the stack first is known as a first-in first-out (FIFO) process. A process that handles the item at the top of the stack first is known as a last-in first-out (LIFO) process.
System of Queuing theory
Elements of Queuing Systems
Figure 1 shows the elements of a single queue queuing system:
Population of Customers can be considered either limited (closed systems) or unlimited (open systems). Unlimited population represents a theoretical model of systems with a large number of possible customers (a bank on a busy street, a motorway petrol station). Example of a limited population may be a number of processes to be run (served) by a computer or a certain number of machines to be repaired by a service man. It is necessary to take the term "customer" very generally. Customers may be people, machines of various nature, computer processes, telephone calls, etc.
Arrival defines the way customers enter the system. Mostly the arrivals are random with random intervals between two adjacent arrivals. Typically the arrival is described by a random distribution of intervals also called Arrival Pattern.
Queue represents a certain number of customers waiting for service (of course the queue may be empty). Typically the customer being 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 are two important properties of a queue: Maximum Size and Queuing Discipline.
Maximum Queue Size (also called System capacity) is the maximum number of customers that may wait in the queue (plus the one(s) being served). Queue is always limited, but some theoretical models assume an unlimited queue length. If the queue length is limited, some customers are forced to renounce without being served.
Queuing Discipline represents the way the queue is organised (rules of inserting and removing customers to/from the queue). There are these ways:
1) FIFO (First In First Out) also called FCFS (First Come First Serve) - orderly 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 customer’s position in the queue according to the time spent already in the queue, expected service duration, and/or priority. These methods are typical for computer multi-access systems.
Most quantitative parameters (like average queue length, average time spent in the system) do not depend on the queuing discipline. That’s why most models either do not take 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) of the waiting time. There is this important rule (that may be used for example to verify results of a simulation experiment):
The two extreme values of the waiting time variance are for the FIFO queue (minimum) and the LIFO queue (maximum).
Theoretical models (without priorities) assume only one queue. This is not considered as a limiting factor because practical systems with more queues (bank with several tellers 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. Systems with more queues (and more servers) where the customers may be served more times are called Queuing Networks.
Service represents some activity that takes time and that the customers are waiting for. Again take it very generally. It may be a real service carried on persons or machines, but it may be a CPU time slice, connection created for a telephone call, being shot down for 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 important parameter is the number of servers. Systems with one server only are called Single Channel Systems, systems with more servers are called Multi Channel Systems.
Output represents the way customers leave the system. Output is mostly ignored by theoretical models, but sometimes the customers leaving the server enter the queue again ("round robin" time-sharing systems).
Queuing Theory is a collection of mathematical models of various queuing systems that take as inputs parameters of the above elements and that provide quantitative parameters describing the system performance.
Because of random nature of the processes involved the queuing theory is rather demanding and all models are based on very strong assumptions (not always satisfied in practice). Many systems (especially queuing networks) are not soluble at all, so the only technique that may be applied is simulation.
Nevertheless queuing systems are practically very important because of the typical trade-off between the various costs of providing service and the costs associated with waiting for the service (or leaving the system without being served). High quality fast service is expensive, but costs caused by customers waiting in the queue are minimum. On the other hand long queues may cost a lot because customers (machines e.g.) do not work while waiting in the queue or customers leave because of long queues. So a typical problem is to find an optimum system configuration (e.g. the optimum number of servers). The solution may be found by applying queuing theory or by simulation.
Applications and limitations
The queueing theorie is used to analyze computer, telecommunication systems, traffic systems (traffic flue), logistic and manufacturing systems.
Some examples :
-Where customers are involved such as restaurants, supermarket, airport, …
-useful in manufactoring units
-applicable for the problem of machine breakdown and repair
-applicable for the sheduling of jobs in production control
-provide solution of inventory control problems
-Most of the queueing models are still complex and are not easy to understand
-Many times form of theoratical distribution applicable to given queueing situations is not known
-The study of queueing problems become more difficult if the queueing discipline is not in „first in, first out“
David George Kendall was an English statistician and mathematician, known for his work on probability, statistical shape analysis, ley lines and queueing theory. Kandall's Notation is the standard system used to describe and classify a queueing node.
A queueing model is characterized by:
a) The arrival process of customers. b) The behaviour of customers. c) The service times. d) The service discipline. e) The service capacity. f) The waiting room.
A special notation, called Kendall's notation, is used to describe a queueing system. The notation has the form A/B/c/K.
->A describes the interarrival time distribution
->B the service time distribution
->c the number of servers
->K the size of the system capacity (including the servers).
The symbols traditionally used for A and B are
->M for exponential distribution (M stands for Markov)
->D for deterministic distribution
->G for general distribution.
When the system capacity is infinite (K = 1) one simply uses the symbol A/B/c. For instance, M/M/1, M/M/c, M/G/1 and G/M/1 are very common queueing systems.
M/M/1 Queuing system
M/M/1 queue represents the queue length in a system having a single server, where arrivals are determined by a Poisson process and job service times have an exponential distribution.The model is the most elementary of queueing models and an attractive object of study as closed-form expressions can be obtained for many metrics of interest in this model. Here is the arrival population unlimited and all arrivals wait to be served. λ is constant and μ >λ (average service rate > average arrival rate).
1. Average server utilization
p=λ / μ
2. Average number of customers waiting
Lq= λ 2 / μ ( μ - λ )
3. Average number in system
L = Lq + λ / μ
4. Average waiting time
Wq=Lq= λ / μ ( μ - λ )
5. Average time in the system
W= Wq + 1/ μ
6. Probability of 0 customers in system
P0= 1 - λ / μ
7. Probability of exactly n customers in system
Pn = ( λ / μ )*n*P0
A mathematical example of M/M/1 Queue
We are in a train station and we see, that a arriving train join a single queue for the runway. We have an exponentially distributed service time with a rate μ= 30 arrivals / hour ( as we computed that in 5 minutes 1 train arrived the station) and we have poisson arrivals with a rate λ= 25 arrivals / hour.
Now we want to calculate W, L, Wq and Lq.
W= 1 / μ - λ= 1/ ( 30-25)= 0,20 hours ≈ 12 min
L= λW = λ / (μ - λ)= 25/ (30-25)= 5 trains
Wq = W- (1/μ)= 1/ (μ - λ) - 1/μ= 1/ ( 30-25) - (1/30)= 0.167 hours≈ 10 min
Lq= λW= λ^2 / μ ( μ - λ )= 25 ^ 2 / 30 ( 30-25) ≈4,167 trains