The scheduling of radiation therapy is a complex problem that significantly impacts patient outcomes and the use of healthcare resources. This paper proposes a novel formalization of the radiotherapy scheduling problem (RTSP) as a modified one-dimensional bin-packing problem (BPP). This formalization ofers several advantages, including leveraging state-of-the-art solvers for the one-dimensional BPP and extending the formulation to various BPP variants that align with the complexities of the RTSP. Preliminary results on a synthetic instance demonstrate the feasibility of the proposed approach.
LGOBE (M. Roveri) https://sites.google.com/site/giovanniiacca (G. Iacca); https://sites.google.com/view/marco-roveri (M. Roveri)
CEUR
ceur-ws.org staf. Stochastic EBP can further capture the innate variability in treatment times arising from preand post-treatment procedures.
The remainder of the article is organized as follows. Section 2 presents the background concepts on the RTSP and the main formalization of the BPP. Section 3 describes our proposed formalization for the RTSP, which is the main contribution of this paper. Section 4 summarizes the relevant related works on the scheduling of healthcare operations and, more deeply, on radiotherapy scheduling. Section 5 shows the preliminary results of our new formalization, starting from a synthetic instance solved with an Integer Linear Programming (ILP) solver. Finally, Section 6 ends this article.
Hereafter we first briefly summarize the main concepts of radiotherapy and its workflow, then we briefly present the BPP.
Radiotherapy is a cancer treatment that involves the use of radiation to attack and kill cancer cells. Since radiation has limited precision, although research in the field has advanced considerably, it is the responsibility of doctors and medical physicists to test and calibrate both the radiation doses and the position of the machine in relation to the patient’s body as efectively as they can. Optimizing the workflow that goes from the time the tumor is diagnosed and the choice of radiotherapy as a treatment to the actual moment the patient undergoes it is therefore of paramount importance. Figure 1 visually shows the macro-stages of a typical radiotherapy workflow, which are briefly described below: • Consultation: After the patient is diagnosed with the tumor and radiation therapy is recommended as treatment, a preliminary consultation is conducted between the patient and the radiotherapist. • Scanning: As the consultation ends with positive feedback from both the patient and the radiotherapist, the pre-treatment flow starts. Firstly, the patient undergoes a series of scans to delineate the tumor’s position. • Image Post-Processing: The resulting image of the scan is post-processed to become as usable and understandable as possible. • Contouring: At this point, the contouring phase starts: the scanned image, after being post-processed, is then used to contour the tumor. This phase is actually very delicate, as the contouring continuously undergoes a review to make sure that it is perfectly executed. • Treatment Planning: The final phase before starting the treatments is used to define the treatment planning. In this context, the dose distribution and the plan for the radiotherapy sessions are decided. • Treatment: After all the pre-treatment phases are completed, the actual treatment can start. This last phase is crucial, as the schedule of the treatment sessions can significantly impact the patient’s health and well-being.
The above-mentioned phases underline the importance of developing a formalization for the RTSP that allows the optimization of the entire radiotherapy workflow. Sub-optimal solutions to this problem can in fact lead to significant disruptions for patients, including long waiting times, underutilized equipment, and disruptions due to unforeseen events.
Parameters
( = 1, … , ) ( = 1, … , ) ( = 1, … , ) ( = 1, … , ; = 1, … , ) =1 ∑ = 1 ∀ ∈ [1, … , ]
The one-dimensional BPP is one of the most known and studied combinatorial problems, known to belong to the class of NP-hard problems. In the BPP, objects of diferent sizes must be packed into a ifnite number of bins or containers of fixed capacity, in order to minimize the number of bins used. It is a combinatorial problem with several areas of application, e.g., in logistics, cloud computing, and resource allocation. It can be formalized as a linear programming problem [2]: We propose a new formulation of the one-dimensional BPP which is used to formalize the RTSP. In this new formulation, each item is part of a group, and all items within the same group must be packed together in consecutive groups of bins. The bins are also grouped, with each group containing a fixed number of bins with a set capacity. When packing items from a group , each item must be placed in any bin within a group that has enough space. In a further development of the problem, some constraints on which bin of the group can be used for item may arise. This problem can be expressed as a linear programming model: min ∑
=1 = 1 ∀ ∈ [1, … , ], ∀ ∈ [1, … ,
] ≤ , , ∀ ∈ [1, … , ], ∀ ∈ [1, … ,
] size of item of group capacity of bin of group maximum bins’ number for each group sets of bins allowed for each group 1 if bin of group is used, 0 otherwise 1 if item of group is packed in bin of group , 0 otherwise
1 if a bin of group is used, 0 otherwise,
i.e. 1 if ∑=1 , ≥ 1, 0 otherwise
(
− 1], ∀ ∈ [1, … , − 1] ∖ ∑ ,,, ∑ , ≤
∀ ∈ [1, … , ] 1 − ∑ , ≤ (1 − )
∀ ∈ [1, … , ]
= 0
∀ ∈ [1, … , ], ∀ ∈ [1, … , ], ∀ ∈ [1, … ,
]
The objective presented in Equation (
A visual example of the proposed modified BPP is shown in Figure 3. Diferent colors indicate
diferent groups of items. Each item in a group has a number identifying it. It can be seen how each
item in a group is packed consecutively, as stated in Equation (
The RTSP can be straightforwardly mapped to this modified one-dimensional BPP formulation. In fact, each is a patient and each fraction is an item . Each group of bins corresponds to a day and each bin in a group is a specific machine for the day . For what concerns the availability of machines in terms of maintenance and in terms of medical personnel that can use the machine, it can be modulated by varying the capacity of the bin that correspond to that machine in that specific day. In a broader view, all the workflow of the patient radiotherapy can be formulated as our modified BPP, by adding some more constraints.
In this section, we first introduce articles that tackle the wider topic of healthcare scheduling, and
then we deepen the literature for the RTSP. We categorize those works into (
Healthcare scheduling. In the last few years, several research eforts have been carried out to develop healthcare resource allocation decision support tools. For example, Kokangul [3], Oddoye et al. [4], Zhang et al [5], Ma and Demeulemeester [6], and Holm et al. [7] developed tools for solving the bed capacity problem. Instead, Wang et al. [8] conducted a study related to operating room capacity. Ordu et al. [9] followed a forecasting-simulation-optimization approach for optimizing the level of resources of a National Health Service. Concerning the problem of patient appointments, Squires et al. [10] developed a novel genetic algorithm for the scheduling of repetitive Transcranial Magnetic Stimulation (rTMS) appointments.
Workflow scheduling. For the specific case of planning and scheduling of patients’ treatments in radiotherapy, there are several studies that have explored the field. Some authors explored the scheduling of the entire radiotherapy process. For instance, Petrovic et al. [11] developed three patientpriority GAs to schedule the entire radiotherapy process–from consultation to treatment–aiming to (i) minimize patient waiting times and (ii) minimize breaches of waiting time targets. These objectives were normalized and weighted using a scalarization approach. Their model considers real-life constraints like doctors’ schedules, machine availability, patient categories, and waiting time targets. Vieira et al. focused on specific stages of radiotherapy. Firstly, they introduced a stochastic Mixed-Integer Linear Programming (MILP) model to optimize the allocation of radiation therapist technologists (RTTs) during pre-treatment, considering stochastic patient inflows [ 12]. Later, they developed a MILP model to develop weekly treatment schedules, taking patient time window preferences into account [13]. Eventually, this model was tested on real data from two radiotherapy centers, where it demonstrated improved performance by reducing LINAC switches and better aligning with patient preferences compared to manual scheduling methods [14]. More recently, Hofmans-Holtzer et al. combined a multiobjective Genetic Algorithm (NSGA-II) with MILP to optimize pre-treatment preparation scheduling [15]. Their model balances average patient preparation time with the risk of overtime, ofering tactical decision-making insights based on factors like patient volume, staf composition, and clinic hours. Appointment scheduling. Several works have focused solely on scheduling radiotherapy treatment appointments, bypassing the pre-treatment phases. The majority of these works focused on using Operational Research approaches. Early work by Conforti et al. [16] formulated the scheduling problem as an ILP, focusing on maximizing the number of patients to be scheduled under four conditions: (i) patient priority, (ii) number of treatment sessions, (iii) consecutive treatment days, and (iv) treatment duration in weeks. Later, they added minimizing patient waiting times as an objective [17], and then further extended the initial model to incorporate patient availability [18]. Sauré et al. formulated the RTSP as a discounted infinite-horizon Markov Decision Process (MDP) model [ 19]. They expanded the work by Partick et al. [20] by introducing multiple appointment requests, diferent session durations, and allowing overtime. They transformed the MDP into a Linear Programming (LP) model and solved its dual problem using the Column Generation (CG) algorithm. More recently, Pham et al. proposed a twophase approach: first, assigning sessions to specific LINACs and days using ILP, and then deciding the sequence of patients on each day/LINAC and the specific appointment times with MILP and Constraint Programming models [21]. This approach was tested on data from CHUM, a large cancer center in Montréal. Finally, Frimodig et al. compared three optimization methods: (i) Integer Programming (IP), (ii) Column Generation IP (CG-IP), and (iii) Constraint Programming, focusing on minimizing waiting times and maximizing patient preference fulfilment [ 22]. They also modeled urgent patient arrivals and machine interruptions. A later study by the same authors focused specifically on the Column Generation algorithm, addressing additional constraints such as machine compatibility, individualized protocols, and multiple hospital sites [23].
Online appointment scheduling. Another challenge in radiotherapy scheduling is the continuous and uncertain arrival of patients. Legrain et al. addressed this by integrating patient arrival uncertainty into a method that combines stochastic and online optimization [24]. Their model utilizes future patient arrival information to better predict resource utilization, adapting an online stochastic algorithm developed by Legrain and Jaillet [25] for real-world radiotherapy scheduling, to determine the initial treatment day and time slot on a LINAC. Additionally, Braune et al. considered the uncertainty of patient preparation and exit times during treatment scheduling [26]. They developed a model for planning appointment times under uncertain duration, employing a combination of GAs and Monte Carlo simulations to heuristically solve the problem.
Appointment scheduling formalizations. In the context of radiotherapy, Vogl et al. modeled treatment appointments at an ion beam facility as a modified job shop scheduling problem (JSP) [ 27]. They established custom constraints and aimed to minimize the operation time of the bottleneck resource, the particle beam, while also reducing violations of time window constraints. To solve this problem, they employed three metaheuristic methods: (i) a GA, (ii) Iterated Local Search, and (iii) a combination of the two.
While previous research has explored the JSP paradigm for ion beam therapy, our work focuses on traditional RTSP. Unlike the first, where treatments require precise start times, the latter primarily involves assigning patients to suitable treatment days and then finding the best start times. p1 p2 p3 p4 p5
Machine m1 m2
This section introduces and explains the synthetic instance created to generate preliminary results to test the proposed formalization.
Synthetic instance We created a synthetic instance, as shown in Table 1, composed of 5 patients with 5 fractions each, which can be allocated on two machines whose capacities are reported in Table 2. Each patient has a diferent duration for the fractions, and the duration of the first fraction is always twice as long as that of the other fractions, since the first time the patient undergoes radiotherapy treatment, they need more time for positioning. Each patient also has a set of allowed machines, which are in total two with diferent capacities each day, as shown in the “Previous Occupation” column in Table 3. When completely unloaded, without previous scheduled appointments, the machines have a maximum capacity of 25 minutes.
Numerical results To validate the proposed formulation, we implemented a prototype using Google OR-Tools1 with the SCIP solver [28] in Python 3.12. The prototype has been run on a MacBook Air with an Apple M1 chip, 8 cores, and 16 GB of RAM. The solver was configured with the constraints and objective described in Section 3. Table 3 presents the results of solving the problem instance described in Section 5. The schedule optimizes patient assignments to machines while adhering to machine restrictions and minimizing treatment days.
day 1 day 2 day 3 day 4 day 5 day 6 day 7 day 8 m1 [(Frac n°, Patient)] [] [(1, ’p1’)] [(2, ’p1’), (1, ’p3’)] [(2, ’p3’), (1, ’p5’)] [(4, ’p1’), (3, ’p3’), (2, ’p5’)] [(5, ’p1’), (4, ’p3’), (3, ’p5’)] [(5, ’p3’), (4, ’p5’)] [(5, ’p5’)]
Prev.
Occ. 0 min 5 min 5 min 0 min 5 min 0 min 0 min 5 min
Plan Occ. 0 min 12 min 20 min 21 min 20 min 20 min 14 min 7 min m2 [(Frac n°, Patient)] [(1, ’p4’)] [(2, ’p4’)] [(1, ’p2’), (3, ’p4’)] [(3, ’p1’), (2, ’p2’), (4, ’p4’)] [(3, ’p2’), (5, ’p4’)] [(4, ’p2’)] [(5, ’p2’)] []
Prev.
Occ. 0 min 10 min 0 min 5 min 0 min 0 min 0 min 0 min
Plan Occ. 10 min 5 min 21 min 19 min 13 min 8 min 8 min 0 min
This paper introduced a novel approach to formalizing the RTSP as a modified one-dimensional BinPacking Problem. The proposed formalization is designed to exploit the research and algorithms developed for the one-dimensional BPP to address the challenges of the RTSP. By mapping radiotherapy 1https://developers.google.com/optimization treatments to items and the LINAC to a bin, we established a clear correlation between these two problems. The proposed formulation ofers several advantages, including the ability to leverage state-ofthe-art solvers used for the plain one-dimensional BPP and the possibility of extending the formulation to other extensively studied versions of the BPP to tackle the complexities of the RTSP.
Future work includes evaluating the performance of the proposed formulation on real-world RTSP instances, incorporating patient priorities and uncertainties in treatment times, and tailoring existing one-dimensional BPP algorithms to the specific requirements of the new formulation. A practical enhancement could involve integrating physicians’ expertise to refine the model’s objectives and constraints, leading to more clinically feasible and optimal treatment plans. In conclusion, this paper provides a promising foundation for addressing the complex problem of radiotherapy scheduling. By leveraging the power of the one-dimensional BPP, we can potentially improve the eficiency and efectiveness of cancer treatment.
This work has been partially supported by the PNRR project FAIR - Future AI Research (PE00000013), the NRRP MUR program funded by the NextGenerationEU, and by the project MUR PRIN 2020 - RIPER - Resilient AI-Based Self-Programming and Strategic Reasoning - CUP E63C22000400001. [11] D. Petrovic, M. Morshed, S. Petrovic, Multi-objective genetic algorithms for scheduling of radiotherapy treatments for categorised cancer patients, Expert Systems with Applications 38 (2011) 6994–7002. [12] B. Vieira, D. Demirtas, J. B. van de Kamer, E. W. Hans, W. van Harten, A mathematical programming model for optimizing the staf allocation in radiotherapy under uncertain demand, European journal of operational research 270 (2018) 709–722. [13] B. Vieira, D. Demirtas, J. B. van de Kamer, E. W. Hans, L.-M. Rousseau, N. Lahrichi, W. H. van Harten, Radiotherapy treatment scheduling considering time window preferences, Health care management science 23 (2020) 520–534. [14] B. Vieira, D. Demirtas, J. B. van de Kamer, E. W. Hans, W. Jongste, W. van Harten, Radiotherapy treatment scheduling: Implementing operations research into clinical practice, Plos one 16 (2021) e0247428. [15] N. Hofmans-Holtzer, L. Smolenaers, M. Olofsen-van Acht, M. Hoogeman, M. Balvert, S. Petit, Robust optimization of a radiotherapy pretreatment preparation workflow, Physics in Medicine & Biology 69 (2024) 025022. [16] D. Conforti, F. Guerriero, R. Guido, Optimization models for radiotherapy patient scheduling, 4or 6 (2008) 263–278. [17] D. Conforti, F. Guerriero, R. Guido, Non-block scheduling with priority for radiotherapy treatments,
European Journal of Operational Research 201 (2010) 289–296. [18] D. Conforti, F. Guerriero, R. Guido, M. Veltri, An optimal decision-making approach for the management of radiotherapy patients, OR Spectrum 33 (2011) 123–148. [19] A. Saure, J. Patrick, S. Tyldesley, M. L. Puterman, Dynamic multi-appointment patient scheduling for radiation therapy, European Journal of Operational Research 223 (2012) 573–584. [20] J. Patrick, M. L. Puterman, M. Queyranne, Dynamic multipriority patient scheduling for a diagnostic resource, Operations research 56 (2008) 1507–1525. [21] T.-S. Pham, L.-M. Rousseau, P. De Causmaecker, A two-phase approach for the radiotherapy scheduling problem, Health Care Management Science (2022) 1–17. [22] S. Frimodig, P. Enqvist, M. Carlsson, C. Mercier, Comparing optimization methods for radiation therapy patient scheduling using diferent objectives, in: Operations Research Forum, volume 4, Springer, 2023, p. 83. [23] S. Frimodig, P. Enqvist, J. Kronqvist, A column generation approach for radiation therapy patient scheduling with planned machine unavailability and uncertain future arrivals, arXiv preprint arXiv:2303.10985 (2023). [24] A. Legrain, M.-A. Fortin, N. Lahrichi, L.-M. Rousseau, Online stochastic optimization of radiotherapy patient scheduling, Health care management science 18 (2015) 110–123. [25] A. Legrain, P. Jaillet, Stochastic online bipartite resource allocation problems, CIRRELT, 2013. [26] R. Braune, W. J. Gutjahr, P. Vogl, Stochastic radiotherapy appointment scheduling, Central
European Journal of Operations Research (2022) 1–39. [27] P. Vogl, R. Braune, K. F. Doerner, Scheduling recurring radiotherapy appointments in an ion beam facility: Considering optional activities and time window constraints, Journal of Scheduling 22 (2019) 137–154. [28] S. Bolusani, M. Besançon, K. Bestuzheva, A. Chmiela, J. Dionísio, T. Donkiewicz, J. van Doornmalen, L. Eifler, M. Ghannam, A. Gleixner, C. Graczyk, K. Halbig, I. Hedtke, A. Hoen, C. Hojny, R. van der Hulst, D. Kamp, T. Koch, K. Kofler, J. Lentz, J. Manns, G. Mexi, E. Mühmer, M. E. Pfetsch, F. Schlösser, F. Serrano, Y. Shinano, M. Turner, S. Vigerske, D. Weninger, L. Xu, The SCIP Optimization Suite 9.0, Technical Report, Optimization Online, 2024. URL: https://optimization-online.org/2024/02/ the-scip-optimization-suite-9-0/.