Particle therapy patient scheduling with limited starting time variations of daily treatments

• Author: Johannes Maschler,Günther R. Raidl
• Date: 01 January 2020
• Published date: 01 January 2020
• DOI: http://doi.org/10.1111/itor.12579

Intl. Trans. in Op. Res. 27 (2020) 458–479

DOI: 10.1111/itor.12579

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Particle therapy patient scheduling with limited

starting time variations of daily treatments

Johannes Maschler and G¨

unther R. Raidl

Institute of Logic and Computation, TU Wien, Favoritenstraße 9–11/186-1, 1040 Vienna, Austria

E-mail: maschler@ac.tuwien.ac.at [Maschler];raidl@ac.tuwien.ac.at [Raidl]

Received 15 November2017; received in revised form 7 May 2018; accepted 15 July 2018

Abstract

The particle therapy patient scheduling problem (PTPSP) arises in modern cancer treatment facilities that

provide particle therapy. It consists of scheduling a set of therapies within a planning horizon of several

months. A particularity of PTSP compared with classical radiotherapy scheduling is that therapies need not

only be assigned to days but also scheduled within each dayto account for the more complicated operational

scenario. In an earlier work,we introduced this novel problem setting and provided first algorithms including

an iterated greedy (IG) metaheuristic. In this work, we consider an important extension to the PTPSP

emerging from practice in whichthe therapies should be provided on treatment days roughlyat the same time.

To be more specific, the variation between the starting times of the therapies’ individual treatments should

not exceed the given limits, and needs otherwise to be minimized. This additional constraint implies that the

sequencing parts within each day can no longer be treated independently. To tackle this variant of PTPSP, we

revise our previous IG and exchange its main components: the part of the applied construction heuristic for

scheduling within the days and the local search algorithm. The resulting metaheuristic provides promising

results for the proposed extension of the PTPSP and further enhances the existing approach for the original

problem.

Keywords:cancer treatment; particle therapy patient scheduling; iterated greedy metaheuristic; hybridmetaheuristic

1. Introduction

Particle therapy is a relatively novel and highly promising option to provide cancer treatments. A

proton or carbon beam is produced byeither a cyclotron or a synchrotron and is directed into one of

up to five treatment rooms, where patients areirradiated. Since several tasks have to be completed in

a treatment room before and after an actual irradiation, the usually single availablebeam is switched

between the available treatment rooms to maximize the throughput of the facility. Consequently,

The copyright line for this article was changed on November20, 2018 after original online publication.

C

2018 The Authors.

International Transactions in Operational Research published by John Wiley & Sons Ltd on behalf of International Federation

of Operational Research Societies

This is an open access article under the terms of the Creative Commons Attribution License,which permits use, distribution and

reproduction in any medium, provided the original work is properlycited.

J. Maschler and G. R. Raidl / Intl. Trans.in Op. Res. 27 (2020) 458–479 459

the main challenge is to arrange the individual treatments in such a way that idle times on the

particle beam are minimized. We consider here specifically the particle therapy treatment center

MedAustron in Wiener Neustadt, Austria, which offers three treatment rooms.

The particle therapy patient scheduling problem (PTPSP) addresses the midterm planning part

of such a particle therapy treatment center and was first introduced in our recent work (Maschler

et al., 2016). In PTPSP an effective plan has to be found for performing numerous therapies, each

consisting of daily treatments (DTs) provided on 8–35 subsequent days. Therapies have to start on

Mondays or Tuesdays between an earliest and alatest allowed starting day.After a therapy is started,

the number of DTs that are provided each week has to stay between a lower and an upper bound.

Moreover, there is a minimal and a maximal number of days that are allowed to pass between two

subsequent DTs, and there has to be a break from the treatment of at least two consecutive days

each week. The DTs have resource requirements that vary with time, but each specific resource is

required at most once for a consecutive time period. These varying requirements originate from the

different tasks involved in providing the treatments. Each resource can only be used by one DT at

a time. Among others, the considered resources involve the particle beam, treatment rooms, radio

oncologists, and an anesthetist. In terms of the resource-constrained project scheduling literature

(see, e.g., Hartmann and Briskorn, 2010), DTs would be called activities with resource requests

varying with time. Typically, the facility is open from Mondays to Fridays, but after recurring

maintenance tasks DTs are also performed on Saturdays. Whenever the treatment center is open,

resources havea regular availability period followed by an extended availability period in whichthey

can be used, where the use of the latter induces (additional) costs. Furthermore, the availability of

resources can be interrupted by so-called unavailability periods. The aim of the PTPSP is to schedule

a given set of therapies by determining days and times for all corresponding DTs while considering

all operational constraints. The objective is to minimize the use of extended availability periods,

while the therapies have to be completed as early as possible. In addition, the DTs belonging to the

same therapy should be planned roughly at the same time, in order to provide a consistent schedule

for the patients. Ideally, the starting times of a therapy’s DTs should not differ more than a half an

hour within each week. Between two weeks, the starting times are allowed to differ by two hours.

However, consistent starting times for DTs are not of direct medical relevance and, consequently,

should not induce additional use of extended service periods or delay therapies. This consideration

of similar DT starting times is a practically highly relevant extension of the PTPSP as introduced

in Maschler et al. (2016).

The aim of this work is twofold. On the one hand, PTPSP is extended to cover the aspect

that the variation among the times at which therapies’ DTs are provided is minimized. On

the other hand, we study an improved variant of the iterated greedy (IG) metaheuristic from

Maschler et al. (2016). Preliminary results of this effort for the original problem formulation

have been published in Maschler et al. (2017). We propose a novel construction heuristic that

assigns DTs to days as the previous construction heuristic but replaces the part for determining

starting times with one that is more appropriate for the extended problem variant. This new

heuristic applied within the IG’s construction phase is able to keep relative timing characteristics

of untouched DTs to a larger extent. Furthermore, we replace the so far rather simple local

improvement operator by a local search method that alternately considers a DT exchange

neighborhood and solves a linear programming (LP) model for determining updated nominal

starting times. The IG is compared with our previous metaheuristic and shows significant

C

2018 The Authors.

International Transactions in Operational Research published by John Wiley& Sons Ltd on behalf of International Federation

of Operational Research Societies