Dynamic Multi-Priority Patient Scheduling With Uncertain Demand
<-- Return to the list
Date: 11-13-2007
Start Time:
1:00pm
End Time: 2:00pm
Speaker: Martin Puterman, University of British Columbia
Location: Mudd 303
ABSTRACT
This talk describes an innovative approach to dynamically schedule
multi-priority patients to a diagnostic facility. The problem
arose from an applied project which sought to identify ways to increase
the efficiency of CT scanner operations at several Vancouver
hospitals. The scheduling problem can be summarized as follows.
Each day, a random number of appointment requests arrive. A
scheduler reviews these requests and assigns them to future appointment
slots. Each request has a priority assigned to it. Different
priorities have different maximum recommended wait times. The challenge
that the scheduler faces is that lower priority patients must be booked
“today” (for an appointment slot some time in the future) prior to
knowing future demand. If patients are booked too far in the
future, they may not meet their priority targets and staff and
equipment may sit idle. If they are booked too soon, then there
may be insufficient capacity to meet wait time targets for higher
priority patients arriving at a later date. Our research provides
precise decision rules to enable schedulers to make these decisions and
meet priority targets.
We model the scheduling process as a Markov Decision Process. Since the
state space is too large for numerical solution, we solve the
equivalent linear program through approximate dynamic programming. What
this means is that we assume a certain form for the Markov
Decision Process value function that makes the linear program
tractable. Two surprising results emerge. First, we can determine the
form of the optimal approximation without having to solve the linear
program. Second, the policy that emerges from the approximate dynamic
program (for the large majority of reasonable cost parameter values)
has a simple and easily implementable form. We demonstrate, through a
simulation of the scheduling process, that our policy outperforms both
a static booking limit policy as well as current practice.
(This research is joint with Jonathan Patrick and Maurice Queyranne)
BIO
Martin L. Puterman is Advisory Board Professor of
Operations in UBC’s Sauder School of Business and Research Director of
the UBC Centre for Health Care Management at UBC. He was founder
and director of the Centre for Operations Excellence at UBC and the
Biostatistical Consulting Service at BC Children’s Hospital. He
has consulted widely on health care operations, statistical modeling,
inventory control, forecasting and operations management.
His research was recognized through the receipt of the prestigious
Lanchester Prize from INFORMS for his book Markov Decision
Processes. He was recently appointed as an INFORMS
Fellow and has received the Canadian Operations Research Society (CORS)
Award of Merit in 2005, the CORS Practice Prize in 2002 and 2005 and
the 2003 INFORMS case prize for his case on forecasting and staff
scheduling for the Whistler-Blackcomb Ski School. He has
served on the editorial boards of Mathematics of Operations Research,
Operations Research, Management Science and The Journal of the American
Statistical Association.
He has a PhD in Operations Research and an MS in Statistics from
Stanford University and AB in Mathematics from Cornell. He
currently sits on the Advisory Boards of the UBC School of Nursing and
the BC Health Services and Policy Research Support Network.