Quantitative Techniques For Management
WAITING MODEL (QUEUING THEORY)
Queuing theory deals with problems which involve queuing (or waiting). Typical examples might be:
- banks/supermarkets - waiting for service
- computers - waiting for a response
- failure situations - waiting for a failure to occur e.g. in a piece of machinery
- public transport - waiting for a train or a bus
As we know queues are a common every-day experience. Queues form because resources are limited. In fact it makes economic sense to have queues. For example how many supermarket tills you would need to avoid queuing? How many buses or trains would be needed if queues were to be avoided / eliminated?
In designing queuing systems we need to aim for a balance between service to customers (short queues implying many servers) and economic considerations (not too many servers).
Queues or waiting lines arise when the demand for a service facility exceeds the capacity of that facility, that is, the customers do not get service immediately upon request but must wait, or the service facilities stand idle and wait for customers.
Some customers wait when the total number of customers requiring service exceeds the number of service facilities, some service facilities stand idle when the total number of service facilities exceeds the number of customers requiring service.
Queuing theory explores and measures the performance in a queuing situation such as average number of customers waiting in the queue, average waiting time of a customer and average server utilization.QUEUING SYSTEMS
The customers arrive at service counter (single or in groups) and are attended by one or more servers. A customer served leaves the system after getting the service. In general, a queuing system comprises with two components, the queue and the service facility. The queue is where the customers are waiting to be served. The service facility is customers being served and the individual service stations. A general queuing system with parallel server is shown in figure below:
A typical queuing system
CHARACTERISTICS OF QUEUING SYSTEM
In designing a good queuing system, it is necessary to have good information about the model. The characteristics listed below would provide sufficient information.
- The arrival pattern.
- The service mechanism.
- The queue discipline.
- The number of customers allowed in the system.
- The number of service channels.
The Arrival Pattern
- How customers arrive e.g. singly or in groups (batch or bulk arrivals)
- How the arrivals are distributed in time (e.g. what is the probability distribution of time between successive arrivals (the inter-arrival time distribution))
- Whether there is a finite population of customers or (effectively) an infinite number
The simplest arrival process is one where we have completely regular arrivals (i.e. the same constant time interval between successive arrivals). A Poisson stream of arrivals corresponds to arrivals at random. In a Poisson stream successive customers arrive after intervals which independently are exponentially distributed.
The Poisson stream is important as it is a convenient mathematical model of many real life queuing systems and is described by a single parameter - the average arrival rate. Other important arrival processes are scheduled arrivals; batch arrivals; and time dependent arrival rates (i.e. the arrival rate varies according to the time of day).
The Service Mechanism
- A description of the resources needed for service to begin
- How long the service will take (the service time distribution)
- The number of servers available
- Whether the servers are in series (each server has a separate queue) or in parallel (one queue for all servers)
- Whether preemption is allowed (a server can stop processing a customer to deal with another "emergency" customer)
Assuming that the service times for customers are independent and do not depend upon the arrival process is common. Another common assumption about service times is that they are exponentially distributed.
The Queue Discipline
In the queue structure, the important thing to know is the queue discipline. The queue discipline is the order or manner in which customers from the queue are selected for service.
There are a number of ways in which customers in the queue are served. Some of these are:
(a) Static queue disciplines are based on the individual customer's status in the queue. Few of such disciplines are:
- If the customers are served in the order of their arrival, then this is known as the first-come, first-served (FCFS) service discipline. Prepaid taxi queue at airports where a taxi is engaged on a first-come, first-served basis is an example of this discipline.
- Last-come-first-served (LCFS)-- Sometimes, the customers are serviced in the reverse order of their entry so that the ones who join the last are served first. For example, assume that letters to be typed, or order forms to be processed accumulate in a pile, each new addition being put on the top of them. The typist or the clerk might process these letters or orders by taking each new task from the top of the pile. Thus, a just arriving task would be the next to be serviced provided that no fresh task arrives before it is picked up. Similarly, the people who join an elevator last are the first ones to leave it.
(b) Dynamic queue disciplines are based on the individual customer attributes in the queue. Few of such disciplines are:
- Service in Random Order (SIRO)-- Under this rule customers are selected for service at random, irrespective of their arrivals in the service system. In this every customer in the queue is equally likely to be selected. The time of arrival of the customers is, therefore, of no relevance in such a case.
- Priority Service-- Under this rule customers are grouped in priority classes on the basis of some attributes such as service time or urgency or according to some identifiable characteristic, and FCFS rule is used within each class to provide service. Treatment of VIPs in preference to other patients in a hospital is an example of priority service.
For the queuing models that we shall consider, the assumption would be that the customers are serviced on the first-come-first-served basis.
The Number of Customers allowed in the System
In certain cases, a service system is unable to accommodate more than the required number of customers at a time. No further customers are allowed to enter until space becomes available to accommodate new customers. Such type of situations are referred to as finite (or limited) source queue. Examples of finite source queues are cinema halls, restaurants, etc.
On the other hand, if a service system is able to accommodate any number of customers at a time, then it is referred to as infinite (or unlimited) source queue. For example, in a sales department, here the customer orders are received; there is no restriction on the number of orders that can come in, so that a queue of any size can form.
The Number of Service Channels
The more the number of service channels in the service facility, the greater the overall service rate of the facility. The combination of arrival rate and service rate is critical for determining the number of service channels. When there are a number of service channels available for service, then the arrangement of service depends upon the design of the system's service mechanism.
Parallel channels means, a number of channels providing identical service facilities so that several customers may be served simultaneously. Series channel means a customer go through successive ordered channels before service is completed. A queuing system is called a one-server model, i.e., when the system has only one server, and a multi-server model i.e., when the system has a number of parallel channels, each with one server.
(a) Arrangement of service facilities in series
(1) Single Queue Single Server
(2) Single Queue, Multiple Server
(b) Arrangement of Service facilities in Parallel
(c) Arrangement of Mixed Service facilities
Arrangements of Service Facilities (a, b, c)
Attitude of Customers
Patient Customer: Customer arrives at the service system, stays in the queue until served, no matter how much he has to wait for service.
Impatient Customer: Customer arrives at the service system, waits for a certain time in the queue and leaves the system without getting service due to some reasons like long queue before him.
Balking: Customer decides not to join the queue by seeing the number of customers already in service system.
Reneging: Customer after joining the queue, waits for some time and leaves the service system due to delay in service.
Jockeying: Customer moves from one queue to another thinking that he will get served faster by doing so.
POISSON AND EXPONENTIAL DISTRIBUTIONS
Both the Poisson and Exponential distributions play a prominent role in queuing theory. The Poisson distribution counts the number of discrete events in a fixed time period; it is closely connected to the exponential distribution, which (among other applications) measures the time between arrivals of the events. The Poisson distribution is a discrete distribution; the random variable can only take nonnegative integer values. The exponential distribution can take any (nonnegative) real value.
Considering a problem of determining the probability of n arrivals being observed during a time interval of length t, where the following assumptions are made.
- Probability that an arrival is observed during a small time interval (say of length v) is proportional to the length of interval. Let the proportionality constant be l, so that the probability is lv.
- Probability of two or more arrivals in such a small interval is zero.
- Number of arrivals in any time interval is independent of the number in nonoverlapping time interval.
These assumptions may be combined to yield what probability distributions are likely to be, under Poisson distribution with exactly n customers in the system.
Suppose function P is defined as follows:
P (n customers during period t) = the probability that n arrivals will be observed in a time interval of length t
This is the Poisson probability distribution for the discrete random variable n, the number of arrivals, where the length of time interval, t is assumed to be given. This situation in queuing theory is called Poisson arrivals. Since the arrivals alone are considered (not departures), it is called a pure birth process.
The time between successive arrivals is called inter-arrival time. In the case where the number of arrivals in a given time interval has Poisson distribution, inter-arrival times can be shown to have the exponential distribution. If the inter-arrival times are independent random variables, they must follow an exponential distribution with density f(t) where,
Example : In a factory, the machines break down and require service according to a Poisson distribution at the average of four per day. What is the probability that exactly six machines break down in two days?
Solving the Problem using Computer
Example 1 is solved using computer with TORA. Enter into TORA package and select Queuing Analysis option. Press 'go to input screen' to enter the values. The input screen is shown in Figure given below. The numbers scenarios is 1 and the value of Lambda is λt = 4 × 2 = 8.
Queuing Analysis Using TORA (Input Screen)
Press 'solve', to view the Queuing Analysis output . Select Scenario 1 option, to get the result, as shown in Figure.
Queuing Analysis Using TORA (Output Screen)
In the output screen, for n = 6 the probability, Pn is given as 0.12214.
Example: On an average, 6 customers arrive in a coffee shop per hour. Determine the probability that exactly 3 customers will reach in a 30 minute period, assuming that the arrivals follow Poisson distribution.
Similarly, when the time taken to serve different customers are independent, the probability that no more than t periods would be required to serve a customer is given by exponential distribution as follows:
p(not more than t time period) = 1 – e– mt where m = average service rate
Example : A manager of a fast food restaurant observes that, an average of 9 customers is served by a waiter in a one-hour time period. Assuming that the service time has an exponential distribution, what is the probability that
- A customer shall be free within 12 minutes.
- A customer shall be serviced in more than 25 minutes.
(a) Given, μ = 9 customers / hour
t = 15 minutes = 0.25 hour
Therefore, p (less than 15 minutes) = l – e– mt
= 1– e– 9 × 0.25
(b) Given, μ = 9 customers / hour
t = 25 minutes = 0.4166 hour
Therefore, P (more than 25 minutes) = l – e– mt
= 1– e– 9 × 0.4166
To analyze queuing situations, the questions of interest that are typically concerned with measures of queuing system performance include,
SYMBOLS AND NOTATIONS
- What will be the waiting time for a customer before service is complete?
- What will be the average length of the queue?
- What will be the probability that the queue length exceeds a certain length?
- How can a system be designed at minimum total cost?
- How many servers should be employed?
- Should priorities of the customers be considered?
- Is there sufficient waiting area for the customers?
The symbols and notations used in queuing system are as follows:
n = Number of customers in the system (both waiting and in service).
λ = Average number of customers arriving per unit of time.
μ = Average number of customers being served per unit of time.
λ / μ = P, traffic intensity.
C = Number of parallel service channels (i,e., servers).
Ls = Average or expected number of customers in the system (both waiting and in service).
Lq = Average or expected number of customers in the queue.
Ws = Average waiting time in the system (both waiting and in service).
Wq = Average waiting time of a customer in the queue.
Pn = Time independent probability that there are n customers in the system(both waiting and in service).
Pn (t) = Probability that there are n customers in the system at any time t (both waiting and in service).
SINGLE SERVER QUEUING MODEL
Model 1: (MM1): (α / FIFO)
This model is based on the following assumptions:
- The arrivals follow Poisson distribution, with a mean arrival rate λ.
- The service time has exponential distribution, average service rate μ.
- Arrivals are infinite population α.
- Customers are served on a First-in, First-out basis (FIFO).
- There is only a single server.
System of Steady-state Equations
In this method, the question arises whether the service can meet the customer demand. This depends on the values of λ and μ.
If λ ≥ m, i.e., if arrival rate is greater than or equal to the service rate, the waiting line would increase without limit. Therefore for a system to work, it is necessary that λ < μ.
As indicated earlier, traffic intensity ρ = λ / μ. This refers to the probability of time. The service station is busy. We can say that, the probability that the system is idle or there are no customers in the system, P0 = 1 – ρ.
From this, the probability of having exactly one customer in the system is P1 = ρ P0.
Likewise, the probability of having exactly 2 customers in the system would be
P3 = ρP1 = ρ2 P0
The probability of having exactly n customers in the system is
Pn = ρnP0 = ρn(1-r) = (λ / μ)n P0
The expected number of customers in the system is given by,
SOLVING THE PROBLEM USING COMPUTER WITH TORA
Example above is solved using computer with TORA.
Enter the values λ = 12
μ = 18
No. of server = 1
The input screen is shown in Figure.
Queuing Analysis Using TORA (Input Screen)
Press Solve to get the output screen and select scenario 1 option in the select output option menu. The output screen for the problem is displayed as shown in Figure.
Queuing Analysis Using TORA (Output Screen)
The values are
(a) P0 = 0.3333 (for n = 0)
(b) Lq = 1.33
(c) Wq = 0.1111
(d) Pb (or) r/C= 0.66667
In the same problem, to determine the probability that there are 2 trucks in the system, we use the formula,
This can also be read in the output screen for n=2 the probability Pn = 0.14815, similarly, the probabilities for different values of n can be directly read.
Example: A TV repairman finds that the time spent on his jobs has a exponential distribution with mean 30 minutes. If he repairs TV sets in the order in which they come in, and if the arrivals follow approximately Poisson distribution with an average rate of 10 per 8 hour day, what is the repairman's expected idle time each day? How many jobs are ahead of the average with the set just brought in?
Solution: Given λ = 10 TV sets per day.
μ = 16 TV sets per day.
(i) The Probability for the repairman to be idle is,
P0 = 1 – ρ
We know, ρ = λ / 30 = 10 / 16 =0.625
P0 = 1 – ρ
= 1 – 0.625 = 0.375
Expected idle time per day = 8 × 0.375= 3 hours.
(ii) How many jobs are ahead of the average set just brought in
Example : Auto car service provides a single channel water wash service. The incoming arrivals occur at the rate of 4 cars per hour and the mean service rate is 8 cars per hour. Assume that arrivals follow a Poisson distribution and the service rate follows an exponential probability distribution. Determine the following measures of performance:
(a) What is the average time that a car waits for water – wash to begin?
(b) What is the average time a car spends in the system?
(c) What is the average number of cars in the system?
Solution: Given λ = 4 cars per hour, μ = 8 cars per day.
(a) Average time that a car waits for water - wash to begin,
Wq= l/ l (m-l)
= 4/ 8(8-4)
= 0.125 hours or 7.5 mins
(b) Average time a car spends in the system,
Ws= 1/ m-l
= 1/ 8-4
= 1/4 = 0.25 hours or 15 mins.
(c) Average number of cars in the system,
Ls= l/ m-l
= 4/4 = 1 car
Example : Arrivals at a telephone booth are considered to be Poisson distributed with an average time of 10 minutes between one arrival and the next. The length of phone call is assumed to be distributed exponentially, with mean 3 minutes.
(i)What is the probability that a person arriving at the booth will have to wait?
(ii)The telephone department will install a second booth when convinced that an arrival would expect waiting for at least 3 minutes for phone call. By how much should the flow of arrivals increase in order to justify a second booth?
(iii)What is the average length of the queue that forms from time to time?
(iv)What is the probability that it will take him more than 10 minutes altogether to wait for the phone and complete his call?
(v)What is the probability that it will take him more than 10 minutes altogether to wait for the phone and complete his call?
Solution: Given λ= 1/10 = 0.10 person per minute.
μ = 1/3 = 0.33 person per minute.
(i) Probability that a person arriving at the booth will have to wait,
P (w > 0) = 1 – P0
= 1 – (1 - λ / μ) = λ / μ
= 0.10/0.33 = 0.3
(ii) The installation of second booth will be justified if the arrival rate is more than the waiting time.
Expected waiting time in the queue will be,
Wq = l/ m (m-l)
Where, E(w) = 3 and λ = λ (say ) for second booth. Simplifying we get
λ = 0.16
Hence the increase in arrival rate is, 0.16-0.10 = 0.06 arrivals per minute.
(iii) Average number of units in the system is given by,
Ls= ρ/1- ρ
= 0.43 customers
(iv) Probability of waiting for 10 minutes or more is given by
This shows that 3 percent of the arrivals on an average will have to wait for 10 minutes or more before they can use the phone.
Example : A bank has decided to open a single server drive-in banking facility at its main branch office. It is estimated that 20 customers arrive each hour on an average. The time required to serve a customer is 3 minutes on an average. Assume that arrivals follow a Poisson distribution and the service rate follows an exponential probability distribution.
The bank manager is interested in knowing the following:
(a) What will be the average waiting time of a customer to get the service?
(b) The proportion of time that the system will be idle.
(c) The space required to accommodate all the arrivals, on an average, the space taken by each car is 10 feet that is waiting for service.
Solution: λ = 20 Customers per hour, μ = 60/25 = 2.4 customers per hour.
(a) Average waiting time of a customer to get the service,
Wq = l/ m (m-l)
= 20/ 24 (24-20) = 20/96
= 0.208 hour or 12.5 mins.
(b) The proportion of time that the system will be idle,
P0 = 1- l/ m
= 1- 20/24
= 0.166 hours or 10 mins.
(c ) Average number of customers waiting in the queue,
Lq = l2/ (m-l)
= 20 2/ 24 (24-20)
= 4.66 customers
10 feet is required for 1 customer. Hence, for 4.66 customers, the space required is
10 × 4.66 = 46.6 feet.
Example: In a Bank, customers arrive to deposit cash to a single counter server every 15 minutes. The bank staff on an average takes 10 minutes to serve a customer. The manager of the bank noticed that on an average at least one customer was waiting at the counter.
To eliminate the customer waiting time, the manager provided an automatic currency counting machine to the staff. This decreased the service time to 5 minutes on an average to every customer. Determine whether this rate of service will satisfy the manager's interest. Also use computer with TORA for solving the problem.
Case 1: l = 60/15 = 4 customers per hour, m = 60/10 = 6 customers per hour.
Average number of customers in the system,
Ls = l/ (m-l)
= 4/6-4 = 4/2 = 2 customers.
Case 2: l = 4, m = 60/15 = 12 customers per hour.
Average number of customers in the system,
=4/8 =1/2 = 0.5, say, 1 customer.
Average number of customers in the queue
Lq= l2/ m (m-l)
= 42/12 (12-4)
= 16/96 = 0.01 customers.
Since no customers are standing in the queue the manager's interest is satisfied. The problem is worked out using TORA. Enter the values as shown in the input screen below in Figure.
Queuing Analysis Using TORA (Input Screen)
Press Solve and go to output screen. Select comparative analysis option in the queuing output analysis menu. The following output screen is displayed.
Comparative Analysis of Queuing Output Analysis Using TORA (Output Screen)
Now, on comparing scenario 1 and scenario 2, under Ls i.e., the average number of customers in the system is 2 and 0.5 respectively. In the first scenario, it means that in the entire system, one customer will be waiting in the queue while others are being served. In scenario 2, only one customer is in the system and being served, where on an average no customer will be waiting.
Example: 12 counters are available in a computerized railway reservation system. The arrival rate during peak hours is 90 customers per hour. It takes 5 minutes to serve a customer on an average. Assume that the arrivals joining in a queue will not be jockeying (i.e., move to another queue). How many counters have to be opened if the customers need not to wait for more than 15 minutes?
Solution: The problem is to be solved as one system comprising of 'n' number of single server queuing model.
Arrival rate, l =90 customers per hour
Service rate, μ = 60/5 =12 per hour
Average waiting time, Wq = 15/60 = 0.25 hours
Average waiting time, Wq = l/ m (m-l)
i.e., 0.25 = l/ m(m l) ................................(i)
Let, number of counters be x,
Considering the single server queuing system, the number of counters required to serve 90 arrivals per hour, l = 90/x substituting l = 90/x in equation (i),
Hence, 10 counters are required so that an average arrival will wait less than 15 minutes.
Example: In a single pump petrol station, vehicles arrive at the rate of 20 customers per hour and petrol filling takes 2 minutes on an average. Assume the arrival rate is Poisson probability distribution and service rate is exponentially distributed, determine
(a) What is the probability that no vehicles are in the petrol station?
(b) What is the probability that 1 customer is filling and no one is waiting in the queue?
(c) What is the probability that 1 customer is filling and 2 customers are waiting in the queue?
(d) What is the probability that more than 2 customers are waiting?
Solution : l = 20 vehicles per hour, μ = 60/2 = 30 vehicles per hour.