<div class="csl-bib-body">
<div class="csl-entry">Höfler, M. (2018). <i>Methods for intraday scheduling in particle therapy</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2018.42364</div>
</div>
-
dc.identifier.uri
https://doi.org/10.34726/hss.2018.42364
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/7908
-
dc.description.abstract
In dieser Arbeit behandeln wir das Intraday Particle Therapy Patient Scheduling Problem (I-PTPSP), ein Planungsproblem für Behandlungstermine von Patienten, das in medizinischen Einrichtungen für Krebstherapien mit Synchrotrons, einem speziellen Typ von Teilchenbeschleunigern für die Strahlentherapie, auftritt. Das Problem beschreibt bevorstehende Behandlungen mit bereits zugewiesenen Terminen auf einen Zeithorizont von maximal einem Tag. Die Problematik liegt darin, dass durch unvorhergesehene Ereignisse diese Behandlungen nicht mehr zu den vorgesehenen Zeitpunkten durchgeführt werden können und deshalb der bestehende Zeitplan an die neue Situation angepasst werden muss. Dieser neue Zeitplan muss möglichst schnell erstellt werden, um negative Auswirkungen auf beispielsweise die Wartezeiten und laufenden Kosten der Einrichtung zu begrenzen. Das I-PTPSP modelliert diese Situation. Eine Besonderheit des I-PTPSP liegt in der Art und Weise wie die Behandlungen durchgeführt werden. Das Synchrotron kann mehrere Behandlungsräume abwechselnd hintereinander bedienen. Das Ziel besteht nun darin, solche Belegungspläne zu finden, in denen Leerlaufzeiten des Beschleunigers möglichst vermieden werden. Neben dem Strahl und den Behandlungsräumen gibt es weitere relevante Ressourcen, die berücksichtigt werden müssen. In dieser Arbeit betrachten wir zunächst verschiedene Varianten von Greedy Konstruktionsheuristiken, um erste Lösungen für das Problem zu erhalten. Die hierfür verwendeten Ansätze nutzen wir anschließend, um ein Branch and Bound (BAB) Verfahren zu entwickeln. Hierbei untersuchen wir sowohl verschiedene Auswahlstrategien der Knoten aus dem BAB-Baum, als auch diverse Techniken um untere Schranken für die Teillösungen zu berechnen. Weiters wird als Referenz ein Constraint Programming (CP) Modell erstellt und mithilfe eines CP Solvers gelöst. Schlussendlich vergleichen wir die Ergebnisse unserer Verfahren mit denen dieser Referenzimplementierung. Hierfür erstellen wir verschiedene Szenarien unterschiedlicher Größe, welche reale Anwendungsfälle, wie eine Verzögerung in einem Behandlungsraum oder eine dringend benötigte Wartung eines medizinischen Gerätes, simulieren. Die so erstellten Problem-Instanzen werden anschließend verwendet, um die Verfahren miteinander zu vergleichen. Während alle drei Methoden ähnlich gute Ergebnisse bei Instanzen kleinerer Größe liefern, zeigt sich, dass der Branch and Bound Algorithmus die anderen beiden Ansätzen bereits bei Problemen ab mittlerer Größe übertrifft.
de
dc.description.abstract
We consider the Intraday Particle Therapy Patient Scheduling Problem (I-PTPSP), a patient scheduling problem that arises in facilities specialized on cancer treatment with synchrotrons, a device for particle therapy treatments. This problem has a time horizon of a single day and already assigned starting times for the pending treatments from an earlier created weekly or monthly schedule. If unforeseen circumstances occur, these predefined schedules need to be adjusted to adapt to the new situation. Finding these new schedules quickly is essential to limit any negative impacts on the waiting times of the patients or the running costs of the facility. The I-PTPSP models this situation. A specialty of the I-PTPSP is the way how the treatments are processed. The synchrotron can serve multiple treatment rooms alternatingly. The aim is to find schedules of treatments that occupy the different treatment rooms in such a way that avoids idle times of the synchrotron to increase the throughput of the facility. Beside the synchrotron and the treatment rooms, other resources are relevant and need to be considered. In this work, we tackle the I-PTPSP with multiple variants of a greedy construction heuristic first. Then, we solve it with a Branch and Bound approach that incorporates some of the ideas obtained during the development of the construction heuristic. In addition, we examine and develop several traversal strategies of the Branch and Bound node tree, as well as, different techniques to obtain lower bounds for the partial solutions. Furthermore, a constraint programming (CP) model solved by a state-of-the-art CP solver is developed. Finally, we compare our solution to this reference implementation. For that reason, we simulate different scenarios of various sizes that resemble real world use cases like a delay in a treatment room or a suddenly needed maintenance of a medical device. The so obtained problem instances are used to compare the performance of our three approaches. While all three approaches perform almost equally well on the smaller instances, the Branch and Bound approach clearly outperforms the other two on the medium to larger problem inputs.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Scheduling
de
dc.subject
Metaheuristiken
de
dc.subject
Constraint Programming
de
dc.subject
Mathematical Programming
de
dc.subject
Scheduling
en
dc.subject
Metaheuristics
en
dc.subject
Constraint Programming
en
dc.subject
Mathematical Programming
en
dc.title
Methods for intraday scheduling in particle therapy
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.identifier.doi
10.34726/hss.2018.42364
-
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Michael Höfler
-
dc.publisher.place
Wien
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
dc.contributor.assistant
Maschler, Johannes
-
dc.contributor.assistant
Riedler, Martin
-
tuw.publication.orgunit
E186 - Institut für Computergraphik und Algorithmen