image/svg+xml
customer
arrival time
service time
Standard assumptions
- Curse of dimensionality
state:
Higher dimensional Markov models
Computational approach to
“rate in = rate out” equations
Truncate an infinite number of equations
Algebraic formulation
Higher dimensional Markov models
Classical analysis: M/M/n system
- Throughout this talk, we use
For sufficiently large t
Key challenge:
No longer independent Poisson
We start with a discrete service-time distribution:
Number in system X(t)
This suggests
for some quantile
cross-covariances
.
where
Remark:
Iglehart 1965
Borovkov 1967
M/G/
Implication:
G/G/
Factory Physics (Hopp/Spearman 2011) proposes Sakasegawa:
Suggested approximation:
We seek the smallest
search over n yields
search over n yields
12am
5am
10am
3pm
8pm
1am
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
Manhattan 2006, health.ny.gov
310 arrivals per week
our data
0
2
4
6
8
10
12
14
E(S) = 4.43 hours
= 0.51
(in simulation: lognormal)
Cochran/Roche 2009
Inpatients in an emergency department
Here: assume nonhomogeneous Poisson arrivals
Goal:
Goal:
where, for an interarrival time T,
On a popular formula for manufacturing applications
G/G/n
* Any distribution can be approximated as closely as desired
Objective: Approximate the steady-state waiting time distribution
System equations approach for G/M/n: overview
Suppose
Arrival and service time data (sample path):
Overview of STEP 1
Represent system dynamics (randomness) via an analytically tractable “system equation”
= number in the system at time
= service rate when i in system
Summary of STEP 1 so far
Overview of STEP 2
Translate system equation to stochastic differential equation
system equation (SE)
stochastic integral equation
STEP 3
Solve the limiting steady-state distribution for number in system,
STEP 4
Approximate waiting time distribution via a “distributional Little’s law”
number in queue = arrival rate x waiting time
“Halfin-Whitt delay function”
DELETED: Why infinite-server approximations?
Modified Offered Load
offered load for one week
Sun
1.093
1.051
1.030
1.002
0.988
0.918
0.918
Mon
Tue
Wed
Thu
Fri
Sat
Average offered load in the M/G/n approximation
Peak offered load in the M/G/n approximation
Weighted offered load approximation
Weighted modified offered load approximation
Define
Summary of STEP 1 so far
Encompasses general i.i.d. interarrival times and
general i.i.d. service times
Can be useful for design, even though nobody waits!
If we have approximations for the mean and variance of X,
then we can set
of the standard normal distribution
(Nonhomogeneous Poisson arrivals)
M /G/
- Number of arrivals in interval [a,b] is Poisson with parameter
- Independent increments
Still approximately
(Blackwell's renewal theorem)
for Poisson arrivals:
After conditioning on appropriate epoch of the total arrival process A:
is a convex combination of
and
Variance for G/G/
Expectation for G/G/
Numerical comparison of approximations
Note: formula doesn’t use
or detailed service time information
12
2
4
4
1
lognormal interarrivals
lognormal services
Constructing S
By construction
Theorem
S is a Poisson process, independent of A!
D. System Equations
= number of arrivals before time
A general formula
Implication of bijection
arrival/Poisson sample path pairs
We know:
Suppose
system equation (SE)
- Suitable system equation yields tractable analysis
Summary
C. Nonstationary non-Markov models
- Many design problems encounter non-stationarity
- Practitioners often use workarounds (especially in healthcare)
- Standard textbooks ignore it
Recall: for M/G/n
such that
uniformly sampled customer
Summary
- Nonstationarity can have huge implications for design
Part I.
B. Stationary non-Markov models
- Discuss infinite-server approximations
- Show how they lead to waiting time approximations for finite-server systems
- Compare approximation to a widely-taught formula
M /G/
equals the expected number in the
Classical analysis: M/M/n system
i.e.,
?
Ingenious application of Markov models: G/M/n
system equation!
Markov models for "non-Markov systems"
* Hyperexponential distribution:
* Other examples include Erlang, Coxian
- Phase type distributions: time to absorption of a Markov chain
* Phase type densities are of the form
- Enlarged state space: keep track of number in each phase
- Considerable implementation effort and risk?
Markov models for "non-Markov systems"
Asmussen/O'Cinneide 1998
- For instance:
- Number in the system upon each arrival is a (discrete-time) Markov chain
* Number in service (at time of arrival)
- Leads to waiting time distribution with exponential tail:
- Exponential interarrival times (i.i.d.)
- Exponential service times (i.i.d.)
- Arrival and service times independent
- Steady-state (stationarity)
Summary
- It is a powerful framework (abandonments, capacities, ...)
* Involve vectors and matrices
* Requires solving matrix recursions
- Captures essential system characteristics with few parameters
- High quality
- Easy-to-use
Summary
nyp.org
Atlanta Journal Constitution, 9/2/2015
10 minutes
15 minutes
10 minutes
20 minutes
15 minutes
5 minutes
10 minutes
Approximations of Queueing Performance
Ton Dieker, Columbia University
Steve Hackman, Georgia Institute of Technology
Emergency Department design
Surgery Department expansion
Design questions:
Market trends
Operating Rooms of the future
Polling station design
gwinnett=[.119,.11456,.10420,.10582,0.09359,0.06642,0.06306,0.0656,0.07025,0.07821,0.0734,0.04587]
TutORial focus
- Rapid system design of "inflexible" capacity to achieve service goals:
- Analyze single-stage classical queueing system
- Limits on expected waiting time
- Limits on the likelihood of excessive waiting time
TutORial goals
- Present high-quality, tractable approximations that can be used to:
- Provide a roadmap for how approximations are developed so as to:
-
Quickly explore initial designs
-
Understand possible limitations
TutORial takeaways
-
- A suggested approximation framework for nonstationary systems
- An appreciation for:
An updated waiting time approximation for a stationary queueing system
- Wide range of techniques employed
TutORial outline
Part I. High-quality, tractable approximations
Part II. Analytical roadmap: system equations, diffusion limits
A.
Stationary Markov models
D.
Application to the G/M/n system
Part III. Summary and closing remarks
- What capacities are needed to meet target growth?
- How will changes to patient mix affect service quality?
- What is the cost/quality tradeoff associated with combining
Reduce computational burdens associated with simulation
-
Have greater confidence in application
Acknowledge the research challenges
-
-
with general interarrival and service time distributions
- Impressive results obtained so far
- Challenges that lie ahead
Stationary non-Markov models
Nonstationary, non-Markov models
B.
C.
Application to a high-dimensional continuous-time Markov chain example
E.
A.
Stationary Markov models
Stationary non-Markov models
Nonstationary, non-Markov models
B.
C.
Classical analysis: M/M/n system
Classical analysis: M/M/n system
Step 6. Use for design
Find lowest n for which
service times
Step 5. Calculate performance metrics
or
Remark:
- Typically NOT
- Must have
by a phase type distribution
- Common examples:
- Similar formulas as M/M/n
- Distribution of number of departures before next arrival depends on:
* Length of interarrival time
- Considerable implementation cost and risk?
Preview: diffusion limit approximation
where
High-quality, tractable approximations
"offered load"
- “rate in = rate out” equations are highly dependent
on service discipline
Key issues:
- It can lead to easy-to-use formulas
- It can be computationally burdensome
- It may not be applicable if assumptions do not hold
Dynamics example: adding a type 2 buffer
Dynamics example: removing a type 2 buffer
E. High-dimensional continuous-time Markov chain example
for Rapid Systems Design
navigation
A computational challenge
An alternate state space
System Equation for buffer count process
With this state space, the jump vectors are
and the System Equation is:
(joint work with student Tonghoon Suk)
SDE approximation vs. simulated distribution of
System Equation for individual buffer count processes
Waiting time
Approximation quality
For example
Example of design criterion
Deriving an SDE
An SDE
Focus here: number of empty buffers
System Equation for the number of empty buffers
Going forward, we again use the shorthand notation
Starting point:
"Centering" step:
?
?
Challenges:
- How to center?
- How to handle dependencies?
- How to deal with the nonlinearity in the last term?
- How to approximate the variance of the D and A terms?
As with G/M/n, appropriate scaling is key:
- Number of samples get arbitrary large:
- Number of buffers get arbitrary large at faster rate than number of samples:
- Service rate fixed proportion of the number of buffers:
This is how we "standardize":
We obtain the following SDE (Ornstein-Uhlenbeck process):
Implications
Y is normally distributed with zero mean and variance:
is approximately normally distributed with the following mean and variance:
This approach also gives an approximation for the expected waiting time:
Design parameters:
* Service rate
* Number of sampled buffers
Pre-Op and Post-Op care spaces?
Atlanta Journal Constitution, 6/23/2015
-
system
Presented an updated approximation for the G/G/n system that:
Part II.
Application to the G/M/n system
Application to a high-dimensional continuous-time
D.
E.
Analytical roadmap:
system equations, diffusion limits
Markov chain
Part III.
Summary and closing remarks
Summary
TutORial summary
Extensions
possible jumps
vector-valued
- Found easy-to-use approximations of performance measures
- Discussed a CTMC that is impractical to solve using standard techniques
This talk presented:
- Abandonments:
Thank you!
Current research challenges
- An updated G/G/n approximation due to Whitt
- An approximation for nonstationary systems
- A window into how these approximations are developed
- Priorities, multiclass, phase type:
- Limited waiting space:
- System Equation approach:
- Simple (and quick) approximations hold tremendous potential
- Infinite-server approximations are very useful here
- Analysis employs a large methodological toolkit
Garnett/Mandelbaum/Reiman 2002, Dai/He/Tezcan 2010
Puhalskii/Reiman 2000
Whitt 2004
Pang/Talreja/Whitt 2007, Anderson/Kurtz 2011
STEP 1
Find an analytically tractable “system equation”
STEP 2
Translate system equation to scaling limit
STEP 3
Characterize steady-state distribution for number in system
STEP 4
Approximate performance metrics
for continuous-time Markov chains
by solving an ordinary differential equation
A. Stationary Markov models
B. Stationary non-Markov models
C. Nonstationary non-Markov models
D. Application to G/M/n
E. Application to a high-dimensional CTMC
Lemma
An approximation for
then
tighter approximations:
Janssen/van Leeuwaarden/Zwart 2011
search over n yields
rate
rate
2
4
6
8
10
12
14
M/M/
G/G/
G/G/n
M/M/n
Whitt 2004
The steady-state density
of Y satisfies
Boundary conditions:
Solution:
interpret as 1 if
search over n yields
number in system
at time t
number in system
at time 0
cumulative number of
of arrivals up to time t
cumulative number of
of departures up to time t
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
0
0.01
0.02
0.03
0.04
0.05
0.06
0.07
0.08
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
0
0.005
0.01
0.015
0.02
0.025
0
0.5
1
1.5
2
2.5
0
0.005
0.01
0.015
Sakasegawa
0.1898
Cumulative number of departures
STEP 1
Represent system dynamics (randomness) via an analytically tractable “system equation”
system equation (SE)
Ito's formula:
- generally distributed i.i.d. interarrival times
- exponential service times
- G/M/n
- Computationally challenging Markov model
Will analyze two systems:
number in the system at time t
Step 1. Identify system states
where
Step 4. Solve for steady-state probabilities
Define
0
0.5
1
1.5
2
2.5
3
3.5
0
0.002
0.004
0.006
0.008
0.01
0.012
0.014
0.016
0.018
Calculating the two parameters
Not so apparent, but we are lucky in the M/M/n case:
= "Erlang-C formula"
where
number in first bufer
number in second bufer
- Gold standard: nontrivial math yields accurate, easy-to-use approximation
- No matrix recursion, fixed point, or balance equations
state:
i.e.,
- Design parameters:
* Service rate
* Number of sampled buffers
- Truncation at content 3 leads to more than one million states
- Intricate dependencies due to sampling mechanism
where
$179K
$224K
$336K
Fast Track
Exam Room
Trauma
Construction
$35K
$44K
$103K
Equipment
Capital costs:
As a consequence:
- Decouples dependencies appropriately
- Linearizes the nonlinear term ("Taylor")
- Approximates variances using "fluid approximations"
- Conventional heavy traffic, reflected Brownian motion, Skorokhod maps
- Non-Markov limits
- Networks
- Computational tools
Cumulative number of arrivals
Cumulative number of departures
we thought 0.84%
we thought 0.57%
we thought 0.48%
Erlang-Whitt
0.3598
Know:
Want: likelihood of
?
STEP 2
Translate system equation to stochastic differential equation
S is a counting process (to be discussed)
0
1
2
Step 2. Draw transition diagram
Kollerstrom 1974
Atar 2012
Gamarnik/Goldberg 2013
We use the following approximation:
we thought 0.56%
mean is approximately 0
variance is approximately
- Service discipline
* Select
* Serve the buffer with highest content among the selected buffers
buffers uniformly at random (with replacement)
- Number of buffers
- Single server
- Enables an asymptotic "decoupling" of dependencies
- Leads to simple approximation for means, expected waiting time
- Connects with mean field theory from statistical mechanics
Throughout, we use
number in the system at time t
number of arrivals up to time t
we get 4.14%
we get 0.07%
we get 0.32%
Simulation
0.3260
(std dev: 0.0018)
Need a departure in the next interval of length
2 servers are working, each rate 1
more generally:
so the probability is:
Theorem
G/M/n sample paths
rate in = rate out
Step 3. Set up "balance equations"
This leads to
we get 0.62%
STEP 3
Solve the limiting steady-state distribution for number in system, by solving an
ordinary differential equation
mean is approximately 0
variance is approximately
STEP 4
Approximate waiting time distribution via a “distributional Little’s law”
G/M/n sample paths
Arrival times
Service times
customer
arrival time
service time
customer
arrival time
service time
Take expectations with respect to p:
Claim:
for large
with a (random) error of order
By definition of p, for any f we need to have
Thus, for each f we must have
mean is approximately 0
variance is approximately
Final step: integration by parts
recall that
1