Particle therapy patient scheduling: First heuristic approaches

Johannes Maschler, Martin Riedler, Markus Stock, Günther R. Raidl

Research output: Contribution to book/report/conference proceedingContribution to conference proceeding

15 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationPATAT 2016 - Proceedings of the 11th International Conference on the Practice and Theory of Automated Timetabling
EditorsEdmund K. Burke, Luca Di Gaspero, Ender Ozcan, Barry McCollum, Andrea Schaerf
PublisherPATAT
Pages223-244
Number of pages22
ISBN (Electronic)9780992998417
Publication statusPublished - 2016
Externally publishedYes
Event11th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2016 - Udine, Italy
Duration: 23 Aug 201626 Aug 2016

Publication series

NamePATAT 2016 - Proceedings of the 11th International Conference on the Practice and Theory of Automated Timetabling

Conference

Conference11th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2016
Country/TerritoryItaly
CityUdine
Period23.08.201626.08.2016

Keywords

  • GRASP
  • Iterated Greedy
  • Metaheuristic
  • Particle therapy
  • Patient scheduling
  • Radiotherapy

ASJC Scopus subject areas

  • Computer Science Applications

Fingerprint

Dive into the research topics of 'Particle therapy patient scheduling: First heuristic approaches'. Together they form a unique fingerprint.

Cite this