Artificial
Intelligence
in
Medicine
53 (2011) 73–
81
Contents
lists
available
at
ScienceDirect
Artificial
Intelligence
in
Medicine
jou
rn
al
h
om
epage:
www.elsevier.com/locate/aiim
A
Markov
decision
process
approach
to
multi-category
patient
scheduling
in
a
diagnostic
facility
Yasin
Gocgun
a,∗
,
Brian
W.
Bresnahan
b
,
Archis
Ghate
c
,
Martin
L.
Gunn
b
a
Operations
and
Logistics
Division,
Sauder
School
of
Business,
University
of
British
Columbia,
2053
Main
Mall
Vancouver,
BC
V6T
1Z2,
Canada
b
Department
of
Radiology,
University
of
Washington
and
Harborview
Medical
Center,
325
9th
Avenue,
Seattle,
WA
98104,
USA
c
Department
of
Industrial
and
Systems
Engineering,
University
of
Washington,
Seattle,
WA
98195,
USA
a
r
t
i
c
l
e
i
n
f
o
Article
history:
Received
28
May
2010
Received
in
revised
form
26
May
2011
Accepted
3
June
2011
Keywords:
Markov
decision
process
Patient
scheduling
in
diagnostic
facilities
a
b
s
t
r
a
c
t
Objectives:
To
develop
a
mathematical
model
for
multi-category
patient
scheduling
decisions
in
computed
tomography
(CT),
and
to
investigate
associated
tradeoffs
from
economic
and
operational
perspectives.
Methods:
We
modeled
this
decision-problem
as
a
finite-horizon
Markov
decision
process
(MDP)
with
expected
net
CT
revenue
as
the
performance
metric.
The
performance
of
optimal
policies
was
compared
with
five
heuristics
using
data
from
an
urban
hospital.
In
addition
to
net
revenue,
other
patient-
throughput
and
service-quality
metrics
were
also
used
in
this
comparative
analysis.
Results:
The
optimal
policy
had
a
threshold
structure
in
the
two-scanner
case
–
it
prioritized
one
type
of
patient
when
the
queue-length
for
that
type
exceeded
a
threshold.
The
net
revenue
gap
between
the
optimal
policy
and
the
heuristics
ranged
from
5%
to
12%.
This
gap
was
4%
higher
in
the
more
congested,
single-scanner
system
than
in
the
two-scanner
system.
The
performance
of
the
net
revenue
maximizing
policy
was
similar
to
the
heuristics,
when
compared
with
respect
to
the
alternative
performance
metrics
in
the
two-scanner
case.
Under
the
optimal
policy,
the
average
number
of
patients
that
were
not
scanned
by
the
end
of
the
day,
and
the
average
patient
waiting-time,
were
both
nearly
80%
smaller
in
the
two-
scanner
case
than
in
the
single-scanner
case.
The
net
revenue
gap
between
the
optimal
policy
and
the
priority-based
heuristics
was
nearly
2%
smaller
as
compared
to
the
first-come-first-served
and
random
selection
schemes.
Net
revenue
was
most
sensitive
to
inpatient
(IP)
penalty
costs
in
the
single-scanner
system,
whereas
to
IP
and
outpatient
revenues
in
the
two-scanner
case.
Conclusions:
The
performance
of
the
optimal
policy
is
competitive
with
the
operational
and
economic
metrics
considered
in
this
paper.
Such
a
policy
can
be
implemented
relatively
easily
and
could
be
tested
in
practice
in
the
future.
The
priority-based
heuristics
are
next-best
to
the
optimal
policy
and
are
much
easier
to
implement.
© 2011 Elsevier B.V. All rights reserved.
1.
Introduction
In
facilities
that
perform
medical
imaging
studies
on
patients
with
differing
degrees
of
urgency,
scheduling
policies
impact
oper-
ational
efficiency
and
influence
service-quality,
costs,
revenues,
and
health
outcomes.
Administrators
encounter
economic
and
clin-
ical
tradeoffs
when
imaging
different
classes
of
patients
using
limited
resources.
For
example,
in
many
radiology
departments,
emergency
patients
(EPs),
inpatients
(IPs),
and
outpatients
(OPs)
may
be
scanned
on
the
same
computed
tomography
(CT)
scan-
ner,
but
often
each
patient
class
must
be
scanned
with
differing
urgency
and
they
may
have
different
revenue/cost
implications.
In
such
cases,
if
an
imaging
time-slot
is
vacant,
an
arriving
EP
is
∗
Corresponding
author.
Tel.:
+1
604
822
5517;
fax:
+1
604
822
9574.
E-mail
addresses:
yasin.gocgun@sauder.ubc.ca,
gocgun@u.washington.edu
(Y.
Gocgun).
scanned
immediately.
However,
in
the
absence
of
an
EP,
schedulers
must
decide
whether
to
scan
a
scheduled
OP,
an
unscheduled
OP,
or
an
IP.
Scanning
an
OP
first
might
lead
to
an
extra
day
of
hospital-
ization
for
an
IP
who
is
waiting
for
a
scan
prior
to
discharge,
if
there
are
insufficient
resources
to
scan
that
IP
by
the
end
of
the
work-
day.
Alternatively,
overtime
costs
may
be
incurred
by
the
imaging
facility.
Preferentially
scanning
the
IP
may
lead
to
a
perceived
loss
of
service-quality
for
the
OP
[1].
Rapid
advances
in
imaging
tech-
nology
and
increasing
demand
for
imaging
services
have
further
compounded
such
scheduling
challenges
[2,3].
Owing
to
the
complexity
of
these
decision-problems,
adminis-
trators,
imaging
technologists,
and
physicians
commonly
use
ad
hoc
approaches,
or
at
best,
rules
of
thumb
determined
by
trial-
and-error,
to
make
scheduling
choices.
In
this
paper,
we
focus
on
patient
scheduling
problems
that
typically
arise
in
computed
tomography
(CT).
Our
goal
is
not
to
incorporate
all
details
of
the
entire
spectrum
of
issues
involved
in
making
scheduling
decisions,
but
rather
to
highlight
several
key
revenue/cost
and
measurable
0933-3657/$
–
see
front
matter ©
2011 Elsevier B.V. All rights reserved.
doi:10.1016/j.artmed.2011.06.001