Simheuristic of Patient Scheduling Using a Table-Experiment approach - Simio and Matlab integration Application

by Mohammad Dehghanimohammadabadi (Northeastern University), Mandana Rezaeiahari (State University of New York at Binghamton) and Thomas K. Keyser (Western New England University)

As presented at the 2017 Winter Simulation Conference


This paper focuses on optimizing patient scheduling at a breast cancer center for two types of patients: follow up and consult patients. Follow up and consult patients have different service times and follow different care pathways. The objective of this paper is to sequence the patients such that minimum average flow time is achieved for each patient type. A simheuristic framework is developed by integrating MATLAB, Simio, and Excel. Unlike existing simulation-optimization (SO) approaches that target the simulation model controls, this framework tries to optimize a data table in the simulation environment. This simulation evaluation (SE) approach could iteratively input patients arrival table into the simulation model, and obtains the expected performance of the system as a reference to generate the next solution. The obtained results from this framework are further analyzed by comparing five heuristic appointment scheduling methods.

1 Introduction

There are several obstacles to achieve effectiveness and efficiency in the delivery of care (Vahdatzad and Griffin 2016). As part of healthcare delivery systems, appointment scheduling (AS) is one of the major challenges in providing timely access to medical services and improving the efficiency of healthcare delivery (Leaven and Qu 2011). Well-timed access to health services will enhance patient satisfaction and is influenced by many factors such as decisions regarding types of medical assets, equipment, as well as the investment, and allocation of resources to healthcare facilities. The scope of these factors is very broad and AS is a critical factor among them (Gupta and Denton 2008).

Appointment scheduling is commonly used by many healthcare providers to effectively schedule patients for visit (Nguyen 2017). In the primary care context, a provider’s time is divided into slots and a patient is assigned to a slot; however, it is possible to assign a patient to more than one slot based on the type of visit (Oh et al. 2013).

Due to the uncertainties associated with service times, AS is a challenging task (Klassen and Rohleder 2004). Unlike primary care, patient service times vary based on diagnosis in specialty clinic, and the length of time slots are determined with respect to service time, and the randomness of emergency patients’ arrival (Wu et al. 2016). In a specialty care environment such as a magnetic resonance imaging (MRI) examination, AS is more complicated due to the presence of the patients and the providers’ preferences, and multiple and competing criteria (Erdogan and Denton 2013). There are three types of access rules in elective surgical scheduling: (1) block-booking, (2) open scheduling, and (3) modified block-booking (Gupta 2007). In block booking, each medical specialty is reserved specific procedure rooms on a recurring basis, and patients are then scheduled into blocks by their provider who is free to allocate patients provided the total procedure time can be completed in the allocated block (Berg and Denton 2012). Open scheduling intention is to intention is to accommodate all patients (Denton et al. 2007), and the operating room (OR) manager arranges an OR for the surgeon one day prior to the surgery. Problems classified under the group of block-booking are solved in multiple stages. First, the capacity allocated to each surgical specialty is specified (i.e., tactical level decision). Second, master schedules are generated that determine the surgical unit associated with each block (i.e., tactical level decision). Third, sequences of surgeries, as well as the start times, are improved to achieve best performance measures (i.e., operational level decision) (Gupta 2007). Despite sequential optimization in block-scheduling problems, open scheduling problems are solved at once considering many constraints, such as availability of providers and resources at the same time (Jerić and Figueira 2012). Thus, the problem of resource allocation is typically embedded in any open scheduling problem (Jerić and Figueira 2012). Finally, modified block booking is a complement of block-booking where underutilized blocks are assigned to other surgeons for surgical case scheduling (Vancroonenburg et al. 2015).

Decisions in AS can be categorized in three levels, namely strategic, tactical, and operational level. decisions Strategic level decisions are concerned with the access policy, the determination of the number of providers, the policy on acceptance of walk-ins, and the type of scheduling (Ahmadi-Javid et al. 2017). Tactical level decisions are aimed at middle-term planning (Osorio et al. 2015), and are mainly related to the allocation of capacity to different patient groups, appointment intervals, block size, and the priority of patient groups (Ahmadi-Javid et al. 2017). Finally operational level decisions are related to allocation of patients to servers, determination of appointment day and time, and patient sequence (Ahmadi-Javid et al. 2017). This paper focuses on the operational level decision of sequencing patients at a breast cancer center with the goal of minimizing the average time of patients in the system. Length of Stay (LOS) or patient flow time through the clinic is categorized as a cost-based measures (Cayirli and Veral 2003) and has been mostly addressed when patients arrive based on first-come-first-serve (FCFS) policy (Mahachek and Knabe 1984; Wang 1993, 1997).

Due to the fast invention and evolution of computational capacity of computers, the integration of simulation and optimization is remarkably grown (Dehghanimohammadabadi et al. 2017). In this study, a novel simulation-optimization (SO) approach using a metaheuristic algorithm is proposed to sequence patients’ arrival with the goal of achieving minimum average LOS. This simheuristic framework is a three-fold integration of MATLAB, Simio, and Excel. This solution evaluation approach is used to run a table-experiment in the simulation environment without involving the difficulties of defining a large set of controls and using black-box optimizers. In this framework, MATLAB deploys an optimum-seeking algorithm to generate solutions (tables), and Simio estimates the expected system performance using the provided solution by MATLAB. The interaction between the simulation and the search for an optimum is cyclic, and the exchange of data is accomplished via an Excel file. For the presented case study at the breast cancer center, a practical and good arrival pattern of patients is achieved using simulation experiments, changing the patients arrival table.

The remainder of the paper is organized as follows. Section 22 provides the relevant literature. Section 3 is devoted to details of the proposed simulation-optimization approach. A case study together with computational results are explained in Section 4. Finally, conclusions and ideas for future research are presented in Section 5.

2 Literature Review

The problem of patient scheduling in outpatient clinics considering patient classes (new and follow-up patients), patient service time distributions, cancellations, and no-shows has been addressed by many researchers recently.

Some researchers have studied the problem of patient sequencing in conjunction with the variation of patient service time distributions. For instance, Berg et al. (Berg et al. 2014) proved that sequencing patients based on the increasing order of service time and no-show probability is optimal. According to Mak et al. (Mak et al. 2014), ordered variance (OV) policy which orders the patients based on increasing variance, produces promising patient sequences. In another study, the OV policy is recommended for heterogeneous patients when no-show probabilities are close to zero (Erdogan et al. 2015). A decomposition-based algorithm is developed by Mancilla and Storter (Mancilla and Storer 2012) that outperforms the OV policy but is computationally time-consuming.

Su and Shih (Su and Shih 2003) conducted a simulation study at a urological specialty hospital in Taiwan to analyze the impact of different scheduling rules on patients’ waiting times and throughput times. Santibáñez and his colleagues (Santibáñez et al. 2009) used simulation to study the effect of operational, scheduling, and resource-allocation decisions on patients’ waiting times and room utilization at a cancer center. In their study, patients are classified based on their visit type (new patients, follow-up and consults) in various programs (medical, radiation, and surgical oncology) and clinic types (breast, lung, etc.). Lee et al. (Lee et al. 2013) studied the effect of open access and overbooking policies on patient no-show rates using simulation of an outpatient clinic. Open access slots are placed at the end of the session (varied from 10% to 80%) and two classes of patients, regular and same-day-appointment, are considered. In their study, no-show is proportional to the appointment delay window and the performance measures are overtime work, appointment backlog, and waiting time of patients. The result of this study shows that overbooking performs better than open access system.

The literature related to AS studies that have combined simulation and optimization is sparse. Klassen and Yoogalingam (Klassen and Yoogalingam 2009) embedded simulation in an optimization heuristic to try to minimize patient waiting time, doctor idle time, overtime and session end time for the physician at a primary care clinic. The decision variables in their study are patient appointments start times. They found that a plateau-dome scheduling rule is robust across all performance measures. The results of their study are compared with five appointment scheduling rules that have been studied in other simulation papers: (1) fixed intervals, (2) two patients are scheduled at the same time, (3) placing two patients in the first time slot and one patient in the second and so on, (4) placing four patients in the first time slot and one patient in the second time slot and so on, (5) off-set rule where earlier slots were shorter than average service time, and later slots were longer than average service time.

Saremi et al. (Saremi et al. 2013) modeled appointment scheduling of outpatient surgeries. They included uncertain pre-operation, surgery, and recovery time in their scheduling problem. Also, they assumed resource-availability constraints and patient compatibility with the provider. The objective of this research is to minimize the waiting time of patients, completion time, and number of cancellations due to unavailability of the resources. Integer programming (IP) is combined with enhanced Simulationbased Tabu Search (STS) to construct a better initial solution neighborhood for Tabu Search (TS) in STS. IP divides the time horizon to time slots and generates a schedule seeking to minimize wait time and completion time considering deterministic case durations. From this initial solution, STS starts to improve the schedule for a stochastic variant of the problem. At each run of the simulation, some neighborhood solutions are evaluated and the best solution is updated for the next iteration of TS. It is necessary to mention that at each run of the simulation, solutions are not fully evaluated but they are sorted based on a deterministic schedule module. Optimization and simulation approaches were used by Liang et al. (Liang et al. 2015) to improve scheduling for chemotherapy patients’ flow in an oncology clinic. In their research patients were distributed evenly into time slots to balance the workload using a mathematical model, and a probability matrix was developed to inform the user with the probability of assigning patients based on their treatment type to the time slots. Several scenarios were evaluated by considering delays in arrivals, patients’ types, variation in treatment time, cancellations, and add-ons. They concluded that balancing the workload decreases the patients’ waiting time and the staff working hours.

3 Simheuristics table-experiment

In this section, we describe the main elements and the structure of the proposed simheuristic model. Then the implementation steps are identified and the software packages used to create the model are introduced. Also, an instance of the solution structure is provided to clarify the solution generation approach used in this study.

3.1 Development

In existing commercial simulation software packages, performing table-experiment design is not trivial, or perhaps possible. To address this issue, we developed a SO framework that could easily run simulation experiments by changing a table of variables. Rather than having difficulties to define a large set of controls and using black-box optimizers such as OptQuest, the proposed framework could efficiently run table-experiments with no significant change of the simulation model structure. As shown in Figure 1, in this framework an external optimizer iteratively changes the table parameters that are applied in the simulation model, and tries to find the best or a good configuration of the table input. The optimization and simulation managers work together in an iterative manner until the stopping criteria of the optimization algorithm are satisfied. In the following section, the implementation aspects of this framework is described.

3.2 Implementation

In order to implement such a framework, we used an integrated approach by combining MATLAB, Simio, and Excel. As illustrated in Figure 2, MATLAB is the main manager, in which an optimization algorithm resides to solve the problem. The metaheuristic algorithm used in this study is Simulated Annealing (SA), which has been successfully applied to numerous optimization problems. SA is derived by a process employed to obtain a perfect crystal by gradual cooling of molten metals (Saruhan 2014). We refer the reader for details of SA to Miki, Hiwa, and Hiroyasu (Miki et al. 2006). For every iteration, the solution provided by optimizer is adjusted in the simulation model via an Excel file. SimioTM is used as the simulation manager due to its simulation capabilities (Dehghanimohammadabadi 2016; Dehghanimohammadabadi and Keyser 2015) and its capacity to interact with MATLAB and Excel.

As mentioned above and demonstrated in Section 4, the purpose of this framework is to enable running table-experiments for patients’ arrival to a breast cancer center. In every iteration, the SA algorithm in MATLAB provides a new solution, which includes the patients’ arrival times. Then, the generated solution is stored in an Excel file to be used by Simio as an input. In fact, the output from Simio is considered to be the cost function of SA, and is called to simulate the clinic model using the new patients’ arrival table. Finally, the simulation model result is transferred to MATLAB to be used by SA to generate the next solution. This interaction between MATLAB and Simio repeats until the stopping criteria of the optimization algorithm are met.

3.3 Solution Structure

In this study, the generated solution by the optimization algorithm represents a table of patients’ arrival times. To clarify how this solution is structured and is embedded into Simio, an instance of the solution considering six appointment slots for six patients is depicted in Figure 3. In the clinic under study, there are two different types of patients, including follow-up and consult patients, with the ratio of 2 to 1, respectively. For example, in the case of having six incoming patients, four are follow-up patients ), and the rest of them are consult patients. It needs to be noted that, this ratio was determined by the clinic staff.

The solution generated by SA, represents an array of numbers with permutation of six for six patients. If the generated number is less than or equal to of total patients), the patient is a follow-up; otherwise he/she is considered as a consult patient. Once the type of the patients is identified, they are assigned to the available time slots accordingly since we used a block-booking approach. The inter-arrival time of the patients for this study is deterministically fixed at 20 minutes. So, once the solution changes, the order and the type of the patients changes for each appointment slot.

As a result, the objective of the optimization algorithm is to find the best arrival table of the patients while the performance measures of the clinic are attempted to be optimized. Hence, once a new solution (patients’ arrival table) is generated by the solver (SA), its impact on the clinic needs to be evaluated via the simulation model.

Case study

4.1 Simulation Model

Dealing with uncertainty is where simulation-optimization models are most applicable (Dehghanimohammadabadi 2016). The applicability of the proposed simulation-optimization approach is tested using a case study in a breast cancer center in upstate New York. The study deals two types of patients; follow-up and consult patients. The number of cancer patients seen by this center stood at 914 and 1,654 in 2014 and 2015, respectively. There is one physician and two medical office assistants (MOAs). The center has in total five rooms including two rooms for the intake process, one room for follow-up, one room for consult, and one room for stereotactic biopsy. Prior to building the simulation model, the process was carefully monitored and the swim lane diagram is depicted in Figure 4.

Both follow-up and consult patients check-in at the receptionist and proceed into the intake process if any of the two intake rooms are available. Then upon availability of the follow-up and consult rooms, follow-up and consult patients are guided to the follow-up or consult rooms, respectively. Follow-up patients leave the system after the visit while consult patients are taken to the biopsy room. The distribution of service times at each stage in the swim-lane diagram are determined as listed in Table 1. The collected data from observations are used to parameterize statistical distributions of the simulation model. For ease of interpretation and validation by hospital staff members (Vahdatzad et al. 2017), triangular distribution is fit to the processing times data where applicable.

4.2 Experimental Design and Results

The breast cancer center in this study takes patients for seven hours with 20-minutes appointment slots. Therefore, a practical and good appointment pattern is needed to schedule 21 patients for a day. First, we used the proposed simheuristic framework in this study to search for an optimal, or at least good patients’ arrival table. Then, to evaluate the effectiveness of the proposed framework, the obtained solution of the model is compared with five heuristic approaches suggested by the clinic staff. The first heuristic (H-1) schedules follow-up patients first, and consults afterwards, while H-2 does the opposite. Heuristics 3 to 5 consider the ratio of patients (2 to 1) and schedules a combination of two follow-ups and one consult for every hour throughout the day. The generated patterns based on these methods are shown in Figure 5.

The obtained solutions from all of these methods are simulated using Simio with 30 replications to evaluate their impact on LOS of patients. To ensure the accuracy of simulation results, half-width of confidence intervals on the mean is considered to determine the number of replications. As shown in Figure 6, the results indicate that the simheuristic model has a lower average for the LOS compared to other methods. Furthermore, a Simio Add-In called "Select Best Scenario using KN" is applied to find the best scenario. This tool implements the procedure developed by Kim and Nelson (Kim and Nelson 2001), and takes an initial set of scenarios and runs additional replications until it is confident that a particular scenario is the best, or within a specified range of the best (called the indifference zone) (Simio 2011). With confidence level of 95%, this tool consistently selects the simheuristic as the best scenario for all of defined indifference zone values.


In this study, we developed a simheuristic framework to perform table-experiments for a simulation model of a breast cancer center. In this new hybrid approach, SA algorithm programmed in MATLAB generates solutions, and calls Simio as a cost function to evaluate them. The initial results from this study indicates that the existing model performs better than heuristic approaches, but the difference is not statistically significant. In the future work one to consider the duration of the time slots as a decision variable. Currently, all of the appointment blocks are fixed at 20-minutes, but they could differ depending on the patient type. Also, adding multiple performance measures such as patients’ waiting time is also desirable. In addition, other environmental factors such as patient no-shows, and patient and provider punctuality could be added to the simulation model.