<div class="csl-bib-body">
<div class="csl-entry">Jatschka, T. (2017). <i>An iterative time-bucket refinement algorithm for high resolution scheduling problems</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2017.45162</div>
</div>
-
dc.identifier.uri
https://doi.org/10.34726/hss.2017.45162
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/8314
-
dc.description.abstract
In dieser Arbeit werden Algorithmen zum Lösen von Scheduling Problemen, die einem langen Zeithorizont unterliegen, entwickelt. Diese Algorithmen werden auf ein Problem, das durch ein Patientenplanungsszenario des Krebsbehandlungszentrums MedAustron in Wiener Neustadt, Österreich, motiviert ist, angewandt. Ziel ist es, einen Plan für die individuellen Behandlungstermine der Patienten zu erstellen, sodass zeitliche Abhängigkeiten zwischen den Behandlungen eingehalten werden. Jede Behandlungsphase benötigt verschiedene Ressourcen. Eine dieser Ressourcen ist der Teilchenstrahl, dessen Nutzung insbesondere optimiert werden muss, da er für jede Behandlung benötigt wird und abwechselnd in mehreren Behandlungsräumen eingesetzt wird. Es soll ein Plan erstellt werden, der so dicht wie möglich ist, sodass möglichst viele Patienten behandelt werden können. Außerdem führt ein kompakter Plan zu einer Reduzierung der Standzeit des Teilchenstrahls. Es werden sowohl exakte als auch heuristische Verfahren entwickelt, um das Problem zu lösen. Als heuristisches Lösungsverfahren wird eine Greedy Randomized Adaptive Search Procedure (GRASP) verwendet. Die exakten Algorithmen basieren auf gemischtganzzahliger linearer Optimierung (engl. mixed integer linear programming (MILP)). Es werden verschiedene MILP-Modelle entwickelt und sowohl in Bezug auf die Modellstärke als auch mithilfe empirischer Experimente miteinander verglichen. Der Hauptalgorithmus der Arbeit ist eine Matheuristik, die MILP mit heuristischen Ansätzen kombiniert. Die Grundidee besteht darin, das Problem zu lösen, ohne explizit den gesamten Zeithorizont zu berücksichtigen. Stattdessen basiert der Algorithmus auf einem relaxierten Modell, in dem der Zeithorizont in sogenannte time-buckets partitioniert wird. Dieses reduzierte Modell ist üblicherweise viel kleiner als das ursprüngliche und kann daher relativ schnell gelöst werden. Eine Lösung des relaxierten Problems repräsentiert eine duale Schranke für den tatsächlichen Lösungswert. Bei der Lösung handelt es sich aber üblicherweise nicht um einen gültigen Plan. Daher wird eine Heuristik verwendet, deren Ziel es ist, eine gültige Lösung (primale Schranke) aus der Lösung des relaxierten Modells abzuleiten. Darüber hinaus zerteilt der Algorithmus mehrere time-buckets, um nach erneutem Lösen des Modells eine bessere Schranke zu erhalten. Die Unterteilung basiert auf Informationen, die aus der Lösung des relaxierten Modells gewonnen werden. Durch das iterative Ausführen dieser Prozedur ergibt sich eine Matheuristik, welche schlussendlich zu einer beweisbar optimalen Lösung konvergiert.
de
dc.description.abstract
In this thesis algorithms are developed for solving scheduling problems subject to a large time horizon. We apply these algorithms on a problem motivated by a real world patient scheduling scenario at the cancer treatment center MedAustron located in Wiener Neustadt, Austria. The tasks involved in providing a given set of patients with their individual particle treatments shall be scheduled in such a way that given minimum and maximum waiting times are respected. Each task needs certain resources for its execution. One of the resources is the particle beam which is particularly scarce as it is required by every treatment and shared between several treatment rooms. The goal is to find a schedule which is as dense as possible to allow treating as many patients as possible. Moreover, a dense schedule reduces the idle time of the particle beam within the day. We develop different exact as well as heuristic algorithms for tackling the problem. A greedy randomized adaptive search procedure (GRASP) is used to heuristically solve the problem. The exact algorithms are based on mixed integer linear programming (MILP). We provide different MILP models and compare the strength of models that are of particular interest. The main algorithm of this thesis is a matheuristic which combines exact mathematical programming methods as well as heuristic approaches. The basic idea of our matheuristic is to solve the problem without explicitly considering the complete time horizon. Instead, the algorithm considers a relaxed model which is based on partitioning the time horizon into so called time-buckets. This relaxation is typically much smaller than the original model and can be solved relatively quickly. An obtained solution provides a dual bound for the problem’s solution value but in general does not represent a feasible schedule. Using the solution to the relaxation, the algorithm tries to heuristically derive a primal bound, i.e., a feasible schedule. Moreover, the algorithm also subdivides some timebuckets based on information gained from the solution to the relaxation and resolves the resulting refined model to obtain an improved bound on the problem. Doing this refinement iteratively yields a matheuristic that in principle converges to a provably optimal solution. A novel set of test instances is used to evaluate the performance of different refinement strategies of the matheuristic and to compare the matheuristic to other exact and heuristic methods.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Patienten-Scheduling
de
dc.subject
Mixed Integer Programming
de
dc.subject
Matheuristics
de
dc.subject
timebucke relaxation
de
dc.subject
Patient Scheduling
en
dc.subject
Mixed Integer Programming
en
dc.subject
Matheuristics
en
dc.subject
timebuckt relaxation
en
dc.title
An iterative time-bucket refinement algorithm for high resolution scheduling problems
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.2017.45162
-
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Thomas Jatschka
-
dc.publisher.place
Wien
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
dc.contributor.assistant
Raidl, Günther
-
dc.contributor.assistant
Maschler, Johannes
-
tuw.publication.orgunit
E186 - Institut für Computergraphik und Algorithmen
-
dc.type.qualificationlevel
Diploma
-
dc.identifier.libraryid
AC14543308
-
dc.description.numberOfPages
95
-
dc.identifier.urn
urn:nbn:at:at-ubtuw:1-107635
-
dc.thesistype
Diplomarbeit
de
dc.thesistype
Diploma Thesis
en
tuw.author.orcid
0000-0003-1885-8905
-
dc.rights.identifier
In Copyright
en
dc.rights.identifier
Urheberrechtsschutz
de
tuw.advisor.staffStatus
exstaff
-
tuw.assistant.staffStatus
staff
-
tuw.assistant.staffStatus
exstaff
-
tuw.assistant.orcid
0000-0002-3293-177X
-
item.mimetype
application/pdf
-
item.grantfulltext
open
-
item.languageiso639-1
en
-
item.fulltext
with Fulltext
-
item.cerifentitytype
Publications
-
item.openaccessfulltext
Open Access
-
item.openairetype
master thesis
-
item.openairecristype
http://purl.org/coar/resource_type/c_bdcc
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity