Transcript Slide 1

COUNTING PROCESSES
Very important modelling concept
e.g….
Arrival
Arrival
Arrival
Arrival
of
of
of
of
a product at a machine
emails to a server
calls to a call centre
a signal to a processor
Described by a counting function N (t) for all t ≥ 0
-Counts how often events occur over time
-Generally, A system that is characterized by customers contending for a
resource, called a server, is a queuing system, or counting process.
20/07/2015
ENGN8101 Modelling and Optimization
1
N(t), t ≥ 0 = a counting process
Assume:
1. Arrivals occur one at a time
2. Arrivals are completely random
– without rush or slack periods (memoryless)
3. All arrivals are independent
Then counting process → Poisson process
So
e  t (t ) n
P( N (t )  n) 
n!
Poissonian
Mean and variance = λt
20/07/2015
ENGN8101 Modelling and Optimization
2
If first arrival = at time A1, second one at time A1+A2 etc..
Then
P(A1 ≤ t ) = 1-e-λt
i.e. A1 = exponentially distributed with mean = 1/λ
Also – all interarrival times A1, A2….
exponentially distributed with mean = 1/λ
If independent and memoryless – we have a Poisson process
Often used to trade off server utilization with customer satisfaction
In terms of line lengths and delays
20/07/2015
ENGN8101 Modelling and Optimization
3
CHARACTERISTICS OF QUEUEING SYSTEMS
Key elements – customers and servers – very generic
Simplest system:
Population of customers = calling population – finite or infinite
20/07/2015
ENGN8101 Modelling and Optimization
4
Example scenario:
A set of 5 machines that process (cure) tires
After t = ? – a machine opens and a worker removes a tire and
loads an uncured tire and closes the machine
Machines = customers who arrive at a rate dependent on the
distribution of the t = ? Values
Worker = server
calling population = 5
Arrival rate = expected number of arrivals in next time unit
 If all 5 machines are closed – arrival rate = maximum
20/07/2015
ENGN8101 Modelling and Optimization
5
Note:
Infinite populations – arrival rates usually modelled as constant
Finite populations – other statistical models used
SYSTEM CAPACITY
Defined when number of customers in the waiting line or system
is limited
e.g. with space constraints
Define arrival rate
(no. of arrivals)
20/07/2015
+
effective arrival rate
(no. of arrivals that enter system)
ENGN8101 Modelling and Optimization
6
Properties of the Poisson process
Random splitting
A Poisson process of rate λ – may have 2 event types (I and II)
of probabilities (P) and (1-P)
N1(t) = random variable for number of type I events
N2(t) = random variable for number of type II events
Such that
N(t) = N1(t) + N2(t)
Then….
20/07/2015
ENGN8101 Modelling and Optimization
7
Both are also Poisson processes
with rates λP and λ(1-P)
Reverse is also true = ‘pooled process’
e.g.
2 Poisson arrival streams of rates λ1 = 10/hour and λ2 = 17/hour
are combined at a system entity and moved on
Result = Poisson process of λ=27/hour
20/07/2015
ENGN8101 Modelling and Optimization
8
QUEUEING MODELS
Queueing models – most common model in engineering
‘Something arrives at an entity, waits, then goes through’
e.g.
server utilization, waiting times, delays, starvation, bottlenecks
etc.
Equally important in manufacturing, electrical and
computer systems etc.
What happens if a system is full?
- Customers either form a queue or are turned away
20/07/2015
ENGN8101 Modelling and Optimization
9
Arrival Processes
Infinite populations – customers may arrive in a random
manner, individually or in groups (batches)
- modelled using probability distributions
Most important model = the Poisson process
An = interarrival time between customers n-1 and n
An = exponentially distributed with mean of 1/λ time units
(arrival rate is λ customers per time unit)
Number of arrivals in time interval t = N(t)
is Poisson with a mean of λt customers
Very reliable and easy to model
20/07/2015
ENGN8101 Modelling and Optimization
10
Proven examples:
restaurants, banks, call centres, machine failures etc.
Finite populations?
Here – customers are pending or non-pending
Returning to the tire system…..
Pending = machine curing (tire not ready yet)
Non-pending = instant the machine is open + demands service
from the worker
Also – define runtime
Runtime for a customer = time from departure from the queue
to their next arrival to the queue
20/07/2015
ENGN8101 Modelling and Optimization
11
Let A1(i), A2(i) etc = successive runtimes of customer i
Let S1(i), S2(i) etc. = corresponding successive system times
Then – for our example (machine 3 as an illustration):
In the total system – A1 will be
min{ A1(1), A1(2), A1(3), A1(4), A1(5)}
Arrival rate is not constant
– dependent on number of pending customers
20/07/2015
ENGN8101 Modelling and Optimization
12
Best example – repair of a failed system entity
Here –
Customers = system entity
Runtime = time to failure
Entity fails – arrives at queueing system (repair facility)
until served (repaired)
Exponential, gamma, Weibull distributions – used to model
distribution of failure times which are assumed to be
independent (not always true e.g. age etc.)
20/07/2015
ENGN8101 Modelling and Optimization
13
QUEUE BEHAVIOUR
When in a queue – a customer can:
Wait until called
Balk (leave if line is too long)
Renege (leave if line is moving too slowly)
Jockey (switch from line to line if moving at different rates)
Good example – passport line at an airport
Queue can be dealt with:
On a first-in-first-out basis (FIFO)
Last-in-first-out basis (LIFO)
Service in random order (SIRO)
Shortest processing time first (SPT)
Service according to priority (PR)
20/07/2015
ENGN8101 Modelling and Optimization
14
System structure
Queueing system:
number of service centres + interconnecting queues
each service centre has c servers working in parallel
customer takes first available server
Parallel service centres – either
single
multiple
unlimited
c=0
c=>1
c=∞
Self-service facility = unlimited
20/07/2015
ENGN8101 Modelling and Optimization
15
EXAMPLE – discount warehouse where customers either serve
themselves or wait for one of three clerks. Then pay through a
single cashier
1 subsystem:
Queueing issues?
20/07/2015
Splitting?
Pooling?
ENGN8101 Modelling and Optimization
16
QUEUEING NOTATION
Many diverse queueing systems – need comprehensive notation
KENDALL notation
A/B/c/N/K system
A = interarrival time distribution
B = service-time distribution
c = number of parallel servers
N = system capacity
K = size of calling population
A, B: M (exponential or Markov), D (constant or deterministic)
G (arbitrary or general), Ek (Erlang of order k) etc.
20/07/2015
ENGN8101 Modelling and Optimization
17
Examples
M/M/1/∞/∞
Single-server system that has unlimited queue capacity +
infinite population of potential arrivals. Interarrival and service
times are exponentially distributed
Also designated M/M/1
Tire curing system?
G/G/1/5/5 system
Notation assumes a FIFO queue discipline unless told otherwise
20/07/2015
ENGN8101 Modelling and Optimization
18
Long-term performance measures
for queueing systems
Queueing ‘system’ = waiting line + service mechanism
‘Queue’ = waiting line only
For a time-dependent system – three phases:
1. Switching on; warming up; ramp-up; beginning…
2. Steady-state long-term use
3. Winding down; switching off; closure etc…
Queueing theory applies to steady state behaviour
20/07/2015
ENGN8101 Modelling and Optimization
19
Pn
Pn(t)
λ
λe
μ
ρ
An
Sn
Wn
WnQ
L(t)
LQ(t)
L
LQ
w
wQ
steady-state probability of having n customers in system
probability of n customers in system at time t
arrival rate
effective arrival rate
service rate of one server
server utilization
interarrival time between customers n-1 and n
service time of the nth arriving customer
total time spent in system by nth arriving customer
total time spent in the waiting line by customer n
the number of customers in system at time t
the number of customers in queue at time t
Long-run time average number of customers in system
Long-run time average number of customers in queue
Long-run average time spent in system per customer
Long-run average time spent in queue per customer
20/07/2015
ENGN8101 Modelling and Optimization
20
L
Long-run time average number of customers in system
A system over time T : Ti when i customers are in the system
Here
So:

 Ti 
L   i 
i 0  T 

where

L
is an estimator of L

L  [0(3)  1(12)  2(4)  3(1)] / 20  23 / 20  1.15 customers
20/07/2015
ENGN8101 Modelling and Optimization
21
w
average time spent in the system per customer
As an estimate:

1
w
N
N
W
i 1
i
Where Wi = time spent in system by customer I
and N = number of arrivals over the measured time period
In steady state conditions, as N → ∞,  → w
w
Previous example – assume FIFO arrangement:
Customer
Customer
Customer
Customer
Customer
20/07/2015
1
2
3
4
5
arrives
arrives
arrives
arrives
arrives
at
at
at
at
at
t=0 and leaves at t=2
t=3 and leaves at t=8
t=5 and leaves at t=10
t=7 and leaves at t=14
t=16 and leaves at t=20
ENGN8101 Modelling and Optimization
22
So
2  5  5  7  4 23
wˆ 
  4.6
5
5
As for time spent in the waiting line:
wˆ Q 
0 033 0 6
 1.2
5
5
Little’s Law
From our system: N = 5 arrivals, T = 20 time units
So arrival rate, λ = 5/20 = ¼ customer per time unit
ˆ  4.6
From before: Lˆ  1.15 and w
So
20/07/2015
Lˆ  ˆwˆ
- Little’s Law of conservation – important!
ENGN8101 Modelling and Optimization
23
ρ
server utilization
= proportion of time between 0 and T that the server is busy
Again, at steady-state:
Very dependent on type of system…
G/G/1/∞/∞ queues
Any single-server queue system of arrival rate λ per time unit
Average service time = E(S) = 1/μ time units
 When busy – server works at rate of μ customers/time unit
μ = service rate
20/07/2015
Little’s Law is valid
ENGN8101 Modelling and Optimization
24
Actual number of customers in the server = 0 or 1
(rest are in the queue)
Our example again…..
T  T0 17
Now L = merely

 ˆ
T
20
Combining into Little’s Law gives   E (S )  

And is always less than 1 in stable situations
20/07/2015
ENGN8101 Modelling and Optimization
25
G/G/c/∞/∞ queues
Here - ρ = Ls /c = λ/cμ
Where Ls = average number of busy servers (0≤Ls≤c) =
Maximum service rate = cμ – when all servers are busy
To be stable: λ < cμ – otherwise a queue will grow
CASE STUDY Q1
Customers arrive at random to a license bureau at a rate of λ = 50 customers per hour.
Currently, there are 20-clerks, each serving μ=5 customers per hour on the average.
What is the long-run average utilization of a clerk and what is the average number of
busy clerks per hour

50

 0.5
c 20(5)
Each clerk is busy 50% of the time
 50
Ls   10
 5
On average – 10 clerks are being used
 - what would be a good number?

20/07/2015
ENGN8101 Modelling and Optimization
26
D/D/1 example
Consider a doctor who schedules patients every 10 minutes
and who spends Si minutes with the ith patient where
 9 minuteswith probability 0.9
Si  
12 minuteswith probability 0.1
Arrivals are deterministic (constant) with λ-1 = 10 = E(A)
Service time mean of E(Si) = 9(0.9) + 12(0.1) = 9.3 minutes
and variance:
V(Si) = E(Si2) – [E(Si)]2
= 92(0.9) + 122(0.1) – (9.3)2 = 0.81 mins
So
ρ = λ/μ = E(S)/E(A) = 9.3/10 = 0.93
20/07/2015
ENGN8101 Modelling and Optimization
27
Steady-state prediction of Markovian queues
i.e. anything with an ‘M’ in it….
If population = infinite
arrivals assumed to follow Poisson behaviour with
λ arrivals per time unit, and interarrival times that
are exponential with mean = 1/λ
service times – exponential or arbitrary (M or G)
If queue discipline =FIFO
A Markovian model results
20/07/2015
ENGN8101 Modelling and Optimization
28
Main Markovian property = memoryless
i.e. state of system is time independent
A good analysis – especially for long-term behaviour
i.e. steady state
These are mathematical models
not simulation models
Difference?
read up!
20/07/2015
ENGN8101 Modelling and Optimization
29
M/G/1 system
Interarrival times = 1/λ
1 server – service times of mean 1/μ and variance σ2
Under steady state
– we have:



L
2 (1 /  2   2 )
 2 (1   2  2 )


2(1   )
2(1   )
w
 (1 /  2   2 )


2(1   )
wQ 
 (1 /  2   2 )
2(1   )
LQ 
P
20/07/2015
1
2 (1 /  2   2 )  2 (1   2  2 )

2(1   )
2(1   )
1 
0
ENGN8101 Modelling and Optimization
30
CASE STUDY Q2
Widget-making machines malfunction apparently at random and then require a
mechanic’s attention. It is assumed that malfunctions occur according to a Poisson
process, at the rate of 1.5 per hour. Observation over several months has found that
repair times by the single mechanic take on average, 30 minutes, with a standard
deviation of 20 minutes. During steady state operation, how many machines on
average are broken?
λ = 1.5 per hour
1/μ = ½ hour
σ2 = 400mins2
Ρ = λ/μ = 0.75
Consistency of units!
L
σ2 = 1/9 hour2
2 (1 /  2   2 )
(1.5) 2 [(0.5) 2  1 / 9]

 0.75 
 2.375machines
2(1   )
2(1  0.75)
At any instant in steady-state time, 2.375 machines are broken
20/07/2015
ENGN8101 Modelling and Optimization
31
LQ – also written as
2
2 2
LQ 

2(1   ) 2(1   )
Analysis of this shows that waiting lines (hence – delays)
are mostly dependent on σ2
variability of service times has
biggest effect on queues and delays
20/07/2015
ENGN8101 Modelling and Optimization
32
CASE STUDY Q3
There are two workers competing for a job, Fred and Bod. Fred claims an average
service time that is faster than Bod’s, but Bod claims to be more consistent, even if
not as fast. The arrivals occur according to a Poisson process at a rate of 2 per hour
(λ). Fred’s service statistics are an average service time of 24 minutes with a standard
deviation of 20 minutes. Bod’s service statistics are an average service time of 25
minutes with a standard deviation of 2 minutes. If the average length of the queue is
the criterion for hiring, which worker should be hired?
λ = 1/30 per minute 1/μ = 24 minutes
σ2 = 400 minutes2
ρ = λ/μ = 24/30 = 0.8
(1 / 30) 2 [242  400]
average queue length = LQ 
 2.711 customers
2(1  0.8)
For Fred,
For Bod,
λ = 1/30 per minute 1/μ = 25 minutes
ρ = λ/μ = 25/30 = 0.84
σ2 = 4 minutes2
(1 / 30) 2 [252  4]
average queue length = LQ 
 2.097 customers
2(1  0.84)
Although faster, Fred’s greater service variability results in an average queue length
about 30% bigger than Bod’s. Alternately, the probability of an arrival finding the
workers idle, and experience no delay (P0 = 1-ρ) is 20% for Fred and only 16.7% for
Bod
Highlights the critical nature of variability to the system and also the importance interpreting the
various answers from the analysis
20/07/2015
ENGN8101 Modelling and Optimization
33
M/M/1 system
Service times = exponential (mean = 1/μ) variance = σ2 = 1/μ2
Good when standard deviations approximate to the mean
L
w



   1 
1
1

    (1   )
wQ 



 (    )  (1   )
2
2
LQ 

 (   ) 1  
n
    
Pn  1     (1   )  n
    
20/07/2015
ENGN8101 Modelling and Optimization
34
CASE STUDY Q4
Suppose that the interarrival times and service times at a single-chair unisex hairstyling shop have been shown to be exponentially distributed. The values of λ and μ
are 2 per hour and 3 per hour respectively – that is, the time between arrivals averages
½ hour, exponentially distributed, and the service time averages 20 minutes, also
exponentially distributed. What is the server utilization and what are the probabilities
of seeing 1, 2, 3 or 4 or more customers in the shop?
Here, λ = 2/hour
Utilization
μ = 3/hour
ρ = λ/μ = 2/3
How many customers are in the shop at any one time?
n
Use
P0 = 0.33
    
Pn  1     (1   )  n
    
P1 = 0.22
P2 = 0.15
P3 = 0.1 P4 = 0.2
Also – the hairstylist is idle 33% of the time (1-ρ)
20/07/2015
ENGN8101 Modelling and Optimization
35
Average number of customers:

2
L

 2 customers
  3 2
Average time spent in the system:
L
2
w    1 hour
 2
Average time spent in the queue per customer:

2/3
wQ 

 2 / 3 hour
 (1   ) 3(1 / 3)
Average number of customers in the queue:
2
4
LQ 

 4 / 3 customers
 (   ) 3(1)
20/07/2015
ENGN8101 Modelling and Optimization
36
EFFECT OF UTILIZATION AND SERVICE VARIABILITY
In any M/G/1 queue..
line size reduced by decreasing server utilization
or service time variability σ2
Reduce ρ by:
decreasing arrival rate λ
increasing service rate μ
increasing no. of servers c
Regarding σ2 – can define the coefficient of variation (cv)
(cv) 2 
V (X )
[ E ( X )]2
In exponential case: E(X) = 1/μ and V(X) = 1/μ2
cv=1
20/07/2015
ENGN8101 Modelling and Optimization
37
Interestingly – for an M/G/1 queue:
  2  1  (cv ) 2 


LQ  
2
 1   

M/M/1 model
correction factor
True for other parameters
An M/G/1 queue is basically a M/M/1 queue with extra variation
20/07/2015
ENGN8101 Modelling and Optimization
38
Multiserver queue – M/M/c
Here – the parameters are complex:


c
and
(c ) c P0
P ( L ( )  c ) 
c!(1   )
L
w
and

P( L()  c)
LQ 
1 
20/07/2015
 (c )  

c 1  1 
P0  
  (c )  

n
!
c
!
1


 

 
 n 0
c 1
and
L  c 
wQ  w 
and
n
1
P( L()  c)
1 
1

L  LQ  c
ENGN8101 Modelling and Optimization
39
P0 = complex expression – but often graphed
20/07/2015
ENGN8101 Modelling and Optimization
40
Also – L:
20/07/2015
ENGN8101 Modelling and Optimization
41
CASE STUDY Q5
Many early examples of queueing theory applied to practical problems concerning
tool cribs. Attendants manage the tool cribs as mechanics, assumed to be from an
infinite calling population, arrive for service. Assume Poisson arrivals at a rate of 2
mechanics per minute and exponentially distributed service times with a mean of 40
seconds.
Now, λ = 2 per minute and μ = 60/40 = 3/2 per minute, so λ/μ = 2/(3/2) = 4/3.
Thus, the utilization is greater than 1, so more than 1 server is required if the system is
to have steady state equilibrium. In this case, as the utilization lies between 1 and 2,
c=2 will suffice.
The quantity 4/3 is the expected number of busy servers, and for c≥2, ρ = 4/(3c) is the
steady state utilization of each server.
20/07/2015
ENGN8101 Modelling and Optimization
42
If there are c = 2 attendants, then P0 is calculated as 0.2
The probability that all servers are busy = P(L(∞) ≥ 2) = 0.533
Thus the time-average length of the waiting line of mechanics = LQ = 1.07 mechanics
and the time-average number of mechanics in the system
= L = 1.07 + 4/3 = 2.4 mechanics
From Little’s Law: the average time a mechanic spends at the tool crib is
w = L/λ = 2.4/2 = 1.2 minutes
and the average time spent waiting for an attendant is
wQ = w – 1/μ = 1.2 – 2/3 = 0.533 minutes
20/07/2015
ENGN8101 Modelling and Optimization
43