Minimizing Patient Waiting Time
Radiation oncology departments are chronically capacity-constrained. A hospital typically owns only two or three linear accelerators (LINACs), yet must serve dozens of patients per day, each with a different treatment duration and a different level of clinical urgency (a pediatric emergency case cannot wait behind a routine follow-up). The scheduling question — which patient goes on which machine, and in what order — directly determines how long people sit in the waiting room before they can start treatment.
This is a textbook instance of the unrelated/identical parallel-machine scheduling problem with weighted waiting time minimization, which is NP-hard in general. In this article we build a concrete example with 16 patients and 3 LINAC machines, solve it with a metaheuristic optimizer, and compare it against the naive first-come-first-served (FCFS) policy that many clinics still use informally.
Problem Formulation
Let $P = {1, \dots, n}$ be the set of patients and $M = {1, \dots, m}$ the set of LINAC machines. Each patient $i$ has:
- a treatment session duration $p_i$ (minutes),
- an arrival / ready time $r_i$ (minutes after the department opens),
- a clinical urgency weight $w_i$.
We must decide a start time $S_i \ge r_i$ and machine assignment for every patient such that no two patients overlap on the same machine. The objective is:
$$
\min \sum_{i \in P} w_i \left(S_i - r_i\right)
$$
subject to, for every pair of patients $i,j$ sharing a machine:
$$
S_i + p_i \le S_j \quad \text{or} \quad S_j + p_j \le S_i
$$
This is a generalization of the classical $1 ,|, \sum w_i C_i$ scheduling problem, and with parallel machines it becomes combinatorially explosive very quickly ($m^n$ machine assignments alone), so exact enumeration is impractical even for modest $n$.
Solution Approach: Random-Key Encoding + Differential Evolution
Rather than optimizing discrete assignments directly, we use a well-known trick from genetic-algorithm literature called random-key encoding:
- Every patient $i$ is given a continuous “priority key” $k_i \in [0,1]$.
- A decoder sorts patients by key value (highest priority first) and greedily assigns each one, in that order, to whichever machine becomes free earliest — but never before the patient’s own arrival time $r_i$.
- This decoding step always produces a 100% feasible schedule, no matter what the key vector looks like.
Because the decoder guarantees feasibility, the search problem reduces to optimizing a continuous vector $\mathbf{k} \in [0,1]^n$, which is exactly what scipy.optimize.differential_evolution (DE) is built for. DE explores the key space with mutation and crossover across a population of candidate vectors, and the decoder translates each candidate into a real, evaluable schedule.
Compared to a full mixed-integer programming formulation, this approach avoids exponential blow-up, decodes in $O(n \log n)$ time, and consistently finds strong (though not provably optimal) solutions within a few hundred generations — well within Google Colab’s free-tier time budget.
Full Source Code
1 | """ |
FCFS total weighted wait : 987.0 patient-weighted-minutes Optimized total weighted wait : 570.0 patient-weighted-minutes Improvement : 42.25 % ID Machine Arrival Start Wait Weight P02 1 15 15 0 1.0 P07 3 22 22 0 5.0 P16 2 27 27 0 5.0 P11 3 48 48 0 2.0 P15 1 54 54 0 3.0 P05 2 60 66 6 3.0 P01 3 62 79 17 2.0 P04 1 54 91 37 2.0 P09 2 94 94 0 3.0 P10 3 77 96 19 1.0 P03 3 101 113 12 3.0 P08 2 112 115 3 3.0 P14 1 53 119 66 2.0 P12 3 99 148 49 1.0 P06 2 44 151 107 1.0 P13 1 65 157 92 1.0
Code Walkthrough
Section 0–1 (setup and problem data): We fix a random seed so the example is fully reproducible, then generate 16 synthetic patients with randomized session durations (15–45 minutes), arrival times spread across a two-hour window, and urgency weights drawn from a skewed distribution — most patients are routine (weight 1), a smaller number are moderately urgent, and a rare few are high-priority cases (weight 5). Three LINAC machines are available, matching a typical mid-sized radiation oncology department.
Section 2 (decoder): decode_schedule is the heart of the encoding trick. Given any vector of priority keys, it processes patients from highest key to lowest, and at each step assigns the current patient to whichever machine becomes idle earliest (np.argmin(machine_free)), while respecting that treatment cannot start before the patient physically arrives. This guarantees a valid, non-overlapping schedule for any input vector, which is exactly the property differential evolution needs to search freely without generating invalid candidates. fcfs_schedule is the same list-scheduling logic but with a fixed processing order (arrival time), representing the naive baseline most clinics fall back to without formal optimization.
Section 3–4 (objective and optimizer): The objective sums each patient’s waiting time weighted by clinical urgency. differential_evolution searches the 16-dimensional key space; because the decoder is $O(n \log n)$ and trivial to evaluate, even a population of 15 candidates over 200 generations evaluates in well under a second per generation, keeping total runtime short on Colab’s CPU. updating="deferred" combined with workers=1 keeps the search deterministic and reproducible given the fixed seed, while still allowing you to switch to workers=-1 for parallel evaluation if you scale up the patient count. The de_callback function records the best objective value at every generation for the convergence plot, and is written to tolerate both older and newer SciPy callback signatures so it won’t break regardless of the SciPy version bundled with your Colab runtime.
Section 5–8 (results and visualization): After optimization, we decode the best key vector into a concrete final schedule, compute the FCFS baseline for comparison, and print a per-patient summary table together with the percentage improvement in total weighted waiting time.
Graph 1 — 3D Gantt Chart of the Optimized Schedule
This chart plots each LINAC machine along the x-axis and time-of-day along the y-axis, with each patient’s treatment session rendered as a 3D bar whose length corresponds to session duration. Bar color encodes clinical urgency (brighter/warmer colors from the plasma colormap indicate higher-priority patients). This view lets you visually confirm two things at a glance: that no two bars overlap in time on the same machine (feasibility), and that the optimizer tends to slot high-urgency patients earlier and pack sessions tightly to avoid idle machine time.
Graph 2 — Per-Patient Waiting Time: Baseline vs Optimized
A direct side-by-side bar comparison of how long each individual patient waits under FCFS versus the optimized schedule. This is often the most persuasive chart for hospital administrators, since it shows concretely which patients benefit — typically the high-weight, urgent cases see their waiting time drop sharply, sometimes at the cost of slightly longer waits for low-priority routine patients, which is the intended clinical trade-off.
Graph 3 — Differential Evolution Convergence
This line plot tracks the best (lowest) weighted waiting time found at each generation of the optimizer. A healthy convergence curve should drop quickly in the first few dozen generations and then flatten out as the population converges toward a strong local optimum. If your curve is still steeply decreasing at generation 200, that’s a signal to increase maxiter; if it flattens out well before generation 200, you can safely reduce maxiter to shorten runtime without sacrificing solution quality.
Graph 4 — Sensitivity Surface: Machine Count vs Patient Load
This is a genuine capacity-planning tool. The surface plots total weighted waiting time as a function of two variables a hospital administrator actually controls or forecasts: the number of LINAC machines installed, and a “load factor” scaling how long treatment sessions run on average (a proxy for case-mix complexity, e.g. more proton therapy or IMRT cases with longer setup times). Reading across the surface at a fixed load factor shows the diminishing-returns curve of adding machines — useful for justifying (or questioning) capital equipment purchases. Reading along a fixed machine count shows how sensitive the department is to creeping session durations, which is valuable for staffing and throughput planning.
Conclusion
Framing LINAC scheduling as a weighted parallel-machine problem and solving it with a random-key differential evolution approach turns an informal, often first-come-first-served process into a quantifiable optimization with measurable improvement. The same decoder-plus-metaheuristic pattern generalizes well beyond radiation oncology — it applies equally to CT/MRI scanner scheduling, operating room allocation, or any other constrained clinical resource where patient urgency and equipment availability must be balanced against waiting time.
