Operating room scheduling problem under uncertainty: Application of continuous phase-type distributions

Abstract

This article studies the stochastic Operating Room (OR) scheduling problem integrated with a Post-Anesthesia Care Unit (PACU), the overall problem is called the Operating Theater Room (OTR) problem. Due to the inherent uncertainty in surgery duration and its consecutive PACU time, the completion time of a patient should be modeled as the sum of a number of random variables. Some researchers have proposed the use of the normal distribution for its well-known additive property, but there are questions regarding its fitting adequacy to real OTR data, which tends to be asymmetric with a long tail. We propose to estimate the surgery and PACU times with the family of Continuous PHase-type (CPH) distributions, which provides both fitting adequacy and additive property. We first compute the completion time of each patient analytically and compare the results with normal and lognormal distributions on a series of real OTR datasets. Then, we develop a search algorithm embedding a constructive heuristic and a meta-heuristic algorithm as a sequence generator engine for the patients, and apply the CPH distribution as a chance constraint to eventually find the schedule of each sequence in the OTR problem. The best algorithm among several tested constructive heuristic algorithms is used as the neighborhood structure of meta-heuristic algorithms. We finally construct a numerical example of OTR problem to illustrate the application of the proposed algorithm.

Keywords:

• Operating theater room scheduling
• Post-Anesthesia Care Unit (PACU)
• minimization of makespan
• continuous phase-type distributions
• heuristics and meta-heuristic algorithms

Acknowledgments

The authors thankfully acknowledge professor John Bowers from University of Stirling, for sharing the datasets of Scottish NHS hospital from 1998 to 1999.

Additional information

Notes on contributors

Mohsen Varmazyar

Mohsen Varmazyar received his Ph.D. in industrial engineering from Sharif University of Technology (SUT) in Iran. He holds a Master’s degree in industrial engineering also obtained at SUT. His research interests focus on applied operations research, scheduling and stochastic processes.

Raha Akhavan-Tabatabaei

Raha Akhavan-Tabatabaei is an associate professor of operations management and co-director of the Master’s program in business analytics at Sabanci School of Management. Prior to this position, she was an associate professor of industrial engineering and the founding director of the Master’s program in analytics at Universidad de los Andes in Bogota, Colombia. Before that, she worked as a senior industrial engineer at Intel Corporation in Arizona, USA. She received her Ph.D. and M.Sc. in industrial engineering and operations research from North Carolina State University, and her B.Sc. from Sharif University of Technology. Her research is focused on stochastic modeling and data-driven decision making with applications in healthcare, logistics, revenue management and reliability.

Nasser Salmasi

Nasser Salmasi received his Ph.D. in the area of industrial engineering from Oregon State University, USA. He worked in the Department of Industrial Engineering at Sharif University of Technology, Tehran, Iran as an associate professor for 9 years. In October 2015 he joined Corning Incorporated in the USA as an operations research analyst. His primary areas of research interests are applied operations research, sequencing and scheduling, and simulation.

Mohammad Modarres

Mohammad Modarres is a professor in the department of Industrial Engineering, Sharif University of Technology, Iran. He received his Ph.D. in systems engineering and operations research from the University of California, Los Angles (UCLA) in 1975. His research interests are operations research, revenue management and robust optimization.