Particle therapy patient scheduling: First heuristic approaches

The Particle Therapy Patient Scheduling Problem arises in radiotherapy used for cancer treatment. Previous contributions in the existing literature primarily dealt with photon and electron therapy with a one-to-one correspondence of treatment rooms and accelerators. In particle therapy, however, a single accelerator serves multiple rooms in an interleaved way. This leads to a novel scenario in which the main challenge is to utilize the particle beam as well as possible. Switching between rooms allows to reduce idle time of the beam that emerges as a consequence of preparation steps. In this work we present first algorithms for solving this problem. In particular, we address the midterm planning variant which involves a time horizon of a few months but also requires detailed scheduling within each day. We formalize the problem via a mixed integer linear programming model, which, however, turns out to be intractable in practice. Consequently, we start with a construction heuristic featuring a forward-looking mechanism. Based upon this fast method we further study a Greedy Randomized Adaptive Search Procedure as well as an Iterated Greedy metaheuristic. A computational comparison of these algorithms is performed on benchmark instances created in a way to reflect the most important aspects of a real-world scenario.