Graduate School ETD Form 9

(Revised 12/07)

PURDUE UNIVERSITY
GRADUATE SCHOOL
Thesis/Dissertation Acceptance

This is to certify that the thesis/dissertation prepared

By Krishna Jayakumar

Entitled Petri-net based Simulation Modeling to Analyze Emergency Department Diversion

For the degree of Master of Science in Industrial Engineering

Is approved by the final examining committee:

Mark Lawley

W
Chair
Vincent Duffy

Joseph Pekny
IE
EV

To the best of my knowledge and as understood by the student in the Research Integrity and
Copyright Disclaimer (Graduate School Form 20), this thesis/dissertation adheres to the provisions of
Purdue University’s “Policy on Integrity in Research” and the use of copyrighted material.
PR

Mark Lawley
Approved by Major Professor(s): ____________________________________
Vincent Duffy
____________________________________

Approved by: Richard Liu 03/03/2010

Head of the Graduate Program Date
Graduate School Form 20
(Revised 1/10)

PURDUE UNIVERSITY
GRADUATE SCHOOL

Research Integrity and Copyright Disclaimer

Title of Thesis/Dissertation:
Petri-net based simulation modeling to analyze Emergency Department Diversion

Master of Science in Industrial Engineering

W
For the degree of ________________________________________________________________

I certify that in the preparation of this thesis, I have observed the provisions of Purdue University
Teaching, Research, and Outreach Policy on Research Misconduct (VIII.3.1), October 1, 2008.*
IE
Further, I certify that this work is free of plagiarism and all materials appearing in this
thesis/dissertation have been properly quoted and attributed.

I certify that all copyrighted material incorporated into this thesis/dissertation is in compliance with
EV
the United States’ copyright law and that I have received written permission from the copyright
owners for my use of their work, which is beyond the scope of the law. I agree to indemnify and save
harmless Purdue University from any and all claims that may be asserted or that may arise from any
copyright violation.
PR

Krishna Jayakumar
______________________________________
Printed Name and Signature of Candidate

02/25/2010
______________________________________
Date (month/day/year)

*Located at http://www.purdue.edu/policies/pages/teach_res_outreach/viii_3_1.html
PETRI-NET BASED SIMULATION MODELING TO ANALYZE EMERGENCY

DEPARTMENT DIVERSION

A Thesis

Submitted to the Faculty

of

W
Purdue University

by
IE
Krishna Jayakumar
EV

In Partial Fulfillment of the

Requirements for the Degree

PR

of

Master of Science in Industrial Engineering

May 2010

Purdue University

West Lafayette, Indiana

 UMI Number: 1479657

All rights reserved

INFORMATION TO ALL USERS

The quality of this reproduction is dependent upon the quality of the copy submitted.

In the unlikely event that the author did not send a complete manuscript
and there are missing pages, these will be noted. Also, if material had to be removed,

W
a note will indicate the deletion.

IE
EV

UMI 1479657
PR

Copyright 2010 by ProQuest LLC.

All rights reserved. This edition of the work is protected against
unauthorized copying under Title 17, United States Code.

ProQuest LLC
789 East Eisenhower Parkway
P.O. Box 1346
Ann Arbor, MI 48106-1346
 ii

W
IE To my wife
To my mom & dad
EV
To my brother
PR
 iii

ACKNOWLEDGMENTS

First and foremost I offer my sincerest gratitude to my supervisor, Dr Mark Lawley,

who has supported me throughout my thesis with his patience and knowledge whilst
allowing me the room to work in my own way. I attribute the level of my Masters
degree to his encouragement and Dr Arun Chockalingam’s effort and without both
this thesis would not have been completed or written.

I wish to thank Dr Duffy, who with his constant words of encouragement and reas-

W
surance has moved me through the roadblocks in my work, including the workstation.

IE
Thanks to my friends Sundar, Aswin and Ezhil for living without their front room for
more than a month. My friends in the Department of Industrial Engineering, Satish,
Pritam, Dabad, Meerant and Bebe (and a million others) need a special mention for
EV
supporting me through my highs and lows.

I express my sincere gratitude to the Department of Biomedical Engineering and

PR

Purdue HTAP for funding my Master’s program.

I wish to thank my parents and my brother for making this opportunity possible.
Finally, I wish to thank my wife, Lalitha for bearing the brunt of my frustrations for
the past 2 something years.
 iv

TABLE OF CONTENTS

Page
LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
ABBREVIATIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
1 INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Motivation for the study . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Conceptual model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

W
1.3 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Construction of the thesis . . . . . . . . . . . . . . . . . . . . . . . 5
2 LITERATURE REVIEW . . . . . . . . . . . . . .
IE . . . . . . . . . . . . 6
2.1 Emergency department divert . . . . . . . . . . . . . . . . . . . . . 6
2.2 Petri-nets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.1 Patient flow modeling using Petri-nets . . . . . . . . . . . . 10
EV
2.3 Simulation modeling of health-care systems . . . . . . . . . . . . . . 11
3 MODEL AND METHODOLOGY . . . . . . . . . . . . . . . . . . . . . . 12
3.1 Hospital Petri-net model . . . . . . . . . . . . . . . . . . . . . . . . 13
3.1.1 Emergency Department Fast Track (FT) . . . . . . . . . . . 13
3.1.2 Emergency Department(ED) . . . . . . . . . . . . . . . . . . 15
PR

3.1.3 Intensive Care Unit . . . . . . . . . . . . . . . . . . . . . . . 16

3.1.4 Medical Surgical Unit (Med/Surge)model . . . . . . . . . . . 17
3.2 Petri-net analysis - Boundedness . . . . . . . . . . . . . . . . . . . . 17
3.3 Simulation modeling of patient flow using AutoMod . . . . . . . . . 21
3.3.1 Converting PN model to Simulation model using Templates 22
3.4 Simulation output analysis . . . . . . . . . . . . . . . . . . . . . . . 25
3.4.1 AutoMod output . . . . . . . . . . . . . . . . . . . . . . . . 25
4 HEURISTIC CONTROL POLICIES . . . . . . . . . . . . . . . . . . . . 27
4.1 Heuristic Control Policies . . . . . . . . . . . . . . . . . . . . . . . . 27
4.1.1 Modeling ED divert . . . . . . . . . . . . . . . . . . . . . . . 27
5 DATA ANALYSIS AND RESULTS . . . . . . . . . . . . . . . . . . . . . 31
6 CONCLUSION AND FUTURE WORK . . . . . . . . . . . . . . . . . . 43
6.1 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
 v

Page
6.1.1 Minimum Parikh Vector generation . . . . . . . . . . . . . . 44
6.1.2 Distance to Divert State . . . . . . . . . . . . . . . . . . . . 45
6.2 Modeling Distance to Divert . . . . . . . . . . . . . . . . . . . . . . 48
6.2.1 Model Selection . . . . . . . . . . . . . . . . . . . . . . . . . 48
LIST OF REFERENCES . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
A.1 AUTOMOD template codes . . . . . . . . . . . . . . . . . . . . . . 51
A.2 MATLAB code for MPV generation . . . . . . . . . . . . . . . . . . 60
A.3 GAMS code for MPV generation . . . . . . . . . . . . . . . . . . . 61
A.4 SAS code for statistical analysis . . . . . . . . . . . . . . . . . . . . 62
VITA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

W
IE
EV
PR
 vi

LIST OF TABLES

Table Page
3.1 Boundedness : resource-token distribution . . . . . . . . . . . . . . . . 19
3.2 Boundedness property verification results . . . . . . . . . . . . . . . . . 20
5.1 Cost of hospital resources . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.2 Comparison of performance measures: uncontrolled vs controlled process 32
5.3 Simulation trials output: Profit . . . . . . . . . . . . . . . . . . . . . . 33
5.4 Simulation trials output: LWBS rate . . . . . . . . . . . . . . . . . . . 36

W
5.5 Performance measures : uncontrolled vs controlled process . . . . . . . 38

IE
EV
PR
 vii

LIST OF FIGURES

Figure Page
1.1 Hospital patient-flow diagram . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 A Petri-net model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1 A Petri-net model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.1 Hospital patient flow Petri-net . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 Boundedness : Petri-net model . . . . . . . . . . . . . . . . . . . . . . 18
3.3 Petri net model simulation demo . . . . . . . . . . . . . . . . . . . . . 21

W
3.4 Flowchart 1- simulation code template . . . . . . . . . . . . . . . . . . 22
3.5 Flowchart 2- simulation code template . . . . . . . . . . . . . . . . . . 23
3.6
3.7
IE
Flowchart 3- simulation code template . . . . . . . . . . . . . . . . . .
Simulation output - instantaneous resource availability . . . . . . . . .
24
26
4.1 Bed availability (ED + ICU) over 30 day period . . . . . . . . . . . . . 28
EV
4.2 Plot of bed availability: uncontrolled vs controlled system . . . . . . . 30
5.1 Plot of main and interaction effects of factors for profit . . . . . . . . . 34
5.2 ANOVA - Test of significance for response variable: profit . . . . . . . 35
PR

5.3 Tukey test for profit: factor - surge level . . . . . . . . . . . . . . . . . 37

5.4 Tukey test for profit: factor - lower bound . . . . . . . . . . . . . . . . 38
5.5 Plot of main and interaction effects of factors for LWBS rate . . . . . . 40
5.6 ANOVA - Test of significance for response variable: LWBS rate . . . 41
5.7 Tukey test for lwbs: factor - surge . . . . . . . . . . . . . . . . . . . . 42
5.8 Tukey test for lwbs: factor - lower bound . . . . . . . . . . . . . . . . . 42
6.1 Example Petri-net model . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6.2 Graph of distance measure over 30 days . . . . . . . . . . . . . . . . . 46
 viii

ABBREVIATIONS

ED Emergency Department
FT Emergency Department Fast Track
ICU Intensive Care Unit
Med/Surg Medical Surgical Unit
OR Operating Room
EMTALA Emergency Medical Treatment and Active Labor Act

W
IE
EV
PR
 ix

ABSTRACT

Jayakumar, Krishna M.S.I.E., Purdue University, May 2010. Petri-net based sim-
ulation modeling to analyze emergency department diversion . Major Professor:
Mark A. Lawley and Vincent G. Duffy.

Emergency Department (ED) overcrowding is a common problem occurring in US

hospitals. Presenting a barrier to safe and timely delivery of healthcare, hospitals
address ED overcrowding by diverting ambulances to the nearest available facility.
This leads to a delay in delivery of care for patients and a loss in revenue for the

W
hospitals. In this work, a Petri-net model of a hospital is developed, and simulation
modeling is used to help develop heuristic control policies that improve patient care
IE
and hospital profits.The benefit of using control policies is highlighted, and a related
stochastic control problem which will yield the optimal policy is discussed.
EV
PR
 1

1. INTRODUCTION

An ambulance diversion is a state which occurs when a hospital Emergency Depart-

ment(ED) cannot care for additional emergency patients. When a hospital is “on
diversion”, it redirects ambulances from their ED to another hospital or medical
facility. The Emergency Medical Treatment and Active Labor Act (EMTALA) is a
United States Act of Congress passed in 1986 which requires hospitals and Emergency
Medical Services (EMS) to provide care to emergency patients who present themselves
at the hospital,regardless of citizenship, legal status or ability to pay [1]. Irrespective

W
of the state of hospital, these laws mandate providing patient care which can lead to
congestion. Studies also suggest that lack of primary care physician and facilities or
IE
the access to one, forces more people to show up at the emergency department for
treatment [2].
EV

1.1 Motivation for the study

The Institute of Medicine’s recent study shows that emergency department (ED)
PR

overcrowding presents a barrier to safe and timely delivery of healthcare. The number
of ED visits has increased by 90.3 million in 2003 compared to a decade ago. On the
other hand, between 1993 and 2003, the number of hospitals has decreased by 703,
the number of beds by 198,000 and the number of emergency departments by 425 [3].
During this time 45% of the hospitals reported some period of time in ambulance
diversion [4]. Studies have shown that ED overcrowding can lead to adverse patient
outcomes and impaired access to care. ED diversion is also costly. Recent studies
indicate that hospitals lose approximately $1086 an hour in revenues in a divert
situation [5]. Each patient not seen equates to $8000 to $10000 in lost revenues [6].
 2

The aim of this thesis is to develop optimal-control policies for ED operations by

combining simulation with Petri-net theory.

1.2 Conceptual model

The patient-flow in a typical hospital system is shown in Figure 1.1. Patient arrival
to the ED can be either by emergency medical services(EMS) or walk-ins. Studies
show that 18% of the patients who visit the ED come by an ambulance. Regulated
by the EMTALA, hospitals cannot avoid the population walking in to the hospital
and so when they are overwhelmed with patients, they divert the ambulances to the
nearest medical facility or hospital. Once considered as a safety measure in most
extreme circumstances, ambulance diversions are now commonplace. On average,

W
an ambulance carrying an emergency patient is diverted once every minute in the
United States. On the other hand, lack of free inpatient beds prevents patients in
IE
the ED from moving further to other departments like the Intensive Care Unit (ICU)
or the Medical Surgical Unit (Med/Surg). This is called access blocking and can be
defined as the situation where patients in the emergency department (ED) requiring
EV
inpatient-care are unable to gain access to appropriate hospital beds within a reason-
able time frame. In 2005, the average length of stay in ED in the United states was
3.7 hours [7]. According to resource dependency theory, all organizations exchange
PR

resources with the environment as a condition for survival. In a hospital, the need for
patients to acquire all required resources creates dependencies between organizations
and external units, ultimately leading to congestion. Patients from the ED may move
to OR for required procedures. After emergency treatment, the more critical patients
may move into the ICU and stable patients to the Med/Surg. Physicians order tests
as part of patient assessment and these tests are done by the labs. Solid lines in the
figure represent patient flow and dotted lines represent information flow.

As a first step to address the problem of ED overcrowding, we develop hospital

 3

Labs

Emergency
Med Surg
Department

ED Fast track
ICU

OR

W
Patient flow IE
Information flow

Figure 1.1. Hospital patient-flow diagram

EV

patient-flow models using Petri-nets(PN). Petri-nets are directed, bipartite graphs

PR

for modeling discrete distributed systems. A PN a set of places, set of transitions

and arcs that connect place(s) to a transition and vice-versa. Non-negative integers
assigned to every place in the net are known as tokens. A distribution of tokens over
all the places in the PN is called a marking. A PN is defined by its structure and its
initial marking mo . A transition is said to be enabled when every input place(s) of the
transition has at least k tokens, where k is the weight of the arc from input place(s) to
the transition. When a transition fires tokens are removed from the input place(s) and
deposited into the output places. Input places are analogous to pre-conditions and
output places are analogous to post-conditions. Transitions can be viewed as events.
 4

Thus, for an event to occur (transition to fire), pre-conditions (tokens in input places)
must be satisfied. Occurrence of the event creates the post conditions. Thus, tokens

T1 T2
P1 P2 P3

T4
P4 P5

Figure 1.2. A Petri-net model

W
are removed from input places and deposited in output places. An example of a PN
IE
model is illustrated in Figure 1.2. Petri-nets, properties and modeling using PN are
discussed in detail in Chapter 2. For this study, divert state is defined as a state
where there are no ED beds and ICU beds available. In the PN model, it can be
EV
viewed as “no available tokens” in the places which holds the resource tokens for ED
and ICU beds. All hospital states where there are no tokens in this specific resource
place can be classified as divert states. The sequence of transition firings required to
PR

move the PN from a given state to a required state is called a Parikh Vector(PV).
Given the current state marking and the definition of divert state for the model, we
generate the minimum sequence of PN transition firings required to reach the nearest
divert state called Minimum Parikh Vector(MPV) [8].

1.3 Contribution

In this work, the use of control policies to manage hospital resources is demonstrated.
These have significant benefits on hospital operation including improvement in patient
care and increase in profit for the hospital. Specifically, these policies dictate when