operations management
jenny2000000
15_QueuingTheory.pptxClass 15 Queuing Theory
Instructor: Mani Lakshmanan
P300 Introduction to Operations Management
Review: Variability in a System
Predictable variability
A regular or predictable pattern over time
Random (Stochastic) variability
No discernible pattern, unknown until it realizes
It’s common that both types of variability exist simultaneously
Customers demand for a type of product/service
Variability’s impact on the system
Waiting
Throughput Loss
Review: Variability + Utilization = Waiting
Synergy between variability and utilization:
Theoretical
Flow Time
Actual
Average
Cycle
Time,
W
Utilization
r
100%
Actual (average)
flowtime, T
variability
Demand Rate
Capacity Rate
=
Put it in another way. It just means that variability and utilization together will contribute to the long waiting. Graphically, let us show the relationship between the throughput and delay. Remember we now only consider the stable system, so demand rate is smaller than capacity rate. Our throughput rate is equal to demand rate. Given capacity rate, as demand rate increase, we will have utilization increase. So, we label the x-axis by utilization rho. For y-axis, it is ok for us to use actual flow time, since the delay is included in it.
If there is no variability, since utilization is smaller than 100%, there is no inventory shown up, no delay. The actual flow time is exactly equal to the theoretical flow time. But when there is variability, for a given utilization, we can find the inventory shown up, delay appeared. The actual flow time is longer than the theoretical flow time. So, in a variable system, the average cannot tell the whole story. In this case, average demand is smaller than the average capacity rate, but due to variability, inventory still occurs.
On the other hand, if we check the effect of utilization, we can find that the bigger the utilization, the longer the actual flow time. And such zooming effect is non-linear. This is a graphic presentation of PK formula.
Review: OM Triangle
Capacity
Inventory
Variability
reduction
Capacity, inventory, and variability reduction (information) are substitute ways to satisfy customers’ demand for products/services.
Waiting room for customers;
Products that can be sold to customers
Reduce both waiting time and throughput loss
Reduce throughput loss
today we are going to analyze the waiting line here in a service system.
Queuing (Waiting Line) Models
In the remaining time, we will just talk one thing. Waiting line models. This is a very important topic. The first thing we should do is to see how to specify a queuing model.
Components
Servicing System
Customer
Arrivals
Servers
Waiting Line
Exit
What do you care most if you are in a queue?
What does a manager care most if he/she is in charge of the service system?
A queuing system typically has three components. Customer arrivals, waiting line, and servers.
Outline
Different Structures of Queues
Number of phases
Number of channels
Number of queues
Priorities
Find the average queue length and waiting time
Apply M/__/__ queuing formulas
Structure of Queues: Phase
Services require a single activity or services of activities called phases.
In a single-phase system, the service is completed all at once
In a multiphase system, the service is completed in a series of phases
Structure of Queues: Channel
In queuing system, the terms server and channel are used interchangeably.
Single phase - Single server:
Single checkout counter in a gas station food mart
Single person selling tickets in a theater
Single phase - Multiple server:
Gas stations with multiple gas pumps
Grocery stores with multiple cashiers
Structure of Queues: Number of Queues
Single Queue
Fairness: First Come, First Served (FCFS)
Long waiting line may cause throughput loss
Multiple Queues
Option of selecting a particular server
Service may be differentiated
Line Jockeying: customer changes one line to another to reduce wait time
1
2
3
1
2
3
waiting before this line
Structure of Queues: Queuing Network
- Network of Processing Nodes
- Nodes with multiple servers/queues
- Dynamic product-specific (re)routing
- Examples: hospital, airport …
SubAssembly 1
SubAssembly 2
Final Assembly
...
...
...
Queuing system can be even more complex. Become something we call as queuing network. All of manufacture plants actually can be viewed as the queuing network.
Queue Priorities
A queue priority rule determines which customer is served next.
FCFS
Emergencies first
Shortest processing time first
Reservation first
Other priority systems
Shortest total waiting time
Outline
Different Structures of Queues
Number of phases
Number of channels
Number of queues
Priorities
Find the average queue length and waiting time
Apply M/__/__ queuing formulas
Description of a Queuing System Kendall’s Notation for Queue Model
___ / ___ / ___
Inter-arrival time M, D
Service time M, D
Number of channels / servers 1, c>1
M / M / 1
M / D / 1
M – Memoryless, Exponential Random Variable
D – Deterministic
M / M / c
Queue
Ok, we are ready to describe a queuing system. Typically we can use three notations to represent a queuing system. The first position is for arrival. We choose either M or D. If we choose M, that means, the interarrival time follows exponential distribution. If D, that means deterministic arrival, no variability are there. The second position is for service. Again we have M or D. M means service time follows exponential distribution, and D for deterministic service time. The third position means how many servers are there. Generally, we use c to imply there are more than 1 server. One thing I want to point it out is. Time follows Exponential distribution is equivalent to number follows Poisson distribution. Let me check if you understand it.
Model
Layout
Service Pattern
Single channel
Memoryless (Exponential)
Single channel
Deterministic
M/M/1
M/D/1
M/M/c
Multichannel
These three models share the following characteristics:
Queuing Models
Memoryless (Exponential)
Infinite source population
Interarrival times are Exponential random variable <- Memoryless
Single phase
Single queue
FCFS
Unlimited queue length, no throughput loss, customers join the queue and wait until they are served
This slide is a summary of three basic waiting line models. In the table, you will see their differences. Below the table, we can see their common characteristics.
Notation
l = arrival rate
m = service rate of a single server
c = number of identical service channels
l < cm stable system
= average number waiting in line
| Queuing Models | |
| M/M/1 | |
| M/D/1 | |
| M/M/c | use “15_Qformula.xlsm” to compute |
Let me summarize the notations we need. We use lamda for demand rate, mu for service rate. We always consider a stable system, that means our demand cannot be higher than the total service rate. n stands for number, t for time. Subscript l for line, and subscript s for system.
Professor holds office hours every Thursday to answer students’ questions. Students arrive at an average rate of 50 per hour. Assume arrivals are random. Professor can process students at an average rate of 60 per hour. Assume the time each student takes is also random.
Q1: What is the average number of students waiting outside Prof.’s office?
M/M/1:
= = 4.17
Example 1
Step 1. What model?
Step 2. Demand rate.
Step 3. Capacity rate.
Step 4. For system or for line
Step 5. Formulation.
Notation
l = arrival rate
m = service rate of a single server
c = number of identical service channels
l < cm stable system
= average number waiting in line
| Queuing Models | |
| M/M/1 | |
| M/D/1 | |
| M/M/c | use “15_Qformula.xlsm” to compute |
= average time waiting in line
Let me summarize the notations we need. We use lamda for demand rate, mu for service rate. We always consider a stable system, that means our demand cannot be higher than the total service rate. n stands for number, t for time. Subscript l for line, and subscript s for system.
Performance Measures
Queue Length: average # waiting in the queue
Inventory
Waiting Time: average time spent in the queue
Flow Time
Little's Law
Inventory = Throughput Rate * Flow Time
Queue Length = Arrival Rate * Waiting Time
These are some measures that we want to get from the queuing models. The first two are quite straightforward. Length and time. They are the things we repeat again and again till now. Also important is the utilization. As well as the probability whether an arrival have to wait. Why does the last one matter? Because there are always impatient customers They will leave whenever they see the server is occupied. And you immediately lose the sale. So this number will tell us what is the potential loss.
Professor holds office hours every Thursday to answer students’ questions. Students arrive at an average rate of 50 per hour. Assume arrivals are random. Professor can process students at an average rate of 60 per hour. Assume the time each student takes is also random.
Q1: What is the average number of students waiting outside Prof. Hu’s office?
Q2: How long do the students wait on average?
M/M/1:
nl = l2/[m(m-l)]
= 502/(60*10) = 4.17
tl = nl /l (Little’s Law)
= 4.17/50=0.083
Example 1
hr = 5min
Step 1. What model?
Step 2. Demand rate.
Step 3. Capacity rate.
Step 4. For system or for line
Step 5. Formulation.
Professor is concerned that students wait too long. As a remedy, he is considering installing an automatic device that can answer all students’ questions. The device would serve each student in exactly 1 minute.
Q3: If the device costs $10,000 and each minute saved from a student’s waiting time is worth $2, should the device be installed? Assume that a total of 1,500 students are served per year.
M/D/1:
tl = nl / l = l/ [2m (m-l)]
= 50/(2*60*10)=0.0417hrs=2.5mins
Savings = (5-2.5)*1500*$2=$7,500
< $10,000
Example 1
Review: Variability + Utilization = Waiting
Synergy between variability and utilization:
Theoretical
Flow Time
Actual
Average
Cycle
Time,
W
Utilization
r
100%
Actual (average)
flowtime, T
variability
Demand Rate
Capacity Rate
=
Put it in another way. It just means that variability and utilization together will contribute to the long waiting. Graphically, let us show the relationship between the throughput and delay. Remember we now only consider the stable system, so demand rate is smaller than capacity rate. Our throughput rate is equal to demand rate. Given capacity rate, as demand rate increase, we will have utilization increase. So, we label the x-axis by utilization rho. For y-axis, it is ok for us to use actual flow time, since the delay is included in it.
If there is no variability, since utilization is smaller than 100%, there is no inventory shown up, no delay. The actual flow time is exactly equal to the theoretical flow time. But when there is variability, for a given utilization, we can find the inventory shown up, delay appeared. The actual flow time is longer than the theoretical flow time. So, in a variable system, the average cannot tell the whole story. In this case, average demand is smaller than the average capacity rate, but due to variability, inventory still occurs.
On the other hand, if we check the effect of utilization, we can find that the bigger the utilization, the longer the actual flow time. And such zooming effect is non-linear. This is a graphic presentation of PK formula.
The self-checkout system in Kroger has 6 serving stations. The time it takes for a customer to checkout through a single station is random, with an average of 3 minutes. Assume customers arrive to the system with an average rate of 1.5 customers/minute.
Q1: What is the average number of customers waiting in front of the system, and how long do they wait on average?
M/M/6:
tl = nl / l
= 1.25 customers / 1.5 customers/min=0.83min
Example 2
nl = 1.25 customers
Use the template provided
All of a sudden, one of the 6 checkout station is out of order.
Q2: Now, what is the average number of customers waiting in front of the system, and how long do they wait on average?
M/M/5:
tl = nl / l
= 6.9customers / 1.5 customers/min=4.6min
Example 2
nl =6.83customers
Use the template provided
Assume that each minute from a customer’s waiting time cost Kroger $1 (“goodwill cost”).
Q3: How much money per hour does this out-of-order station cost?
Goodwill cost = (4.6-.85) *$1*1.5*60=$337.5
Web page Information and Excel file for calculating the M/M/C problems
Web links If the hyper link does not work Copy and paste the link in a browser .
http://www.supositorio.com/rcalc/rcalclite.htm
http://www.onlinecalculatorfree.org/queueing-theory-calculator.html#.VhqVRHpViko
http://people.revoledu.com/kardi/tutorial/Queuing/MMs-Queuing-System.html
