Traditional scheduling assumes knowledge of how long tasks take. In the reality of hospitals, we may at best have a good guess how long a surgery will take. Can you schedule next week's surgeries so that the risk of having to bump a patient to the following day is minimized?
Overfit Memorial, the DS City hospital, has reached out for your help. They have three isolated surgery wings with 3 operating rooms (OPs) each. Each wing is also equipped with 4 post-anesthesia care units (PACUs). Here are the upcoming operations for one of the wings, with their average operation (OR) and PACU times (see this Colab for the data):
Each of the 3 OPs offers 480 minutes (8 hours) of scheduled operating time per day. After an operation, a patient must be moved to a PACU of which there are only 4 (PACUs in other wings cannot be used). If no PACU is available, the patient has to remain and will block the OP until the patient has recovered or a PACU becomes available.
Val, the hospital manager of Overfit Memorial, tells you that they already use operations research to optimize their schedules. And this has led to great improvements. But they still have a problem. Because the time of surgery and recovery vary not just from operation type to operation type, but from patient to patient. While the table above gives average OR and PACU times, Val believes that the actual distribution is a Gamma distribution with shape 16 and scale mu/16, whereby mu is the average as given in the table.
"Of course, we are not stupid. When an operation takes longer, we shift things around. The next surgery that was supposed to start is simply moved to the first OP that will be free. And when recovery is taking longer, we move the patient to the first available PACU. From the optimized solution, we really only use the ordering of surgeries each day and assign OPs and PACUs according to the first-available rule," Val explains.
"But we cannot start an operation if its average time would mean that it would exceed the 480 minute ceiling [this regards operation time only - PACUs do not have a time limit]. But of course, if an operation takes longer, we still finish it. Only if we see that it is expected to go into overtime, we bump that operation to the earliest slot the next day. And that is very costly, because it means the patient has to stay in the hospital one day longer. We also need to prep them again and may have to find a different surgeon. On average, a bumped operation costs us $3,500."
Val shrugs his shoulders: "The solution we get from the optimizer now results in about two bumped operations per wing and week. So we have over 300 bumped operations per year, which cost us almost $1 million annually. We have to reduce that cost if we can."
And this is where your expertise is required. Can you help Val with an improved sequence of operations for this one wing in his hospital?
[Scroll down for the solution]
For extra credit, keep in mind that Val's assumption of distributions is an estimate. How does your solution fare if his distributional assumption is off?
Using Val's estimate, Seeker produces this sequence of surgeries for each day:
Day 1: [12, 5, 13, 2, 15, 6, 7, 8, 10, 9, 1, 11, 3, 4, 14, 0]
Day 2: [13, 0, 10, 4, 15, 7, 14, 6, 1, 8, 5, 12, 3, 2, 11, 9]
Day 3: [8, 10, 13, 12, 5, 6, 15, 7, 4, 9, 3, 1, 11, 14, 2, 0]
Day 4: [1, 3, 14, 7, 6, 15, 8, 5, 0, 13, 9, 10, 12, 4, 2, 11]
Day 5: [14, 9, 1, 12, 2, 5, 7, 15, 4, 8, 3, 6, 11, 0, 13, 10]
If all operations and recoveries go according to plan, this sequence would result in this schedule:
Curiously, this solution looks a bit worse than the existing solution:
The corresponding sequences from the existing optimizer are:
Day 1: [8, 14, 5, 4, 9, 2, 3, 12, 0, 7, 15, 6, 1, 13, 10, 11]
Day 2: [5, 8, 6, 3, 9, 14, 2, 13, 12, 7, 15, 4, 0, 1, 10, 11]
Day 3: [11, 5, 6, 9, 2, 14, 3, 13, 7, 15, 4, 12, 8, 1, 10, 0]
Day 4: [9, 5, 7, 11, 8, 14, 12, 3, 13, 6, 4, 15, 1, 2, 0, 10]
Day 5: [6, 8, 14, 12, 9, 3, 13, 11, 4, 15, 7, 5, 2, 0, 1, 10]
However, the Seeker solution results in expected 0.60 bumps ($2,088) for this hospital wing in this week while the deterministic solution results in 1.75 bumps (cost per wing and week $6,110). Provided that the data is indicative of all three wings and all weeks, Seeker reduces the annual costs from $953,160 for the solution from the deterministic optimizer to $331,952.
What if our stochastic assumptions are wrong?
But wait: Val was estimating that the operation and recovery times were varying in accordance with a Gamma distribution with a given estimated mean and 25% standard deviation. What if he is wrong?
This is one of the most common concerns when it comes to stochastic optimization: How can I possibly get accurate distributional estimates? How do I even measure the accuracy of distributions?
Let us experiment with the assumptions and change them as follows: For each operation (and PACU-recovery) in the data, we randomly either change its shape from Gamma to Normal or Exponential. We also randomly change the means by drawing a new mean from a normal distribution with the same mean as Val's guess, but with 10% standard deviation. And we also vary the variance of the distributions in the same manner.
Thus, a Gamma distribution for a 45 minute surgery can now morph into a a normal distribution or an exponential distribution as shown below. You will agree that these distributions sufficiently differ from Val's Gamma distribution assumption which we used to create our solution.
Now, we keep our solution that was optimized for the Gamma-distribution assumption fixed. Naturally, we also fix the deterministic solution, which did not rely on stochastic assumptions in the first place.
Now, for 100 random alterations of our assumed distributions into the "real" distributions, we sampled 10,000 "real" surgery and recovery durations each (1 million scenarios total) and recorded the average number of bumped operations and the annual costs that this value would result in. The results on these 100 alternative realities is shown in the plot below.
We observe that the deterministic solution never beats the stochastic solution, even though the distributional assumptions are partly massively off. Moreover, on average the deterministic solution creates annual costs of $1.1 million while the Seeker solution costs only $502 thousand.
That is to say: Even when our distributional assumptions are off in shape, average, and in variance, on average the stochastic solution still beats the deterministic by a factor of 2. And it never performs worse.
Can you afford deterministic solutions that are over 100% suboptimal? Yes? Then keep worrying that your distributional assumptions are off.
All others may stop worrying.