Mathematical Programming and Heuristic Design for Planning of Operating Rooms

Justin Britt, University of Windsor


In Canada, a significant percentage of government spending goes towards healthcare. The three biggest spending areas are hospitals, drugs, and physicians. In a hospital, operating rooms (ORs) and the downstream resources, such as recovery ward (RW) beds, used by surgical patients are expensive to operate but improve the welfares of patients and provide a large portion of the revenue. Hospital managers must plan and schedule the ORs in order to utilize the physical resources and the human resources who staff them as efficiently as possible.

OR planning and scheduling problems are divided into three phases: strategic, tactical, and operational. In the strategic phase, the Case Mix Problem (CMP) involves assigning numbers of patients to surgical specialties and/or surgeons for a planning horizon of one or more years. Time assignments in the ORs can also be determined in this phase. In the tactical phase, the Master Surgical Scheduling Problem (MSSP) is solved in order to obtain a master surgical schedule (MSS). This assigns surgical specialties and/or surgeons to time blocks in the ORs. The planning horizon ranges from one week to several weeks. In the operational phase, there are two problems: the Surgical Case Assignment Problem and the Elective Surgery Sequencing Problem. In the first problem, each patient is assigned to a surgeon, OR, and time block. In the second problem, assigned patients are sequenced. The planning horizon for both problems ranges from one day to several days.

In this dissertation, methods for the strategic and tactical phases of OR planning are developed and evaluated. The problems considered are the CMP and the MSSP. The methods include mathematical models, which use robust optimization (RO) and stochastic programming to account for uncertainties, and discrete event simulation (DES) models. In addition, there are multiple solution methods, including metaheuristics and a hyperheuristic. Because multiple problems are being considered, the heuristic solution methods are mostly independent of the problem being solved. A decision support system (DSS) that incorporates the mathematical and DES models and solution methods is developed. Computational experiments are performed in order to compare these methods to similar existing ones.

For the CMP in the strategic phase, a mixed integer program is formulated. The objective function maximizes the total benefit of the assigned case mix, where the benefit of a surgery is the difference between the long term savings associated with performing the surgery and the direct medical costs. The constraints consider RW beds, RW censuses, time block assignments, surgical durations, and surgery assignment bounds. RO is used to account for uncertainties in surgical durations. A fuzzy late acceptance hyperheuristic is developed and used to generate strategic plans.

For the MSSP in the tactical phase, a hierarchical approach consisting of multiple mathematical programs is developed. The mathematical programs are solved in series and meet external waiting time targets, minimize differences between the actual and target number of patients, maximize the utilization of ORs, minimize variations in assignments to both weekdays and ORs, minimize the total number of expected patients in the RW and minimize variations in the RW utilization. Stochastic programming is used to account for uncertain surgical durations and patient lengths of stay. A hybridized metaheuristic that uses a genetic algorithm, variable neighbourhood search, and a late acceptance hill climbing heuristic is used to generate tactical plans.

An iterative software development lifecycle (SDLC) model is used to develop the DSS for strategic and tactical OR planning. The SDLC model has four phases: system initiation, system requirements, system design, and system construction. This culminates in an easy to use software package that has several systems, including a graphical user interface and data management, optimization, and simulation systems.

Comparative experiments are performed using the proposed methods and existing ones. Several performance indicators, including the number of patients, number of OR and weekday assignments, OR underutilization, expected values and variances of RW censuses, and expected bed shortages, are used. Aside from a few exceptions, this approach performs as well or better than the comparative models.