02.07.2018  Ausgabe 2/2019 Open Access
Scheduling recurring radiotherapy appointments in an ion beam facility
Considering optional activities and time window constraints
 Zeitschrift:
 Journal of Scheduling > Ausgabe 2/2019
1 Introduction
The worldwide number of patients diagnosed with cancer has steadily increased over the past decade, from approximately 10 million cases (and 6 million deaths) in 2003 to around 14.1 million cases (8.2 million deaths) in 2012 (Steward and Wild
2014). Projections for 2030 range between 17.1 and 22.2 million cases, which equals an increase of 21.3–57.4% (see Bray et al.
2012; World Health Organization
2012). Radiation therapy, or short radiotherapy, is commonly prescribed in addition to or instead of chemotherapy or surgery. The goal is to deliver a maximum amount of radiation to kill the cancer while sparing the healthy tissue surrounding the tumorous region (Washington and Leaver
2016). In classical photon radiotherapy, which is available in virtually every hospital worldwide, radiation is delivered using a linear particle accelerator (linac) that supplies Xrays. More advanced but less numerous ion beam centers [only roughly 70 centers exist in the world, 48 of which have multiple treatment rooms, see PTCOG (
2017)] use protons and/or carbon ions to achieve superior dose conformity and thereby lower the chances of patients developing secondary tumors later in life (Ohno
2013). However, because these ion beam centers also use significantly larger particle accelerators, their operations are much more costly than is classical radiotherapy using linacs and the efficient usage of the beam resource is crucial.
In this paper, we analyze and solve a realworld radiotherapy scheduling problem arising in a recently opened, specialized ion beam center close to Vienna, Austria, which offers two particle types for radiation treatment: protons and carbon ions. It plans to treat approximately 1000 patients per year. A radiation treatment consists of both a pretreatment phase and the irradiation treatment phase itself. During the pretreatment phase, multiple examinations take place, followed by intensive treatment planning, during which radiooncologists (RO), together with medical physicists, determine the dose of one treatment activity (called a “fraction”) and the number of fractions a patient should receive. They also define the particle type used and develop a socalled immobilization device, which helps the patient lie still during the treatment. The treatment phase then consists of a fixed number of daily treatment activities, imaging, and examination appointments, all of which require multiple resources simultaneously. Assigning treatments to days and scheduling the exact starting times of the activities to maximize facility usage and thereby minimize patients’ waiting times before they start treatment is of utmost importance.
Anzeige
The problem can be formalized as a complex job shop scheduling problem with multiple custom constraints that need to be considered. We introduce recurring optional appointments that, to the best of our knowledge, have not been considered in radiotherapy treatment scheduling before. Furthermore, we consider time windows between each activity for a patient that guarantee stable start times during the treatment phase. As solution techniques, we present three metaheuristics, namely a genetic algorithm and an iterated local search, whose operators are tailored to the problem at hand, as well as a combination of these two approaches in a third algorithm. In doing so, we achieve a highly effective method to solve the problem of scheduling recurring radiotherapy appointments in the ion beam facility. The time horizon of realworld problem instances reflects various weeks and contains up to 10,000 activities to be scheduled. Due to the high problem complexity of the longterm planning and the lack of reliable longterm stochastic data, we solve the problem deterministically. Future research will be dedicated to stochastic optimization of radiotherapy schedules for a given day
d, because various disruptions can occur during the execution of a given schedule (e.g., room unavailability for a longer period). More specific data on past activity durations for a given patient then would be available (e.g., treatment duration of first five treatments took 12 min instead of estimated 8 min in the longterm planning) and could be used to revise the longterm schedule.
This article is organized as follows: Sect.
2 presents the formal problem statement of the radiotherapy patient scheduling problem (RPSP) and discusses the constraints that arise at ion beam facilities in particular. Section
3 gives insight into related work on the radiotherapy patient scheduling problem. Section
4 is devoted to the mathematical programming formulation of the underlying scheduling problem. In Sect.
5, we discuss the three heuristical solution methods—two standalone methods and one hybrid algorithm—the results of which are in Sect.
6. Finally, Sect.
7 offers some conclusions and proposes possible extensions to our work.
2 Problem statement
Ion beam facilities are typically equipped with one particle beam that serves multiple treatment rooms, as shown in Fig.
1. It depicts the specific problem setting we address, consisting of three treatment rooms with (1) horizontally directed, (2) vertically and horizontally directed, and (3) 180degree rotatable particle beams. The particle beam—consisting of either protons or carbon ions—first moves through a linear accelerator, followed by multiple circulations through the synchrotron, where the beam gets accelerated to twothirds of the speed of light, until it finally moves to one of the three treatment rooms. The beam can only serve one room at a time though, so we consider the particle beam the bottleneck resource in the irradiation process. Switching between the two mentioned particle types also requires a setup time of 3 min.
×
×
×
The treatment of one patient
\(p \in {\mathcal {P}}\) consists of a predefined number of recurring (almost) daily irradiation appointments [daily treatments, (DTs)] with fixed duration and resource requirements (e.g., treatment room, particle type, assigned RO). A patient needs to attend, on average, 20 daily treatments with an average irradiation duration of 8–10 min, depending on the particle type. Some patients need to attend regular, additional imaging appointments [positron emission tomography (PET)] directly after the DTs to ensure the accuracy of the irradiation treatment. Between DTs, patients regularly (i.e., once within a span of five consecutive days during the treatment phase) see their assigned RO for a control examination [weekly control examination (WCE)]. The sequence of these activities is fixed, as is shown by the “activity chain” in Fig.
2, where “FDT” and “LDT” denote the first and last DT, respectively. Note that both PET and WCE are listed after each DT in the activity chain. These activities are optional in the sense that they must take place once within every span of five consecutive days, but the optimization algorithm must determine which WCE and PET activities should be scheduled and which ones can be skipped.
×
Anzeige
The FDT must be scheduled between the patient’s specific release date and due date. As mentioned, the irradiation appointments then take place almost every day, and only one DT can take place per day. Although the total number of DTs,
\(N_p^\mathrm{DT}\), is fixed by the RO, the days to which the treatments are assigned may vary slightly: starting from the FDT until the day of the LDT, patients need at least four irradiation treatments within every span of five consecutive days. The treatment phase then corresponds to the time period between the FDT and the LDT.
Each DT activity consists of three inseparable tasks: (1) a setup time, in which the patient is prepared for the treatment inside the treatment room; (2) the irradiation itself, which requires the use of both the beam resource and the treatment room; and (3) a teardown time, during which only the treatment room is occupied. These three phases are depicted in Fig.
3. Scheduling two patients that require the same treatment room consecutively therefore causes extensive idle time on the beam resource (teardown time of the first patient and setup time of the second patient). Note, however, that the sum of the setup and teardown times equals an average of 18 min, whereas a treatment takes on average 8–12 min, depending on the particle type. Therefore, even alternating between two rooms would lead to beam idle time. An ideal schedule would interleave the three rooms, as depicted in Fig.
4. Here, even though the proposed scheduling pattern applies in the beginning, idle time on the beam resource between patient 4 and patient 5 is
unavoidable, because patient 5 could not have started his setup in room 2 earlier. (The room was still blocked by the teardown of patient 2). The same applies to the idle time between patients 6 and 7. This situation makes it considerably harder to calculate a reasonable lower bound for the objective value, reflecting the total operation time of the beam (see Maschler et al.
2018, whose work is inspired by the same realworld problem).
The treatment activities within the activity chain of one patient are tied together using minimum and maximum time lags (“finishstart relations”). For example, to deliver accurate results, a PET appointment must start no later than 15 min after the preceding DT irradiation has finished. To maximize the patient’s convenience, the DT activities also should take place at approximately the same time on every treatment day during a week. We therefore introduce a daytime window for each week a patient receives treatment, which is defined by its midpoint. We call this midpoint the “stable starting time,” as the approximate time a patient comes in for treatment on each day of the given week. Only deviations smaller than 30 min from the defined stable starting time are accepted, creating an even tighter time window for the DT activities. Furthermore, the stable starting times of two consecutive weeks may only differ by a maximum of 4 h, allowing for changed approximate treatment times between weeks. Violations of the time windows formed by both finishstart relations and stable starting times result in penalties in the objective function.
Finally, some activities can be executed on alternative resource sets. For example, it might be preferable for the patient’s assigned RO to perform the WCE, but if he or she is busy, any other RO on duty can undertake the examination.
We aim to minimize the total operation time of the beam resource, which consists of the active time and the induced idle time and potential setup time due to particle switches, while the actual number of patients to be treated is determined by the doctors and is not part of the optimization. We thereby produce tight schedules which allow for the machine to be used for research in the field of medical physics and particle physics during the times when no patients are treated. Simultaneously, we minimize penalties arising from the belated starting times of activities that violate either general time window constraints or the patientspecific stable treatment starting time per week.
3 Related work
3.1 Radiotherapy scheduling
Appointment scheduling problems in health care systems arise in different environments, such as operating room scheduling, outpatient scheduling, and recurring treatment appointment scheduling (as in radiotherapy scheduling) (e.g., Gupta and Denton
2008). Radiotherapy scheduling in particular has attracted the interest of research groups during the past two decades. It first appeared in the literature in a review paper by Kapamara et al. (
2008), followed by basic algorithms for radiotherapy treatment booking proposed by Petrovic et al. (
2006). Various studies model this problem mathematically and solve it using standard Mixed Integer Programming (MIP) solvers (e.g., Conforti et al.
2008,
2010,
2011; Burke et al.
2011). The different heuristics applied to the problem vary from pure constructive and hill climbing approaches (Kapamara and Petrovic
2009) to greedy randomized adaptive search procedures (GRASP) (Petrovic and LeiteRocha
2008a) and (multiobjective) genetic algorithm (GA) approaches (Petrovic et al.
2009,
2011). Some authors focus on scheduling activities within the pretreatment phase and use linear programming, simple dispatching rules, and GAs to solve this appointment scheduling problem (Petrovic and Castro
2011; Castro and Petrovic
2012). In a Ph.D. thesis, LeiteRocha (
2011) summarizes research on radiotherapy scheduling prior to 2011 and proposes various extensions to their mathematical models.
More recent publications consider stochastic and dynamic attributes of the radiotherapy scheduling problem. Sauré et al. (
2012) formulate the model as discounted infinitehorizon Markov decision process to identify good policies for allocating capacity to incoming demand and thereby minimizing patient waiting times. Legrain et al. (
2015) integrate stochastic patient arrival times into their model and develop a hybrid stochastic and online optimization algorithm. Gocgun (
2016) also considers stochastic patient arrival times and introduces a simulationbased approximate dynamic programming approach to solve the problem. The Ph.D. thesis by Men (
2009) centers the analysis on the optimal mix of patients and diagnoses for an ion beam facility, to maximize the throughput of patients. Lately, Vieira et al. (
2016) published a literature review on radiotherapy resource planning and treatment scheduling and categorized the papers according to their hierarchy level, methods used, the extent of implementation and the potential impact on the performance. They conclude that future research could incorporate specialized clinical pathways and additional devices such as PETs.
This mentioned research stream thus mainly focuses on scheduling treatments for “classical” photon therapies, for which each treatment room is equipped with a distinct linear accelerator. Sequencing patients per day and thereby scheduling exact starting times for all patients is less crucial in these settings, and accordingly, two main strategies for scheduling activities within the treatment phase dominate prior literature:
This vast variation in treatment durations, as well as the bottleneck resource “particle beam” that is shared among various treatment rooms, necessitates scheduling exact (“totheminute”) starting times at ion beam facilities. Maschler et al. (
2016) propose a detailed scheduling approach using both a GRASP procedure and an iterated greedy approach, which incorporates interconnected day and time assignment phases. They extend the latter approach in a subsequent study and yield even better results on a midterm planning horizon (Maschler et al.
2017). However, they do not incorporate optional activities, and they focus on scheduling the core irradiation appointments. Using a surrogate model to estimate the lower bound for the time the beam resource is required if the patients treated on the specific day are known (i.e., the day assignment phase has already finished), Maschler et al. (
2018) also apply this information iteratively to optimize the day assignment.
1.
Assign treatments to days. This approach incorporates an average resource profile and does not schedule exact starting times on each day. Therefore, it requires a second step, namely patient sequencing per day (Petrovic and LeiteRocha
2008b; Men
2009; Conforti et al.
2010; Burke et al.
2011; Sauré et al.
2012).
2.
Split the day into time slots of predefined lengths (e.g., 15 or 30 min) and allocate the treatments to these time slots (i.e., “block scheduling,” Conforti et al.
2008,
2011; Legrain et al.
2015). This approach allows for the immediate consideration of stable activity starting times, but it also assumes that the treatment duration will be more or less equal to the length of the time slot, which is not the case in ion beam therapy, for which treatment durations vary substantially according to the diagnosis received by the patient.
4 Problem formulation
The objective function and constraints described in Sect.
2 can be formulated mathematically. Table
1 lists the symbols and sets used in the formulation of the problem; Table
2 summarizes all necessary input information; and Table
3 gives an overview of the decision variables of the mathematical modeling formulation.
Table 1
Sets of the mathematical modeling formulation
Notation

Description


Sets


\({\mathcal {P}}\)

Set of all patients, index
\(p \in \{1,\ldots ,P\}\)

\({\mathcal {O}}_p\)

Set of operations/activities of patient
p

\({\mathcal {R}}\)

General set of resources, index
\(r \in \{1,\ldots ,R\}\)

\({\mathcal {K}}_{pi}\)

Set of resource requirements for patient
p’s activity
i

\({\mathcal {R}}_{pik}\)

Set of eligible resources for activity
i and patient
p, and resource requirement
k. If only one (compulsory) resource is available, then
\({\mathcal {R}}_{pik}=1\)

\({\mathcal {D}}\)

Set of days in the planning horizon, index
\(d \in \{1,\ldots ,D\}\)

\({\mathcal {W}}\)

Set of weeks in the planning horizon, index
\(w \in \{1,\ldots ,W\}\)

\(\varPhi _p\)

Set of activities belonging to the subgroup of daily treatment activities for patient
p

\(\varPsi _p\)

Set of activities belonging to the subgroup of weekly control examination activities for patient
p

\(\Xi _p\)

Set of activities belonging to the subgroup of PET activities for patient
p

Table 2
Parameters and input variables to the mathematical modeling formulation
Notation

Description


Parameters and input variables


\(u_{piqjr}\)

Setup time between activity
i for patient
p and succeeding activity
j (patient
q) on resource
r

\(v_{pir}\)

Setup time of activity
i for patient
p on resource
r

\(w_{pir}\)

Teardown time of activity
i for patient
p on resource
r

\(\lambda _{pi}\)

Processing time of activity
i of patient
p on all resources

\(\hbox {FS}^{\mathrm{min}}_{pi,p(i+\delta )}\)

Minimum time from finish of activity
i to start of activity
\(i+\delta \)

\(\hbox {FS}^{\mathrm{max}}_{pi,p(i+\delta )}\)

Maximum time from finish of activity
i to start of activity
\(i+\delta \)

\(\underline{dw_d}\),
\(\overline{dw_d}\)

Begin and end of daytime window of day
d

\(\alpha '\)

Maximum intraweek variation from the stable starting time

\(\alpha ''\)

Maximum interweek variation from the stable starting time

\(r_p\)

Release day for patient
p’s FDT

\(d_p\)

Due day for patient
p’s FDT

M

Large number

Table 3
Variables of the mathematical modeling formulation
Notation

Description


Decision variables


\(h_{pikr}\)

Binary variable, set to 1 if activity
i of patient
p is assigned to resource
r for resource requirement
k

\(s_{pir}\)

Starting time of activity
i for patient
p on resource
r

\({\bar{s}}_{pi}\)

Starting time of activity
i for patient
p

\(y_{piqjr}\)

Binary variable for immediate successor of activity
i for patient
p (namely
qj) on resource
r

\(o_{pi}\)

Binary variable, indicating whether activity
i for patient
p takes place or not

\(\theta _{pid}\)

Binary variable, indicating whether activity
i takes place on day
d or not (
\(=1\) if
\(\underline{dw_d} \le {\bar{s}}_{pi} \le \overline{dw_d})\)

\(t_{pd}\)

Starting time of treatment for patient
p on day
d (independent of the activity
i, time between the start of daytime window and the scheduled starting time)

\({\widetilde{t}}_{pw}\)

Stable starting time of treatment for patient
p in week
w

\({\bar{x}}_{pd}\)

Binary variable, indicating whether day
d is within the treatment phase of patient
p

\({\bar{z}}_{pw}\)

Binary variable, indicating whether week
w contains the treatment phase of patient
p

\(f_{d}\)

Finish time of last activity on the beam resource on day
d

\({\widetilde{\gamma }}_{pd}\)

Stable time violation on day
d for patient
p

\({\hat{\gamma }}_{pi}\)

Time window violation for patient
p’s activity
i

The objective function minimizes the operation time and thereby the idle time of the beam while simultaneously minimizing penalties arising from time window violations of activity
i of patient
p and stable time violations for patient
p and day
d. Here,
\(f_d\) denotes the operation time of the beam resource on day
d,
\({\widetilde{\gamma }}_{pd}\) describes penalty caused by violations of the stable starting time [see Eq. (
19)] and
\({\hat{\gamma }}_{pi}\) accounts for general time window violations [see Eq. (
11)]. All three parts of the objective function are measured in time unites (min), i.e., 1 min of extra beam duration accounts for 1 min of delay for the patient (either time window or stable time violation). As will be shown in Table
10 in Sect.
6, the latter two parts of the objective function tend to almost disappear during the optimization process.
The model’s constraints can be categorized into various subsections: resource constraints, sequencing and optional activities, linking constraints, recurring activities, stable activity starting times, and general treatment start time constraints.
$$\begin{aligned} \mathrm {minimize} \sum _{d\in {\mathcal {D}}} f_{d} + \sum _{d\in {\mathcal {D}}} \sum _{p\in {\mathcal {P}}} {\widetilde{\gamma }}_{pd} + \sum _{p\in {\mathcal {P}}}\sum _{i\in {\mathcal {O}}_p} {\hat{\gamma }}_{pi}. \end{aligned}$$
(1)
4.1 Resource constraints
Each activity
i requires
\(K_{pi}\) resources simultaneously for every patient
p. For some resource requirements, there also exist multiple alternative resources
r, defined by the set of eligible resources for resource requirement
k, namely
\({\mathcal {R}}_{pik}\):
Constraint (
2) assures that for each required resource, one of the eligible resources is chosen if the activity takes place (i.e., variable
\(o_{pi}=1\)). Then,
Constraint (
3) fixes the starting times of nonchosen resources to 0. Constraint (
4) assigns the exact same starting times
\({\bar{s}}_{pi}\) to all resources chosen for activity
i of patient
p, as the sum over all starting times on all eligible resources has only one positive entry per resource requirement
k due to the previous constraint. In turn,
Constraints (
5) and (
6) thus give the immediate successor structure of activities on resource
r. Finally,
Constraints (
7) and (
8) confirm that both the sequencedependent setup times and the nonsequencedependent setup and teardown times are respected.
$$\begin{aligned} \sum _{r\in {\mathcal {R}}_{pik}} h_{pikr} = o_{pi} \quad \forall p \in {\mathcal {P}}, i \in {\mathcal {O}}_p, k \in {\mathcal {K}}_{pi}. \end{aligned}$$
(2)
$$\begin{aligned}&s_{pir} \le h_{pikr}\cdot M \quad \forall p \in {\mathcal {P}},i \in {\mathcal {O}}_p, k \in {\mathcal {K}}_{pi}, r \in {\mathcal {R}}_{pik} , \end{aligned}$$
(3)
$$\begin{aligned}&\sum _{r\in {\mathcal {R}}_{pik}} s_{pir} = {\bar{s}}_{pi} \quad \forall p \in {\mathcal {P}},i \in {\mathcal {O}}_p, k \in {\mathcal {K}}_{pi} . \end{aligned}$$
(4)
$$\begin{aligned}&\sum _{\begin{array}{c} i' \in {\mathcal {O}}_p\\ i'>i \end{array}} y_{pipi'r} + \sum _{q \in {\mathcal {P}} {\setminus } \{p\}}\sum _{j \in {\mathcal {O}}_q} y_{piqjr} = h_{pikr} \nonumber \\&\quad \forall p \in {\mathcal {P}},i \in {\mathcal {O}}_p, k \in {\mathcal {K}}_{pi}, r \in {\mathcal {R}}_{pik}, \end{aligned}$$
(5)
$$\begin{aligned}&\sum _{\begin{array}{c} j' \in {\mathcal {O}}_q\\ j'<j \end{array}} y_{qj'qjr} + \sum _{p \in {\mathcal {P}} {\setminus } \{q\}}\sum _{i \in {\mathcal {O}}_p} y_{piqjr} = h_{qjkr} \nonumber \\&\quad \forall q \in {\mathcal {P}},j \in {\mathcal {O}}_q, k \in {\mathcal {K}}_{qj}, r \in {\mathcal {R}}_{qjk} . \end{aligned}$$
(6)
$$\begin{aligned}&s_{pir} + \lambda _{pi} + u_{piqjr}\cdot y_{piqjr}  (1y_{piqjr}) \cdot M \le s_{qjr} \nonumber \\&\quad \forall p \in {\mathcal {P}},i \in {\mathcal {O}}_p,q \in {\mathcal {P}},j \in {\mathcal {O}}_q, r \in {\mathcal {R}}, \end{aligned}$$
(7)
$$\begin{aligned}&s_{pir} + \lambda _{pi} + w_{pir}\cdot y_{piqjr} + v_{qjr}\cdot y_{piqjr} \nonumber \\&\quad  (1y_{piqjr}) \cdot M \le s_{qjr} \nonumber \\&\quad \forall p \in {\mathcal {P}},i \in {\mathcal {O}}_p,q \in {\mathcal {P}},j \in {\mathcal {O}}_q, r \in {\mathcal {R}} . \end{aligned}$$
(8)
4.2 Sequencing and optional activities
Each activity
i of patient
p is associated with a binary variable
\(o_{pi}\) that indicates whether the activity takes place or not. It is essential for optional activities (PETs and WCEs), and for DTs, this variable must equal 1. The starting time of activities that do not take place is then set to 0, using Constraint (
9):
$$\begin{aligned} {\bar{s}}_{pi} \le o_{pi} \cdot M \quad \forall p \in {\mathcal {P}},\quad i \in {\mathcal {O}}_p . \end{aligned}$$
(9)
×
The problem of scheduling the activities of patient
p considering the precedence relations (finishstart, FS) is further complicated by the optional activities within the activity chain, as shown in Fig.
5. If, for example, a PET does not take place, the DT and WCE need to be tied together using the corresponding FS. However, if the PET is scheduled, the link between the DT and the WCE should be deactivated. In Constraints (
10) and (
11), successive activities that actually take place are connected using the minimum and maximum time lags between them. Constraint (
11) further quantifies the time window violation (belated scheduling) that is penalized within the objective function. Furthermore,
\(\varDelta ^{\mathrm {max}}\) denotes the maximum number of consecutive optional activities, in our case,
\(\varDelta ^{\mathrm {max}} = 2\).
$$\begin{aligned}&{\bar{s}}_{p(i+\delta )} \ge {\bar{s}}_{pi} + \lambda _{pi} + \hbox {FS}_{pi,p(i+\delta )}^{\mathrm{min}}  \sum _{j = i}^{j = i + \delta }(M \cdot (1o_{pj})) \nonumber \\&\quad \forall p \in {\mathcal {P}}, i \in {\mathcal {O}}_p, \delta \in \{1,\ldots ,\varDelta ^{\mathrm {max}}+1\}, \end{aligned}$$
(10)
$$\begin{aligned}&{\bar{s}}_{p(i+\delta )} \le {\bar{s}}_{pi} + \lambda _{pi} + \hbox {FS}_{pi,p(i+\delta )}^{\mathrm{max}}\nonumber \\&\quad + \sum _{j = i}^{j = i + \delta }(M \cdot (1o_{pj})) + {\hat{\gamma }}_{pi}\nonumber \\&\quad \forall p \in {\mathcal {P}}, i \in {\mathcal {O}}_p, \delta \in \{1,\ldots ,\varDelta ^{\mathrm {max}}+1\}. \end{aligned}$$
(11)
4.3 Linking constraints
Constraints (
12) to (
15) serve as linking constraints. If an activity starts within a daytime window, the corresponding assignment variable
\(\theta _{pid}\) equals 1. Constraint (
13) also calculates the general daily starting time by subtracting the day start from the scheduled starting time. The treatment phase (days between FDT and LDT) of patient
p can be calculated for both day
d and week
w using Constraints (
14) and (
15). Note that we display these constraints as nonlinear indicator constraints for better readability. The numeric tests in Sect.
6 use linearized versions of these constraints.
$$\begin{aligned} \theta _{pid}= & {} 1 \iff \underline{dw_d} \le {\bar{s}}_{pi} \le \overline{dw_d} \nonumber \\&\forall p \in {\mathcal {P}}, i \in {\mathcal {O}}_p, d \in {\mathcal {D}}, \end{aligned}$$
(12)
$$\begin{aligned} t_{pd}= & {} \sum _{i \in \varPhi _p} {\bar{s}}_{pi} \cdot \theta _{pid}  \underline{dw_d} \iff \sum _{i \in \varPhi _p}\theta _{pid} = 1 \nonumber \\&\forall p \in {\mathcal {P}}, d \in {\mathcal {D}}, \end{aligned}$$
(13)
$$\begin{aligned} {\bar{x}}_{pd}= & {} 1 \iff \sum _{0\le d'\le d} \sum _{i \in {\mathcal {O}}_p} \theta _{pid'} \ge 1 \nonumber \\&\wedge \sum _{d\le d'\le D} \sum _{i \in {\mathcal {O}}_p} \theta _{pid'} \ge 1 \quad \forall p \in {\mathcal {P}}, d \in {\mathcal {D}}, \end{aligned}$$
(14)
$$\begin{aligned} {\bar{z}}_{pw}= & {} 1 \iff \sum _{d=5\cdot w 4}^{5 \cdot w} {\bar{x}}_{pd} \ge 1 \nonumber \\&\forall p \in {\mathcal {P}}, w \in {\mathcal {W}}. \end{aligned}$$
(15)
4.4 Recurring activities
Constraint (
16) ensures that at least four daily treatments are scheduled on five consecutive days within the treatment phase. Constraints (
17) and (
18) guarantee that at least one WCE (PET) is performed within five consecutive days during the treatment phase, respectively.
$$\begin{aligned}&\sum _{d=s}^{s+4}\sum _{i \in \varPhi _p}\theta _{pid}+M\cdot (1{\bar{x}}_{pd}) \ge 4 \nonumber \\&\quad \forall p \in {\mathcal {P}}, 1 \le s\le D4 , \end{aligned}$$
(16)
$$\begin{aligned}&\sum _{d=s}^{s+4}\sum _{i \in \varPsi _p}\theta _{pid}+M\cdot (1{\bar{x}}_{pd}) \ge 1 \nonumber \\&\quad \forall p \in {\mathcal {P}}, 1 \le s\le D4 , \end{aligned}$$
(17)
$$\begin{aligned}&\sum _{d=s}^{s+4}\sum _{i \in \Xi _p}\theta _{pid}+M\cdot (1{\bar{x}}_{pd}) \ge 1 \nonumber \\&\quad \forall p \in {\mathcal {P}}, 1 \le s\le D4 . \end{aligned}$$
(18)
4.5 Stable activity starting times
Inequalities (
19) and (
20) constrain the daily starting time for each patient to the stable starting time of the corresponding week and the stable starting times of two consecutive weeks, respectively:
$$\begin{aligned}&t_{pd}  {\widetilde{t}}_{pw}  M \cdot (1\sum _{i \in \varPhi _p}\theta _{pid}) \le \alpha ' + {\widetilde{\gamma }}_{pd} \nonumber \\&\quad \forall p \in {\mathcal {P}}, w \in {\mathcal {W}}, 5w4 \le d \le 5w , \end{aligned}$$
(19)
$$\begin{aligned}&{\widetilde{t}}_{pw}  {\widetilde{t}}_{p(w+1)}  M \cdot (1{\bar{z}}_{pw}) \nonumber \\&\quad  M \cdot (1{\bar{z}}_{p(w+1)})\le \alpha '' \quad \forall p \in {\mathcal {P}}, w \in {\mathcal {W}}. \end{aligned}$$
(20)
4.6 Treatment starting time
No treatments can be assigned to patient
p prior to his release day
\(r_p\), so
However, there has to be at least one treatment scheduled for patient
p between his release day and due day, so
$$\begin{aligned} \sum _{i \in \varPhi _p} \sum _{d=0}^{r_p1}\theta _{pid} = 0 \quad \forall p \in {\mathcal {P}}. \end{aligned}$$
(21)
$$\begin{aligned} \sum _{i \in \varPhi _p} \sum _{d=r_p}^{d_p}\theta _{pid} \ge 1 \quad \forall p \in {\mathcal {P}} . \end{aligned}$$
(22)
4.7 Active time of beam resource
Finally, we calculate the active time of the beam according to Constraint (
23):
$$\begin{aligned} f_{d} \ge t_{pd} + \sum _{i \in \varPhi _p} \lambda _{pi} \cdot \theta _{pid} \quad \forall d \in {\mathcal {D}}, p \in {\mathcal {P}} . \end{aligned}$$
(23)
5 Solution methods
In this section we present three metaheuristic approaches to the proposed radiotherapy scheduling problem, to tackle the problem efficiently (as we show in Sect.
6, solving the exact MIP formulation, even for small to mediumsized problem instances, is intractable). We compare two metaheuristic paradigms, namely a populationbased GA approach with a trajectorybased local search heuristic and combine the two to a simple hybrid algorithm. Both methods have successfully been applied to related radiotherapy scheduling problems [e.g., GAs have been used in Petrovic et al. (
2009,
2011), while local search has been performed in Petrovic and LeiteRocha (
2008a) and Kapamara and Petrovic (
2009)].
×
Section
5.1 describes how we map the solution attributes to a multiencoded solution representation. Section
5.2 gives some insight into the complexity of the problem and the proposed encoding scheme. In Sect.
5.3, we describe a greedy randomized method for creating initial solutions to the problem, followed by a detailed description of the decoding algorithm that transforms the solution encoding into a schedule with exact starting times in Sect.
5.4. Finally, Sects.
5.5 to
5.7 present the three distinct solution methods: a GA, an iterated local search method (ILS), and a combination of the two approaches (combined GA and ILS, briefly cGAILS).
5.1 Solution representation
A solution to the RPSP is represented by a multiencoded scheme that consists of three main parts. The first part (“DT assignment”) contains, for every patient
\(p \in {\mathcal {P}}\), an assignment of treatments to days. Days prior to the release time of the patient automatically remain unassigned. Between the FDT and the LDT (i.e., treatment phase), at least four treatments must be assigned to five consecutive days for the solution to be feasible. In the second part, two binary vectors for each patient
\(p \in {\mathcal {P}}\) indicate, when (i.e., after which DT) a WCE and a PET is scheduled (“WCE/PET assignment”). An entry at the
ith position in these vectors implies that a WCE (PET) has been added after the
ith DT activity. We must ensure a minimum of one WCE (PET) within each span of five consecutive days, resulting in at least one entry in the binary encoding over four consecutive DTs. Finally, the third part of the solution encoding consists of a vector of patient indices that displays the sequence in which the patients should be scheduled on a specific day (“patient sequence”).
Figure
6 illustrates a solution of an RPSP for 15 patients (
\(P=15\)), where
\(N_p^\mathrm{DT}\) denotes the patientspecific number of required DTs. The bold frame within the DT assignment marks the treatment phase. The grayshaded cells indicate the release and due dates for the FDT. Out of space considerations, we only display the WCE assignments; the PET assignments would reveal different allocations but the same sizes (
\(N_p^\mathrm{DT}\) of the patient
p). Here, patient 1 starts his treatment on day 4. Directly after his first DT, a WCE is scheduled. The patient sequence lists patient 1 in the fifth position, so all predecessors will be scheduled prior to patient 1 on day
d using the solution decoding algorithm (see Sect.
5.4).
5.2 Excursus on problem complexity
The presented solution representation already gives insight into the complexity of the underlying problem. The number of permutations of the DT assignment list for one patient
p depends strongly on the number of DTs to be scheduled for this patient, namely
\(N_p^\mathrm{DT}\) and can be calculated using Equation (
24) (assuming the day of the FDT is fixed for patient
p), with
\(h^{\mathrm{max}}_p\) denoting the maximum number of unassigned days allowed during the treatment phase. Given the above information, we define:
On average, a radiotherapy treatment consists of 20 DTs, which allows a maximum of five unassigned days during the treatment phase (
\(h^{\mathrm{max}}_p=5\)) and a total of 657 feasible DTtoday assignments, given the day of the FDT is fixed. A realworld instance would contain an average of 100 patients, each of which is assigned to an individual permutation list of DT assignments. Additionally, for each patient
p, there exist on average four different “minimally occupied” WCE and PET assignments and a multiplicity of “nonminimally occupied” assignments. Finally, given
P, or the number of patients to receive radiotherapy,
P! permutations of the patient sequence exist. We then calculate the number of possible permutations by multiplying the three parts:
\(P! \times \prod _{p=1}^{P} g(p) \times 4^P \times 4^P\).
$$\begin{aligned} g(p) := \sum _{r = 0}^{h^{\mathrm{max}}_p} {{N_p^\mathrm{DT}  3\cdot r + 2}\atopwithdelims (){r}} . \end{aligned}$$
(24)
Therefore, instances including only five patients (
\(P=5\)) with 20 treatments each (
\(N_p^\mathrm{DT}=20\)) and a fixed treatment start day already would imply
\(P!=5!=120\) permutations of the patient sequence, for each patient 657 feasible DTtoday assignments, i.e.,
\(\prod _{p=1}^{5} 657=1.22 \times 10^{14}\) possible assignments and both
\(4^5=1024\) possible WCE and PET assignments. This results in a total of
\(1.54 \times 10^{22}\) solution permutations.
5.3 Initial solutions
Initial, partly randomized solutions can be created using simple construction rules. We apply different strategies to the parts of the solution representation: For each patient, we first randomly fix the day of his or her FDT, noting the release and due days. Then, the subsequent treatment days are fixed, with the premise that four treatments must be scheduled within five consecutive days. The probability of leaving one specific day
d unscheduled (i.e., four prior days have a DT scheduled) is rather small, ranging between 0 and 30%. The same strategy applies for the WCE and PET assignments, where only one activity must be assigned over four consecutive DTs.
Building the patient sequence requires a more sophisticated method though. We build a “global” patient sequence for all patients, in which we neglect the fact that some patients by definition will not be treated on the same day (because their release time will be later than other patient’s LDT day, resulting in nonoverlapping treatment phases). Using the assumption that all patients must be treated on a fictitious day
\(d^*\), we choose a random patient, whom we add as the first patient in the patient sequence. Then, we continuously add one more patient, who minimizes the total idle time of the beam, due to either room unavailability (i.e., the teardown time of the previous patient is not yet finished when the setup of the current patient should start) or setup time due to particle type switches (from proton to carbon ion or vice versa). This strategy results in a starting solution; only in rare cases are two patients requiring the same treatment room scheduled successively.
5.4 Solution decoding and solution evaluation
To decode this described solution representation into a schedule that provides exact starting times and resource decisions for each activity, we first transform the solution into a chronological (i.e., daywise) prioritized activity list. Then, using Algorithm 1, we determine the exact starting time and the resource set on which the activity should be performed. We begin the search for a feasible starting time on the “preferred” resource set (
\(n=1\)). We use function
FindStartingTime(
\(i,n,{\bar{s}}_{pi},l_{pi}\)) to determine the earliest starting time for activity
i on resource set
n, with
\({\bar{s}}_{pi}\) as the earliest time to start and as
\(l_{pi}\) the latest possible starting time. We first search all
\(N_{pi}\)eligible resource sets for a
feasible starting time (i.e., a smaller than or equal to
\(l_{pi}\)). If no such starting time arises from any resource set, the first nonfeasible (i.e., belated) starting time on the “preferred” resource set is accepted as the starting time for activity
i, though it results in a penalty within the objective function.
Note that function
FindStartingTime(
\(i,n,{\bar{s}}_{pi},l_{pi}\)) in Algorithm 2 does not necessarily add activities to resources chronologically. Activities can be scheduled to fill up “holes” in resources, such as might occur if we were to schedule two treatment activities in the same treatment room successively and therefore face idle time on the beam resource due to teardown and setup times. We then would aim to schedule activities requiring any other treatment room in between those activities to minimize the idle time on the beam resource. This approach has been proven beneficial in our problem setting (see Vogl et al.
2018).
×
×
The sequential nature of the decoding algorithm requires a postscheduling evaluation of the treatment starting times to evaluate the stable time violations, because the stable time for each patient
p and each week
w needs to be assigned “globally” and not when scheduling the first activity of the week. Therefore, we solve a small linear program for each patient
p to reveal stable time violations. The model contains only two variable types, namely,
\({\widetilde{t}}_{w}\), the stable time of week
w, and
\(\gamma _d\), the stable time violations on day
d. The daily starting time
\(t_d\), the day assignment variable
\(\theta _d\), and the weeks within the treatment phase
\(\mathcal {W'}\) have already been fixed during the solution decoding phase and are therefore input parameters. Accordingly,
subject to:
The objective function is to minimize the sum of daily deviations from the stable starting times. These deviations are calculated using Constraint (
26). Constraint (
27) then assures that the interweek stable time variation is smaller than the maximum allowed deviation, namely
\(\alpha ''\).
$$\begin{aligned} \mathrm {minimize} \sum _{d \in {\mathcal {D}}}^{}\gamma _{d} \end{aligned}$$
(25)
$$\begin{aligned}&t_{d}  {\widetilde{t}}_{w}  \gamma _{d}  M \cdot (1\theta _{d}) \le \alpha ' \nonumber \\&\quad \forall w \in \mathcal {W'}, 5w4 \le d \le 5w, \end{aligned}$$
(26)
$$\begin{aligned}&{\widetilde{t}}_{w}  {\widetilde{t}}_{w+1} \le \alpha '' \quad \forall w \in \mathcal {W'}. \end{aligned}$$
(27)
5.5 Genetic algorithm
Genetic algorithms have been implemented successfully to solve the radiotherapy patient scheduling problem (Petrovic et al.
2009,
2011). In a preliminary study, we introduced the solution decoding presented in Sect.
5.4 and presented initial tests of different decoding algorithms and GA settings, applied within this research setting (Vogl et al.
2018). We enhance this strategy here by introducing a more sophisticated crossover mechanism, in addition to the patientwise crossover presented in the previous work. Algorithm 3 gives an overview of the mentioned GA components. Note that the algorithm contains two sets of solutions:
\({\mathcal {P}}_t\) forms the current population during iteration
t and
\(C^B\) contains children that did not reach the success criterion of being better than at least their worst parent (see line 12 in the algorithm) and therefore do not immediately contribute to the next generation. The latter solutions are potentially used if by producing five times the population’s size as offspring is not sufficient to build the new population from successful children.
Crossover(
\(p_1\),
\(p_2\)) The multiencoded solution representation demands specific crossover and mutation operators for the individuals to remain feasible throughout the evolutionary process. We use two crossover operators: (1) The patientwise crossover operator presented by Vogl et al. (
2018), where the whole DT assignment as well as the whole PET and WCE lists of one patient
p is randomly inherited either by the first or the second parent. This simple crossover only leads to limited variety in the binary encodings, because the combinations of the initial population dominate the search. So we developed a (2) a tailormade, daywise crossover operator for the DT assignment part of the multiencoded chromosome, illustrated in Fig.
7. The daywise crossover chronologically compares entries of the parents on a specific day
d. If both parents have a DT assigned on day
d, we naturally assign a treatment on this day (white entries). The same applies for the cases in which no treatment is planned on day
d, observable by two “0” entries in the parent chromosomes. Grayshaded cells indicate days with different allocations among the parents. The assignment of every yet undecided day
d is fixed randomly, again defining the allocations chronologically. We first have to determine if leaving day
d unassigned leads to an infeasible solution regarding the constraint of assigning four treatments within every five consecutive days. If so, we assign a treatment to this day in any case.
The probability of assigning a treatment to day
d depends on the number of still missing DTs for patient
p,
\(n_{\mathrm{missing}}\), and the number of undecided days,
\(n_{\mathrm{undecided}}\):
\(P(\mathrm {DT}_d)=\frac{n_{\mathrm{missing}}}{n_{\mathrm{undecided}}}\). We call this crossover strategy the “daywise crossover operator.”
The daywise crossover and patientwise crossover then are chosen randomly during the genetic evolution of the DT assignments with equal probabilities. The WCE and PET assignments use only the patientwise crossover operator. Finally, we apply the positionbased crossover operator (PBX) to the patient sequences of two parent solutions to receive the child’s patient sequence (Syswerda
1996).
Mutate(
c) To enhance the search, we apply mutation operators to 10% of the descendants in each generation. The DT assignment per patient is mutated by inverting the list within the treatment phase. The WCE and PET assignments are completely reversed, and the patient sequence is mutated using the wellknown shift mutation operator, such that one random patient
p is removed from the current sequence and reinserted at a random position within the sequence.
×
To choose individuals for reproduction [
Perform Selection(
\({\mathcal {P}}_{i}\))], we employ the rank selection operator. Because offspring selection (Affenzeller and Wagner
2004) is beneficial in our problem setting (Vogl et al.
2018), we again incorporate this strategy into our GA. We aim to build 70% of the offspring population from children that outperform their worse parent (see line 7 and lines 12–17 in Algorithm 3). The number of reproductive steps is limited to five times the population size in each iteration (see line 7). The rest of the population is then filled up with random individuals that did not outperform their worse parent (lines 19–23). In addition, 1% of the offspring population is composed of the best individuals of the parent population [
GetElites(
\({\mathcal {P}}_{i}\))].
×
5.6 Iterated local search
As an alternative approach to the GA, we introduce an ILS to solve the RPSP, where the local search step of the algorithm is formed by a variable neighborhood descent (VND). Algorithm 4 gives an overview of the classic ILS (Lourenço et al.
2010) components, all of which are described in more detail in the following paragraphs.
×
GenerateInitialSolution The initial solution of the ILS is defined by the best solution found within a pool of randomly generated solutions, which are constructed using a partly greedy, partly random approach described in Sect.
5.3. The pool size depends o the instance size with larger, realworld inspired instances in Sect.
6 having a pool of 200 initial solutions to choose from.
LocalSearch The local search part of the algorithm is formed by a VND, which operates on different parts of the solution representation in Sect.
5.1. Traditionally, the VND contains various different neighborhoods with increasing degree of disruptiveness, which allows the algorithm to leave potential local minima. Preliminary tests have shown that in our specific case, the following
\(k_{d}=6\) neighborhoods contribute to the search for improvements to the solution fitness. For details on these preliminary tests please refer to Sect.
6.2.
If a better solution is found, the VND continues its search within the first neighborhood. In case no better solution can be found in any of the listed neighborhoods, we reach a local minimum, leading to the termination of the VND. Because the high complexity of the underlying problem leads to vast neighborhood sizes, we impose a limit on the number of evaluated neighbors in each iteration of the VND (see Sect.
6 for details). Experiments have shown that the best improvement policy during the neighborhood search of the VND is beneficial, which is why we follow this scheme.
1.
Perform a random shift of a patient within the patient sequence (N1).
2.
Invert the DT assignment of a random patient (N2).
3.
Invert both the WCE and PET assignments of a random patient (N3).
4.
Swap two random patients within the patient sequence (N4).
5.
Rebuild the DT, WCE, and PET vectors for a random patient from scratch (random assignment, as in the starting solutions, (N5).
6.
Invert a random subsequence of a size between 2 and 5 of the patient sequence (N6).
Perturbation If the local search gets stuck in a local minimum, a perturbation of the current solution is performed, to leave the local minimum and restart the local search phase from another starting point. We use two different perturbation strategies, one less and one more invasive method. Any time a local minimum is found that improves the global best, we use the less invasive perturbation method. Otherwise, we alternate these approaches.
The less invasive method inverts the DT, WCE, and PET assignments of a random patient, and it also inverts a random part of the patient sequence of size
P / 7. The second perturbation strategy rebuilds a completely new assignment of DTs, WCEs, and PETs for a random patient (as in neighborhood 5 of the VND) and inverts a random part of the patient sequence of size
P / 5.
AcceptanceCriterion The acceptance criterion determines whether solution
\(s^{*\prime }\), found by the latest local search step, replaces the current incumbent solution
\(s^*\). Lourenço et al. (
2010) describe two extremes of acceptance criteria during ILS. Either the new solution is accepted only if it improves
\(s^*\) (i.e., “better” acceptance criterion), or it is accepted in any case (i.e., “random walk”). Between these extremes, many intermediate acceptance criteria can be found in prior literature, such as thresholdbased or probabilistic ones (simulated annealing). Preliminary results have shown that in our case, the “better” criterion outperforms all other mentioned approaches.
5.7 Combined GA and ILS
Combinations of genetic algorithms and local searchbased algorithms, socalled memetic algorithms or genetic local search metaheuristics, have proven to be beneficial in the literature (see, e.g., Neri et al. (
2012), who summarized work on memetic algorithms or Vela et al. (
2010), who successfully interleaved a GA with a local search and called this hybrid form “genetic local search”). Because the power of ILS in our case highly depends on the quality of the initial solution, we investigated further into hybrids of the two presented approaches. However, classic memetic approaches that perform a local search on children in the GA were not competitive. Therefore, we present a simple but effective (see Sect.
6) combination of the two described standalone metaheuristics in a way that we first run the GA and afterward, taking the best solution of the GA, we perform the proposed ILS approach. The available CPU time is distributed equally among the approaches.
6 Results
We implemented and tested the solution approaches with a set of randomly generated problem instances of varying sizes. After a brief description of the instances and environment used for our computational study (Sect.
6.1), we give insight into preliminary tests conducted in order to measure the impact of the neighborhoods listed in Sect.
5.6. Then, we proceed with the analysis of small, toy instances to assess the performance of the metaheuristic solution approaches in comparison with the exact MIP formulation in Sect.
6.3. Finally, we discuss the computational results for large and mediumsized problem instances in Sect.
6.4 and compare the algorithms on various key figures associated with the solutions.
6.1 Experimental setup
The instances were generated using the knowledge of MedAustron staff about the underlying distribution functions. Patientspecific random variables came from the distributions summarized in Table
4. Small toy examples with 3–25 patients are created to assess the quality of the heuristic methods in comparison with exact solution methods; the larger, more realistic instances include 35–175 patients.
Additional instance settings are as follows:
$$\begin{aligned} u_{piqjr}= & {} {\left\{ \begin{array}{ll} 3, \begin{aligned} &{}\quad \text {if } p \text { and } q \text { have different beam} \\ &{}\quad \text {types and } r \text { is the beam resource}, \\ \end{aligned}\\ 0,\quad \text {otherwise}. \end{array}\right. }\\ \lambda _{pi}= & {} {\left\{ \begin{array}{ll} 30, &{} \quad \text {if } i \in \Xi _p, \\ 10, &{} \quad \text {if } i \in \varPsi _p. \end{array}\right. }\\ \alpha '= & {} 30 \text { min}\\ \alpha ''= & {} 120 \text { min}\\ \hbox {FS}^{\mathrm{min}}_{pi,p(i+\delta )}= & {} {\left\{ \begin{array}{ll} 0, &{} \quad \text {if } i \in \varPhi _p \wedge (i+\delta ) \in \Xi _p, \\ 15, &{} \quad \text {if } i \in \varPhi _p \wedge (i+\delta ) \in \varPsi _p,\\ 15, &{} \quad \text {if } i \in \Xi _p \wedge (i+\delta ) \in \varPsi _p. \end{array}\right. }\\ \hbox {FS}^{\mathrm{max}}_{pi,p(i+\delta )}= & {} {\left\{ \begin{array}{ll} 15, &{} \quad \text {if } i \in \varPhi _p \wedge (i+\delta ) \in \Xi _p, \\ 60, &{} \quad \text {if } i \in \varPhi _p \wedge (i+\delta ) \in \varPsi _p,\\ 60, &{} \quad \text {if } i \in \Xi _p \wedge (i+\delta ) \in \varPsi _p. \end{array}\right. } \end{aligned}$$
Table 4
Probability distributions of instance specifics
Attribute

Probabilities


Beam type

\(P(\mathrm{BeamType}_p = P) = 0.5\)

\(P(\mathrm{BeamType}_p = C) = 0.5\)


Duration irradiation
\(\lambda _{pi} \quad \forall i\in \varPhi _p\)

\(\sim {\mathcal {N}}(12,5) \iff \hbox {BeamType}_p = P\)

\(\sim {\mathcal {N}}(8,5) \iff \hbox {BeamType}_p = C\)


Room

\(P(\hbox {Room} = 1) = 0.33\)

\(P(\hbox {Room} = 2) = 0.33\)


\(P(\hbox {Room} = 3) = 0.33\)


Duration inroom setup

\(P(v_{pir} = 12) = 0.8\)

\(P(v_{pir} = 22) = 0.2\)


Duration inroom teardown

\(P(w_{pir} = 3) = 0.7\)

\(P(w_{pir} = 6) = 0.3\)


aRO

\(P(\hbox {aRO} = 1) = P(\hbox {aRO} = 2) = \)

\(P(\hbox {aRO} = 3) = P(\hbox {aRO} = 4) = 0.25\)


PET

\(P(\hbox {PET} = \hbox {true}) = 0.5\)

For instances with
\(P \ge 35\), we acknowledge that several patients probably have already started their treatment, prior to the beginning of the planning horizon. According to our project partner, patients require an average of 20 treatments, resulting in the following scheme: For any day in the planning horizon, approximately 1/4 of patients will be having their first week of treatments; another quarter is within the second treatment week. Finally, 1/4 of patients has already had two treatment weeks and is currently in the third week of treatments and the last quarter of patients is finishing treatment after the current week. We follow this systematic approach when generating our realworld inspired problem instance. We therefore create seven types of patients, as in Table
5. The first three categories have already started their treatment prior to the beginning of the planning horizon and have between 4 and 15 treatments left. Therefore, the release date for these patients is 0. For 20% of these patients, we assume that they could have a day off on day 0, resulting in a due date of 1 instead of 0. In categories 4–7, patients start their treatment in weeks 0–3, respectively. Because we plan a total of 4 weeks, we assign only a limited number of DTs to these patients. The release and due dates of these patients equal Monday to Tuesday of the given starting week
\(w_{\mathrm{FDT}}\).
Instances with
\(P \in \{9, 15, 25\}\) follow a similar pattern but use only 3, 5, and 5 categories and planning horizons of 10, 15, and 15 days, respectively. Patients in instances with
\(P \in \{3,4,5\}\) all have equal release dates (day 0) and due dates (day 1) and every patient needs the same number of DTs. The total number of DTs for these instances is given in Table
7.
Table 5
DT Specifics of Larger Instances
Cat.

\(w_{\mathrm{FDT}}\)

\(N_p^\mathrm{DT}\)

\(r_p\)

\(d_p\)


1

–

\(\sim {\mathcal {U}}(4,5)\)

0

\(P(d_p = 0) = 0.8\)

\(P(d_p = 1) = 0.2\)


2

–

\(\sim {\mathcal {U}}(8,10)\)

0


3

–

\(\sim {\mathcal {U}}(12,15)\)

0


4

0

\(\sim {\mathcal {U}}(16,20)\)

0

1

5

1

\(\sim {\mathcal {U}}(12,15)\)

5

6

6

2

\(\sim {\mathcal {U}}(8,10)\)

10

11

7

3

\(\sim {\mathcal {U}}(4,5)\)

15

16

The calculation of tight lower bounds is hardly possible for the RPSP, so we manipulated the activity durations of the DTs of randomly generated instances so that there exists an (optimal) solution to the problem for which no unavoidable idle time of the beam resource is necessary. These optimal solutions also do not contain time window violations. The objective value then consists of the total durations of the DTs, that is, the minimum time the beam is used in total. For nonmanipulated instances (see Table
9), we use the same measure as a lower bound to the problem.
All algorithms have been implemented in C++. The MIP was solved using Gurobi 7.0.2. The experiments have been carried out on the Vienna Scientific Cluster (VSC3), whose compute nodes are equipped with two Intel Xeon E52650v2, 2.6 Ghz, 8 core CPUs each.
×
6.2 Experimental evaluation of VND neighborhoods
We conducted preliminary experiments in order to assess the impact of all six neighborhoods used within the VND part of the ILS. Therefore, we formed multiple subsets of the
\(k_{d}=6\) neighborhoods and performed randomized computational tests on 10 problem instances including 35–175 patients. Five instances are randomly generated, while the remaining five are again “manipulated” instances with known lower bound. Seven subsets have been chosen such that each subset still operates on all three parts of the solution representation. These subsets are:
1.
All
\(k_{d}=6\) neighborhoods N1, N2, N3, N4, N5, and N6
2.
Neighborhoods N1, N2, and N3
3.
Neighborhoods N1, and N5
4.
Neighborhoods N4, and N5
5.
Neighborhoods N5, and N6
6.
Neighborhoods N2, N3, N4
7.
Neighborhoods N2, N3, N6
Table 6
Success rates of each neighborhood during the optimization of five instances and two algorithmic settings (small, large neighborhood) each
P

SN/LN

N1 (%)

N2 (%)

N3 (%)

N4 (%)

N5 (%)

N6 (%)


35

SN

44

31

18

17

49

32

35

LN

44

31

18

17

50

32

70

SN

50

32

21

19

57

45

70

LN

52

32

21

20

59

43

105

SN

50

40

28

18

69

57

105

LN

53

40

29

19

73

57

140

SN

52

40

35

19

77

64

140

LN

56

38

36

21

81

65

175

SN

53

36

45

20

84

73

175

LN

58

34

48

23

86

74

Table 7
Results of small instances
MIP

Heuristics



P

\(N^{\mathrm{DT}}\)

Opt.

Full

Timeto (s)

Vars

Cons

Reduced

Timeto (s)

Vars

Cons

GA

ILS

Time

Small instances


3

12

184

184*

4/33

580

850

184*

2/13

358

508

184

184

60

4

16

240

240*

82/5797

923

1276

240*

1/122

623

812

240

240

60

5

20

248

248
\(\hat{}\)

7609

1226

1647

248
\(\hat{}\)

4369

876

1078

248

248

60

3

27

414

414
\(\hat{}\)

3326

2596

3818

414
\(\hat{}\)

1184

1359

1411

414

414

60

5

30

372

372
\(\hat{}\)

22,432

3026

4416

376

1518

1745

1704

372

372

60

4

36

540

540
\(\hat{}\)

79,853

4609

6862

540
\(\hat{}\)

54,769

4148

6507

540

540

60

5

45

558

591

3173

6743

9736

563

26,121

5567

7836

558

558

60

9

60

720

759

84,633

13,250

20,364

–

86,400

11,201

17,336

720

720

1800

15

135

1410

–

86,400

57,409

72,971

–

86,400

46,785

59,587

1414

1410

3600

25

225

2295

–

86,400

156,304

184,960

–

86,400

120,699

140,088

2353

2296

5400

On all 10 instances and two neighborhood sizes (small, “SN” and large, “LN”), 16 replications of the ILS were run, equaling
\(20 \times 16\) runs for each of the neighborhood subsets mentioned above. Then, concerning the average results obtained by the 16 replications, the rank of the neighborhood subset was calculated for each of the 10 problem instances and the two neighborhood sizes. The best neighborhood subset obtained rank 1, while the worst one obtained rank 7 (see e.g., Hemmelmayr et al.
2012 for a similar comparison of neighborhood subsets). Figure
8 depicts the results of the ranking for all neighborhood subsets in form of box plots. The results show that for some of the tested instances, a subset of the six neighborhoods, more specifically the subset containing N1 and N5, performs best and is therefore ranked number 1. However, averaged over all instances (see the bold line in the boxes representing the median rank), the proposed version of the algorithm containing the full set of neighborhoods, is clearly better than all the remaining subsets.
Additionally, we analyzed the success rate of each neighborhood during the optimization by dividing the number of times the neighborhood lead to a better solution through the number of times the neighborhood was called during the optimization, i.e.,
\( n_{\mathrm{success}}/n_{\mathrm{called}}\). The corresponding results are summarized in Table
6. All six neighborhoods have considerable success rates, indicating once more that all six neighborhoods contribute to the search of the best solution. Furthermore, the success rate of each neighborhood apparently increases with the instance size. Hence, larger instances seem to profit even more from the whole range of neighborhoods, which is why we have chosen to include all six neighborhoods in the more extensive experimental tests of small and large instances.
Table 8
Results of large, manipulated instances (one instance per
P with 16 replications each)
P

Av.
\(N^\mathrm{DT}\)

Opt.

Time limit

Initial

GA

ILS

cGAILS



Average

Gap (%)

Average

Gap (%)

Av. SN

Av. LN

Gap (%)

Average

Gap (%)


Large instances


35

400

3920.0

7200

5143.0

31.2

4153.9

6.0

4065.
3

4068.2

3.7

4097.8

4.5

70

800

7580.0

14,400

10,515.8

38.7

8143.
6

7.4

8209.3

8196.4

8.1

8163.3

7.7

105

1200

11,240.0

21,600

14,463.8

28.7

12,279.2

9.2

12,507.1

12,457.9

10.8

12,252.
0

9.0

140

1600

14,900.0

28,800

20,309.6

36.3

16,426.
7

10.2

16,792.3

16,630.8

11.6

16,490.1

10.7

175

2000

18,560.0

36,000

27,057.9

45.8

20,631.
7

11.2

21,104.4

20,956.6

12.9

20,686.4

11.5

Table 9
Results of large, realworldinspired instances (16 instances per
P with 16 replications each)
P

Av.
\(N^\mathrm{DT}\)

LB

Time limit

Initial

GA

ILS

cGAILS



Average

Gap

Average

Gap (%)

Av. SN

Av. LN

Gap (%)

Average

Gap (%)


Large instances


35

400

3717.6

7200

5145.7

38.4

4544.2

22.2

4476.2

4473.3

20.3

4459.
6

20.0

70

800

7107.4

14,400

10,522.0

48.0

8638.9

21.5

8577.7

8572.0

20.6

8520.
6

19.9

105

1200

10,603.0

21,600

14,442.9

36.1

13,070.1

23.3

12,995.2

12,997.9

22.6

12,820.
4

20.9

140

1600

13,976.7

28,800

20,315.3

45.4

17,212.8

23.2

17,267.1

17,369.9

23.5

16,930.
7

21.1

175

2000

17,734.8

36,000

27,016.5

52.3

22,205.6

25.2

22,288.7

22,422.1

25.7

21,946.
5

23.7

6.3 Small instances
The initial tests entail small instances with known optimal solution (see Table
7, column “opt.”). We compare results from two versions of the linearized variant of the MIP model presented in Sect.
4: The full model contains all variables and constraints described in Sect.
4, whereas in the reduced model, optional activities are assigned prior to the optimization, thereby radically decreasing the number of variables and constraints in the model (see Table
7, columns “vars” and “cons,” respectively). The “timeto” column indicates the running time needed to achieve the best found solution (and to prove the optimality of this solution), with a maximum running time for both MIP versions of 24 h. Furthermore, the two basic versions of the GA and ILS (large neighborhood) are listed. The results show that the optimal solution was found almost for all problem instances in a reasonable time span by the GA and the ILS, with a small advantage for the latter method. The smaller instances with
\(N^\mathrm{DT} = \sum _p N_p^\mathrm{DT} \le 36\) also could be solved to optimality by Gurobi (marked by
\(\hat{}\)). However, Gurobi was only capable of proving optimality for the two smallest instances (marked with *). Furthermore, the running time to find (the optimal) solutions is already vast for the small instances; those with 45 or more DTs likely could not be solved to optimality by Gurobi. For instances with 15 and 25 patients, not even a single feasible solution was found after 24 h of running time. We therefore conclude that solving the RPSP to optimality using mathematical programming techniques is beyond the scope for larger problem instances.
6.4 Medium and large instances
Tables
8 and
9 summarize the results of computational tests performed using larger problem instances that include 35–175 patients. The combination of the day assignment and the inroom setup and teardown times complicate the calculation of a strict lower bound, because it makes assessing
unavoidable idle time on the beam resource virtually impossible. Therefore, we adopt two strategies to evaluate the quality of the solutions. Table
8 lists five instances in which we manually manipulated the proportion of time used for setup, teardown, and treatment so that there exists an optimal solution without idle time on the beam. The calculated gaps for these manipulated instances can be interpreted as optimality gaps. Then, Table
9 contains averages over 16 randomly generated instances. Here, we compare the solution to a naive lower bound consisting of the total time the beam is required within the planning horizon, equal to the sum of all irradiation durations of all patients.
The “Initial” column lists the objective value of the best solution among the initial GA population, which also serves as a starting solution to the ILS. The “average” column reveals the average of best found solution fitnesses after the time limit has been reached for all proposed methods. Note that we limited the number of evaluated neighbors within the local search of the ILS. We investigated two neighborhood sizes: The first, “small” approach evaluates
\(\sqrt{N}\) neighbors per iteration, with
N as the total number of potential activities to be scheduled, which we abbreviate to “SN.” The second approach allows us to examine
P neighbors of the current solution (denoted “LN”).
The results show a slight advantage of the GA and cGAILS for the manipulated instances in Table
8. The corresponding gaps from the optimal values increase slightly with the instance size and the underlying problem complexity for these manipulated instances.
×
The randomly generated instances in Table
9 clearly show the benefits of combining GA and ILS, which for all problem sizes delivers the best solutions. For the realworld, nonmanipulated instances, the gap from the lower bound remains more or less stable, even with increasing problem size. The dominance of the hybrid method over the standalone methods, for all
\(5\times 16=80\) realworldinspired instances, can be verified statistically using both
t tests and Wilcoxon Rank tests. Specifically, these tests yield significantly better results for almost all instances: cGAILS produces significantly superior results to GA in 78 of the 80 instances. Furthermore, the combined method performs significantly better than ILS with small neighborhood in 61 and better than ILS with large neighborhood in 62 cases (tables of the results of all statistical tests can be found in “Appendix”).
Figure
9 compares the empirical cumulative distribution functions (ECDF) of the four methods: GA, ILS with small neighborhood, ILS with large neighborhood, and cGAILS for one specific instance including 175 patients. For these functions, all 16 replications per solution method were sorted according to their objective value. The graph displays the percentage of solutions (
yaxis) among these 16 replications per method that lie below a given objective value (
xaxis), i.e., the midpoint of the
yaxis gives the median performance of the algorithms, whereas the upper line gives the worst case and the lower line the best case performances. According to this analysis, cGAILS performs better for all percentiles of the ECDF. Although GA and ILSsmall depict comparable median performance, both the best and the worst solutions of the GA are weaker than the best/worst of the ILS with small neighborhood. Furthermore, ILS with large neighborhood does not yield comparable results for this specific instance, which is also evident for instances with 140–175 patients in Table
9.
Table 10
Key figures of 175patient instances
Method

Av. Fit.

Av. Pen.

Av. holes

Av. pS

Av. sr2

Av. sr1b


GA

22,205.6

28.1

44.9

134.4

33.4

509.2

ILSsmall

22,288.7

37.4

48.3

305.5

27.8

564.9

cGAILS

21,946.5

26.0

54.3

179.7

25.6

535.2

Table
10 gives an overview of some attributes of the achieved solutions by the three metaheuristic approaches for the 175 patients instances (last row in Table
9). The “av. Fit.” column denotes the average fitness of the solutions, with “av. Pen.” indicating the penalty term of the fitnesses. The “av. holes” column lists the total number of unassigned days over all patients, and “av. pS” sums the particle switches that cause sequencedependent setup on the beam resource. Furthermore, “av. sr2” indicates how often the same room is required for a DT consecutively, leading to immediate idle time on the beam during the inroom setup and teardown times. Finally, “av. sr1b” counts cases in which it was not possible to iterate through all rooms, so only a switch between two rooms occurred (e.g., room 1, room 2, and again room 1, with only one patient treated in a different room between the two times in the same room). We aim to minimize key figures av. pS to av. sr1b to achieve solutions with less idle time. A low number of unassigned days (“holes” within a patient’s treatment plan) do not necessarily lead to better solutions; instead, we anticipate some “optimal” number of unassigned days for each instance.
Comparing the three methods according to the key figures gives an initial impression of the advantages and drawbacks of each method. The average GA solution includes only small time window penalties and particle switches, but the same room is more often used consecutively, leading to higher idle time on the beam. In contrast, ILS results in a higher number of particle switches, simultaneously reducing av. sr2 to only 27.8. Then, cGAILS can further shorten this number to 25.6, at the same time accepting somewhat more particle switches than the GA solutions. However, particle switches cause beam idle time of 3 min, whereas using the same room twice consecutively, on average, leads to an idle time of 17.9 min. Therefore, if idle time is unavoidable, we would rather switch beam types than use the same room twice in a row. Finally, the average number of holes within the best found solution is significantly higher than in GA and ILS. Accordingly, we conclude that the optimal number of unassigned days over all patients lies between 50 and 60 for the 175patient instances.
Table 11
Results of
t tests of 80 instances, batched by number of patients
P per instance
cGAILS versus GA

cGAILS versus ILSSN

cGAILS versus ILSLN



P

***

**

*

ns

***

**

*

ns

***

**

*

ns

t test (twosided)


35

16

16

16

0

2

5

6

10

1

2

5

11

70

16

16

16

0

4

9

13

3

4

10

12

4

105

16

16

16

0

12

14

15

1

12

12

14

2

140

15

16

16

0

15

16

16

0

16

16

16

0

175

4

11

14

2

9

11

11

5

12

14

15

1

\(\sum _P\)

67

75

78

2

42

55

61

19

45

54

62

18

Table 12
Results of Wilcoxon rank tests of 80 instances, batched by number of patients
P per instance
cGAILS versus GA

cGAILS versus ILSSN

cGAILS versus ILSLN



P

***

**

*

ns

***

**

*

ns

***

**

*

ns

Wilcoxon Rank test


35

16

16

16

0

2

4

6

10

0

2

4

12

70

15

16

16

0

3

8

12

4

4

8

12

4

105

16

16

16

0

9

13

16

0

12

12

15

1

140

13

16

16

0

14

16

16

0

16

16

16

0

175

4

8

15

1

9

10

11

5

12

14

15

1

\(\sum _P\)

64

72

79

1

37

51

61

19

44

52

62

18

7 Conclusion
Scheduling recurring radiotherapy treatment appointments in ion beam facilities in which multiple rooms share one particle beam represents a complex job shop scheduling problem with custom constraints. We have introduced the specific problem setting and formulated the problem mathematically. However, in realizing that solving the MIP for realworld instances is intractable, we developed a GA and an ILS approach, both of which build on a multiencoded solution representation and a chronological decoding algorithm. The GA contains tailormade, feasibilitypreserving, crossover operators, and an offspring selection strategy. The local search within the ILS is composed of a VND that operates on six different neighborhoods of the incumbent solution. We have shown that the two standalone metaheuristic approaches lead to excellent solutions for small problem instances, even highly dominating the MIP approach with regard to running times and solution quality. For larger instances, the combination of the populationbased GA and the individualbased ILS leads to significantly better results than each of the approaches achieves individually, yielding solutions that perform soundly on all measured key figures.
Future research on radiotherapy scheduling will be dedicated to stochastic optimization techniques; many parameters of the underlying problem are subject to intense uncertainty. For example, some patients might not be capable of getting the planned irradiation treatment if their condition becomes very severe. Sometimes the treatment start needs to be postponed for patients to recover from shortterm illnesses. Such requirements might be assessed by either robust scheduling techniques on a longterm basis and/or intelligent intraday optimization approaches that handle disruptions to the planned schedule on the fly.
Acknowledgements
Open access funding provided by University of Vienna. We thank EBG MedAustron GmbH for giving us insight into the problem of scheduling recurring radiotherapy treatment appointments and for its fruitful collaboration.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (
http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Appendix: Statistical tests
To prove the superiority of the hybrid method cGAILS relative to the standalone methods GA, ILS with small neighborhood, and ILS with larger neighborhood, we conducted various statistical tests, the results of which are presented in the following Tables
11 and
12. We performed both
t tests (twosided) and Wilcoxon Rank tests and obtained comparable results, as both tests support the hypothesis that the hybrid method achieves significantly better outcomes. ***, **, and * denote
p values
\(\le 0.001\),
\(\le 0.01\), and
\(\le 0.05\), respectively, whereas “ns” indicates cases with
p value
\(>0.05\). For each of the
\(5\times 16=80\) instances, 16 replications were run.