Optimization Of Surgery Scheduling with Uncertain Models
This project is a cooperation with the Charité hospital, and aims at creating a tool that helps to schedule patients and human resources (surgeon, anesthesiologists, nurses) in a surgical unit. From a mathematical point of view,
this is a resource-constrained scheduling problem, with uncertain durations and activity insertions (emergency cases).
In this project we research on developing and implementing suitable algorithms for an optimal planning of the surgical units,
by taking the inherent uncertainty of this problem into account.
The project OPOSSUM aims at developing algorithms to schedule patients and human resources in a surgical unit. During the first phase of this project (2013-2014), we have built a model of the surgical process for the Charité hospital in Berlin. This model describes the sequence of events in the operation theater, and predicts the duration of each event -- in terms of probabilities -- based on the available diagnostic information.
During the main phase of this project (2014 - ), we will develop algorithms that use this model to optimize the logistics in the surgical unit. Our primary focus is on reducing the overtime through a better allocation of resource. Here, the overtime is defined as the time where elective patients are being handled outside the scheduled time of opening of the surgical unit.
Our final goal is to implement a computer tool that can be used by the surgery schedulers. This tool will contain both an optimizer (that searches the optimal sequence of cases to handle and allocates resources to each patient), and a simulator (that allows the scheduler to evaluate the goodness of a particular schedule).
We have analyzed 2 years of (anonymized !) data from the Charité to create a statistical model for the frequency of emergency cases, and for the duration of different events in the surgical process (induction of anesthesia, surgical procedure, turnovers, ...). Our model mainly relies on the diagnostic information that is available prior to the operation. To achieve a more accurate estimation of the durations, we plan to incorporate other factors in our model, such as an estimate of the durations made by the surgeons.
From a mathematical point of view, the scheduling problem in a surgical unit is a RCPSP (Resource Constrained Project Scheduling Problem) with uncertain durations and activity insertions (emergency cases). Already in the deterministic case (that is, all durations are known and there are only elective patients), RCPSPs belong to a class of very hard combinatorial optimization problems. However, we have shown in the first phase of this project that some parts of the problem -- such as the allocation of one type of resources -- can be solved very efficiently. We want to take advantage of this situation to develop a decomposition approach that finds a scheduling strategy with a guaranteed efficiency.
The scheduling process in an operation theater can be represented by a Petri Net (cf. logo of the project). We have implemented a simulator that simulates this process, and outputs some statistics --such as the expected distribution of overtime-- to evaluate a particular scheduling strategy.