A Variable neighborhood search for the job sequencing with one common and multiple secondary resources problem

Abstract

Diese Arbeit behandelt heuristische Verfahren zur Lösung eines Optimierungsproblem, welches in modernen Krebsbehandlungseinrichtungen auftritt, in welchen ein Partikelstrahl mehrere Behandlungsräume abwechselnd bedient. Obwohl in der näheren Vergangenheit bereits verschiedenste Optimierungsprobleme im Kontext solcher Einrichtungen intensiv untersucht wurden, liegt der Fokus dieser Arbeit jedoch ausschließlich auf dem kürzlich von Horn et al. beschriebenen Teilproblem zur Ermittlung von täglichen Ablaufplänen. Insbesondere sind wir daran interessiert die zeitliche Abfolge einer Menge von nicht unterbrechbaren Aufgaben zu bestimmen und dabei eine Zielfunktion zu minimieren. Während der Ausführung der Aufgaben sind grundsätzlich zweierlei Ressourcen anzufordern. Eine Ressource welche von allen Aufgaben geteilt wird, jedoch nur für einen Bruchteil der gesamten Ausführungszeit einer Aufgabe anzufordern ist, sowie einer sekundären Ressource, welche zwar für die gesamte Ausführungszeit benötigt wird, jedoch nur mit einer Teilmenge der anderen Aufgaben geteilt wird. Ziel ist es, eine gültige Lösung zu finden, welche einerseits alle Einschränkungen hinsichtlich der Ressourcen erfüllt, sowie den Zeitpunkt der Beendigung der letzten Aufgabe, die Makespan, minimiert. In ihrer Arbeit stellten Horn et al. ein exaktes Optimierungsverfahren vor und zeigten dessen Effektivität zur Ermittlung optimaler Lösungen für eine Vielzahl an großer Instanzen. Da sich jedoch einige Instanzen für ihren Ansatz als schwieriger herausstellten und heuristisches Verbesserungspotential vermuten ließen, wurde als alternativer Lösungsansatz im Zuge dieser Arbeit ein metaheuristisches Verfahren basierend auf einer Variablen Nachbarschaftssuche (VNS) entwickelt und analysiert. Hierzu beschäftigt sich diese Arbeit zu Beginn vorranging mit effizienten Evaluierungsansätzen in der kodierten Lösungsrepräsentation und zeigt ein konstantes Laufzeitverhalten bezüglich der Anzahl der Aufgaben in experimenteller Weise. In Folge dessen werden verschiedenste Aspekte von Suchlandschaften in mehreren Experimenten untersucht und dienen als Grundlage für die Entwicklung der VNS, in welcher effiziente Intensivierungsphasen mit exponentiell stärker diversifizierenden Mechanismen kombiniert zum Einsatz kommen. Abschließend werden in einer Reihe von Experimenten verschiedenste Variationen des entwickelten Algorithmus analysiert und mit den Ansätzen von Horn et al. verglichen. Es kann gezeigt werden, dass das entwickelte Verfahren für eine weites Spektrum an Eingabeinstanzen hochqualitative Lösungen mit einem durchschnittlichen Optimality Gap nicht größer als 0.288% finden kann.

In this thesis we are interested in heuristically solving a problem appearing in novel cancer treatment facilities, where a particle beam serves multiple treatment rooms in a multiplexed manner. Previously, several variations of the induced optimization problem have been studied intensively, however, in this work, we solely concentrate on the subproblem of finding feasible daily schedules, as recently introduced by Horn et al. In particular, we are interested in scheduling a set of jobs without preemption while minimizing the objective function. Each job needs two types of resources. The common resource is shared among all jobs but is acquired only for a certain period in a jobs processing time, whereas secondary resources are shared only among a subset of the jobs but have to be acquired throughout a jobs entire processing time. The objective is to obtain a feasible solution that satisfies all resource constraints and minimizes the makespan. In their work, Horn et al. proposed a complete optimization approach and showed its effectiveness to obtain globally optimal solutions for a diverse set of even large instances. However, some instances turned out to be more challenging for their approach, thus left some room for heuristic improvement. To this end, this thesis proposes a Variable Neighborhood Search (VNS) for the considered problem and experimentally evaluates various aspects of it. We start this work with efficient evaluation schemes for different neighborhood structures on an encoded solution representation and experimentally show its constant temporal behavior with respect to the number of jobs. We then analyze different aspects of the encountered search landscapes in various experiments and subsequently use the findings to devise a proper VNS, where efficient intensification phases are combined with exponentially more perturbative diversification techniques. Finally, in a series of experiments we study different variations of the devised algorithm, compare them to the selected baseline algorithms from Horn et al. and thereby show its effectiveness to obtain high-quality solutions with an average optimality gap not greater than 0.288% throughout the considered instance classes.