Jatschka, T. (2017). An iterative time-bucket refinement algorithm for high resolution scheduling problems [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2017.45162
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
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.