finish the document “Queuing Problem”
Queuing Problems
1. Sharp Discounts Wholesale Club has two service desks, one at each
entrance of the store. Customers arrive at each service desk at an
average of one every six minutes. The service time at each service desk is
four minutes per customer.
a) How often (what percentage of time) is each service desk idle?
b) What is the probability that both service clerks are busy?
c) What is the probability that both service clerks are idle?
d) How many customers, on average, are waiting in line in front of each service
desk?
e) How much time does a customer spend at the service desk (waiting plus
service time)?
2. Burrito King (a new fast food franchise opening up nationwide) has
successfully automated burrito production for its drive-up fast food
establishments. The Burro-Master 9000 requires an average service time of
45 seconds, exponentially distributed, to produce a batch of burritos. It has
been estimated that customers will arrive at the drive-up window according to a
Poisson distribution at an average of one every 50 seconds. To help determine
the amount of space needed for the line at the drive-up window, Burrito
King would like to know the expected average time in the system, the
average line length (in cars), and the average number of cars in the system
(both in line and at the window).
3. The Bijou Theater in Hermosa Beach, California, shows vintage movies.
Customers arrive at the theater line at the rate of 100 per hour. The ticket
seller averages 30 seconds per customer, which includes placing validation
stamps on customers’ parking lot receipts and punching their frequent
watcher cards. (Because of these added services, many customers don’t
get in until after the feature has started.)
a) What is the average customer time in the system?
b) What would be the effect on customer time in the system of having a second
ticket taker doing nothing but validations and card punching, thereby cutting the
average service time to 20 seconds?
c) Would system waiting time be less than you found in b) if a second window
was opened
with each server doing all three tasks?
Where Does Variability Exist In Operations?
1
1
Where Does Variability Exist In Operations?
Demand
Operation Completion
Transport
Labor
Machine Downtime
Raw Material Quality
2
2
How Does Variability Affect Operations?
Capacity?
Utilization?
Efficiency?
Throughput Time?
Cost?
3
3
Tools For Capacity Planning With Variability
Without Variability – Long Division
With Variability:
Linear Programming – to allocate capacity over multiple facilities or multiple time periods
Simulation – model any complex system using random numbers
4
4
New Tool:
Queueing Models
Mathematical analysis of waiting line systems of all types
Fast
Little data needed
5
5
Why Do Queues Exist?
6
6
Why Do Queues Exist?
They are due to short run variations in demand and capacity
To understand how much additional capacity we need, we need to understand queues
But are all queues the same?
7
7
Elements of A Queueing System
Customers (Orders, Raw or WIP Materials, etc.) arrive according to a known or predictable random process – Arrival (or birth) Process
Arrivals wait (literally or figuratively) in line to be serviced – Queue
Arrivals are selected out of the line according to a rule such as first come first serve – Queue Discipline
Customers enter service from queue then exit system when service is complete – Service (or Death) Process
8
8
Elements of A Queueing System
Queue Structure
Single Line
Single Queue/Single Server or
Single Queue/Multiple Server
Parallel Lines – Multiple Single Queue/Single Server Lines
Stages Service – A Sequence of operations each with a queue
9
9
Elements of A Queueing System
Service Order
First Come First Served
Last Come First Served
Random Order
Shortest Processing Time First
Priorities
Appointments/Due Dates
10
10
Data/Facts You Need For A Queueing Model
Customer Arrival Rate – Average number of customers arriving per time period
Service Time – Average time a server takes to service a customer
Service Rate – Average number of customers a server can serve per unit of time
Number of Servers
Queue Structure
Queue Discipline
11
11
Random Arrival Process
Poisson Process
Arrivals are independent of one another
Average arrival rate is constant over period of analysis
Arrivals occur one at a time
Number of arrivals in an interval is described by a Poisson distribution
The time between arrivals is described by an Exponential Distribution
12
12
Definitions
λ – Average arrival rate: The number of customers arriving per unit time
μ – Average service rate: The number of customers a server can serve per unit time
– Average service time: Average time to serve one customer by one server
13
13
Average Time Spent In The Queue
Average Time In System (Time in queue plus time in service)
Average Length Of Queue
Average Number Of Customers In The System
Probability That A Customer Waits Before Service Begins (Probability of a Delay)
Server Utilization
14
Some Performance Measures
14
Simple Formulae For Simple Case
Single Queue/ Single Server/FCFS
Utilization () Equals average arrival rate over average service rate
Average Time In The System
Average Number In System
15
15
Formula… cont’d.
Average Time In The Queue
Average time in system minus average time in service
Average Number In The Queue
16
16
Multiple Servers
Formulae Are More Complicated
Utilization () Equals average arrival rate over number of servers (S) times average service rate
All performance measures can be obtained by using MMs Excel spreadsheet on Courseworks
17
17
Multiple Servers/Single Queue Formulae
Find Lq from Table
18
18
Example
The manager of a store has two clerks in different parts of store. λ of 15 Overall
Same as two single server queues each with λ of 7.5 customers per hour
μ = 15 per Hour
19
19
Measures For This Alternative:
2 Single Queue Single Server
For Each
Number in Queue:
Number in System: customer at each place
Time in System: hour or 8 minutes
Time in Queue: hour or 4 minutes
For Entire System
Time in System = 8 minutes
Number in System = 2 customers
Time in Queue = 4 minutes
Number in Queue = 1 customer
20
20
Multiple Server / Single Queue
Put the two clerks together
Have customers form one line that feeds the two servers
Calculate measures of performance
21
21
Multiple Servers Measures:
Single Queue Two Servers
λ = 15 per Hr
μ = 15 per Hr
Number of Servers = 2
Utilization = 15/2*15 = 50% – Same
Number In Queue: Lq = From Table for 15/15 and 2 Servers = 0.333 cust.- Better
Time In Queue = Wq = 0.333/15 Hrs = 1.33 min – Better
Number In System = Ls = 0.333+(15/15) = 1.333 – Better
Time In System = Ws = 1.333/15 Hrs or 5.33 min. – Better
22
22
Another Example
The Manager of the Store Has Another Choice. He Can Have:
One Fast Check Out Clerk Who Can Process One Customer Every Two Minutes or
Two Moderately Fast Clerks Who Can Each Service A Customer In Four Minutes.
Which Alternative Is Better? (Assume Customers Arrive Randomly at the Rate of 15 per Hour in Each Case.)
23
23
Single Server Measures:
Single Queue Single Server
λ = 15 per Hour
μ = 30 per Hour (One Every Two Min.)
Utilization = 15/30 = 50%
Time In System = 4 Minutes
Average Number in System = 1 Customer
Average Wait in Queue = 2 Minutes
Average Number in Queue = 0.5 Customers
24
24
Multiple Servers Measures:
Single Queue Two Servers
λ = 15 per Hr
μ = 15 per Hr
Number of Servers = 2
Utilization = 15/2*15 = 50% – Same
Time In System = 5.33 min. – Worse
Number In System = 1.33 cust. – Worse
Time In Queue = 1.33 min. – Better
Number In Queue = 0.33 cust. – Better
25
25
Mathematical Lessons About Queueing Theory
λ must be less than μ per server times the number of Servers ()
If λ is well below , waiting times are low – Customer is happy, but utilization is low – boss sees waste
If λ is close to , waiting times are high – customer is unhappy, but utilization is high – workers are busy
For multiple servers, better to have single queue
If not FIFO, order by expected time of completion – good for most but bad for the longest
26
26
More Lessons
For series or networks, look for weakest link, balance network
In low utilization systems (Emergency Response) find something else for them to do
Special queues for special needs
27
27
mms
| mms.xls M/M/s Queueing Formula Spreadsheet | |||||||||||
| Inputs: | Definitions of terms: | ||||||||||
| lambda | 0.1 | lambda = arrival rate | |||||||||
| mu | 0.3 | mu = service rate | |||||||||
| s = number of servers | |||||||||||
| Lq = average number in the queue | |||||||||||
| Ls = average number in the system | |||||||||||
| Wq = average wait in the queue | |||||||||||
| Ws = average wait in the system | lambda/mu | ||||||||||
| P(0) = probability of zero customers in the system | 0.33333333333333337 | ||||||||||
| P(delay) = probability that an arriving customer has to wait | |||||||||||
| Outputs: | Intermediate Calculations: | ||||||||||
| s | Lq | Ls | Wq | Ws | P(0) | P(delay) | Utilization | (l/u)^s/s! | sum (l/u)^s/s! | ||
| 0.0 | 1.0 | 1.0 | |||||||||
| 1.0 | 0.1667 | 0.5000 | 1.6667 | 5.0000 | 0.6667 | 0.3333 | 0.3333 | 0.33333333333333337 | 1.3333333333333335 | ||
| 2.0 | 0.0095 | 0.3429 | 0.0952 | 3.4286 | 0.7143 | 0.0476 | 0.1667 | 0.055555555555555566 | 1.388888888888889 | ||
| 3.0 | 0.0006 | 0.3340 | 0.0062 | 3.3396 | 0.7164 | 0.0050 | 0.1111 | 0.006172839506172842 | 1.395061728395062 | ||
| 4.0 | 0.0000 | 0.3334 | 0.0004 | 3.3337 | 0.7165 | 0.0004 | 0.0833 | 5.144032921810702E-4 | 1.395576131687243 | ||
| 5.0 | 0.0000 | 0.3333 | 0.0000 | 3.3334 | 0.7165 | 0.0000 | 0.0667 | 3.429355281207135E-5 | 1.3956104252400552 | ||
| 6.0 | 0.0000 | 0.3333 | 0.0000 | 3.3333 | 0.7165 | 0.0000 | 0.0556 | 1.9051973784484087E-6 | 1.3956123304374337 | ||
| 7.0 | 0.0000 | 0.3333 | 0.0000 | 3.3333 | 0.7165 | 0.0000 | 0.0476 | 9.072368468801947E-8 | 1.3956124211611185 | ||
| 8.0 | 0.0000 | 0.3333 | 0.0000 | 3.3333 | 0.7165 | 0.0000 | 0.0417 | 3.7801535286674784E-9 | 1.395612424941272 | ||
| 9.0 | 0.0000 | 0.3333 | 0.0000 | 3.3333 | 0.7165 | 0.0000 | 0.0370 | 1.4000568624694365E-10 | 1.3956124250812778 | ||
| 10.0 | 0.0000 | 0.3333 | 0.0000 | 3.3333 | 0.7165 | 0.0000 | 0.0333 | 4.666856208231456E-12 | 1.3956124250859447 | ||
| 11.0 | 0.0000 | 0.3333 | 0.0000 | 3.3333 | 0.7165 | 0.0000 | 0.0303 | 1.4141988509792291E-13 | 1.3956124250860862 | ||
| 12.0 | 0.0000 | 0.3333 | 0.0000 | 3.3333 | 0.7165 | 0.0000 | 0.0278 | 3.928330141608971E-15 | 1.3956124250860902 | ||
| 13.0 | 0.0000 | 0.3333 | 0.0000 | 3.3333 | 0.7165 | 0.0000 | 0.0256 | 1.0072641388740952E-16 | 1.3956124250860902 | ||
| 14.0 | 0.0000 | 0.3333 | 0.0000 | 3.3333 | 0.7165 | 0.0000 | 0.0238 | 2.398247949700227E-18 | 1.3956124250860902 | ||
| 15.0 | 0.0000 | 0.3333 | 0.0000 | 3.3333 | 0.7165 | 0.0000 | 0.0222 | 5.329439888222727E-20 | 1.3956124250860902 | ||
| 16.0 | 0.0000 | 0.3333 | 0.0000 | 3.3333 | 0.7165 | 0.0000 | 0.0208 | 1.1102999767130683E-21 | 1.3956124250860902 | ||
| 17.0 | 0.0000 | 0.3333 | 0.0000 | 3.3333 | 0.7165 | 0.0000 | 0.0196 | 2.1770587778687616E-23 | 1.3956124250860902 | ||
| 18.0 | 0.0000 | 0.3333 | 0.0000 | 3.3333 | 0.7165 | 0.0000 | 0.0185 | 4.031590329386596E-25 | 1.3956124250860902 | ||
| 19.0 | 0.0000 | 0.3333 | 0.0000 | 3.3333 | 0.7165 | 0.0000 | 0.0175 | 7.072965490151924E-27 | 1.3956124250860902 | ||
| 20.0 | 0.0000 | 0.3333 | 0.0000 | 3.3333 | 0.7165 | 0.0000 | 0.0167 | 1.1788275816919872E-28 | 1.3956124250860902 | ||
| 21.0 | 0.0000 | 0.3333 | 0.0000 | 3.3333 | 0.7165 | 0.0000 | 0.0159 | 1.871154891574583E-30 | 1.3956124250860902 | ||
| 22.0 | 0.0000 | 0.3333 | 0.0000 | 3.3333 | 0.7165 | 0.0000 | 0.0152 | 2.8350831690523986E-32 | 1.3956124250860902 | ||
| 23.0 | 0.0000 | 0.3333 | 0.0000 | 3.3333 | 0.7165 | 0.0000 | 0.0145 | 4.108816187032462E-34 | 1.3956124250860902 | ||
| 24.0 | 0.0000 | 0.3333 | 0.0000 | 3.3333 | 0.7165 | 0.0000 | 0.0139 | 5.706689148656198E-36 | 1.3956124250860902 | ||
| 25.0 | 0.0000 | 0.3333 | 0.0000 | 3.3333 | 0.7165 | 0.0000 | 0.0133 | 7.608918864874932E-38 | 1.3956124250860902 | ||
Queuing Models ( A = arrival rate; p = service rate)
Mfl/1 Queue
++++.) –
Anivals
Expected number in system: A L =-
P – A
Expected number in queue: L, =
A
P(P – A)
1 Expected waiting time (includes service time): W = –
C L – A
Expected time in queue:
Probability that the system is empty:
M/G/l Queue
+ + + + + –
Arrivals
Expected number in system:
Expected number in queue: L, =
AZcr2 + (Alp)’
2(1 – Alp)
I
Expected waiting time (includes service time): W = Wq + –
CL
L
Expected time in queue: Wq = A
Probability that the system is empty:
M ! / s Queue
Arrivals
Expected number in system:
Expected number in queue:
Expected waiting time
(includes service time):
Expected time in queue:
probability that the system is empty:
