Introduction
Radiotherapy is a critical component of modern cancer care, yet the logistics of scheduling treatments remain a significant hurdle for clinical efficiency. At the AI4CC-IPS-RCRA-SPIRIT 2024 workshop, researchers presented a novel approach to this problem by formalizing the Radiotherapy Treatment Scheduling Problem (RTSP) as a modified one-dimensional Bin-Packing Problem (BPP). This mathematical reframing allows clinicians to leverage mature optimization algorithms to improve patient throughput and reduce waiting times.
The Radiotherapy Scheduling Challenge
Scheduling radiotherapy is inherently complex due to the multi-step nature of the treatment pipeline and the strict clinical constraints involved. Patients must undergo a series of pre-treatment steps, including consultation, scanning, and contouring, before the actual radiation delivery begins.
Once treatment starts, patients require multiple "fractions" (doses) delivered over consecutive days. Clinics operate with a limited number of Linear Accelerators (LINACs), each with fixed daily hours. The scheduling task must balance three primary factors:
- Urgency: Minimizing the time between referral and the start of treatment.
- Clinical Constraints: Ensuring fractions occur on consecutive days and matching patients to compatible machines.
- Scalability: Moving beyond manual scheduling or metaheuristic approaches that lack optimality guarantees.
Methods: Mapping Scheduling to Packing
The core innovation of this research is the translation of temporal scheduling into a spatial packing problem. In this model, time is treated as a resource to be "packed" into containers.
The authors map the medical domain to the BPP framework as follows:
- Items & Sizes: Each treatment fraction is an item, with its duration representing its "size."
- Item Groups: All fractions belonging to a single patient are grouped together.
- Bins & Capacity: Each LINAC machine acts as a "bin," with its daily operating hours defining its "capacity."
- Bin Groups: Machines available on a specific calendar day form a "group of bins."
To adapt the standard BPP for clinical use, the authors introduced several specialized constraints. The Consecutive Constraint ensures that sequential fractions are scheduled on consecutive calendar days. Machine Eligibility constraints ensure patients are only assigned to compatible LINACs. The primary objective of the resulting Integer Linear Programming (ILP) model is to minimize the total number of days required to complete the treatment set.
Validation and Results
The model was validated using a synthetic clinical instance involving five patients, each requiring five fractions, across two machines with varying capacities. To reflect clinical reality, the first fraction for each patient was modeled as twice the duration of subsequent fractions to account for initial setup and positioning.
Using the SCIP solver via Python, the researchers successfully generated a valid 8-day schedule. The results demonstrated that the model could perfectly adhere to machine eligibility, fraction durations, and the consecutive-day requirement, even when accounting for "Previous Occupation" (pre-existing clinical appointments).
Future Outlook
While the initial results are promising, the study identifies several areas for expansion. The current model is deterministic and was tested on a small scale. Future work will focus on scaling the formulation against real-world datasets involving hundreds of patients and incorporating variability in treatment and preparation times. By bridging the gap between medical logistics and combinatorial optimization, this work provides a scalable foundation for automating one of the most bottlenecked processes in oncology.
Summary updated