Patient scheduling in particle therapy

Abstract

Particle therapy is an innovative and highly promising option to provide cancer treatments. In particle therapy protons or carbon ions are accelerated and redirected to one of several treatment rooms that all share the single accelerator. Each treatment starts with some specific preparations such as immobilization and positioning of the patient. Then the irradiation using the particle beam takes place. Afterwards, some additional imaging needs to be done before the patient can leave and the treatment room becomes available for a next patient. Ideally, one aims to find a schedule where the particle beam can be directly switched from one treatment room to next without significant breaks. Accomplishing this goal is far from trivial and requires elaborate scheduling techniques. We study the midterm planning problem of such a particle therapy treatment center, which consists of scheduling therapies over the next few months. Therapies involve 8 to 35 daily treatments (DTs) that need to be provided on subsequent days. There are various constraints determining the succession of the therapies DTs including allowed starting days and minimum and maximum numbers of days between subsequent DTs. Next to assigning DTs to days also detailed schedules for each of these days have to be provided. For their execution DTs require several resources for a specified duration. Among those resources are the treatment rooms that are typically required for the whole DT and the particle beam which is needed only during the irradiation. Resources are available for a regular and an extended service time. The objective is to find a schedule for all DTs that minimizes the use of extended service time as well as the therapies finishing days. Since initial investigations soon showed that solving this problem with exact techniques is clearly out of reach, we focus on heuristic and metaheuristic techniques. We propose a constructive heuristic that first assigns DTs therapy-wise to days and afterwards creates schedules for the individual days. Based on this constructive heuristic we provide an iterated greedy (IG) metaheuristic that is able to substantially improve upon the already reasonable results of our greedy heuristic. This initially simple metaheuristic is then improved further in several steps. We first revise the IGs main operators and incorporate a new powerful local search method. Afterwards, an advanced surrogate model is developed to further improve the assignment of DTs to days. In the last stage of extensions we consider the important additional aspect that the DTs belonging to the same therapy should be planned roughly at the same time. In the conducted computational study we show that each of these extensions results in a significant improvement of the approach.Next we focus in more detail on the isolated scheduling of DTs at single days. In the considered more abstract problem we are given a set of jobs with similar characteristics as DTs. Due to time windows only a subset of the jobs can typically be feasibly scheduled. The objective is to maximize the total prize associated with each of the scheduled jobs. This prize-collecting aspect reflects the need of delaying less critical DTs to later days if for the considered day the facilitys capacity is reached. We study for this problem the application of decision diagrams (DDs). Relatively compact relaxed and restricted DDs are employed that represent discrete relaxations for the problem and encode heuristic solutions, respectively. The prize-collecting aspect of the problem at hand has not been studied in this form before and provides new interesting challenges. We investigate different methods for compiling relaxed and restricted DDs for our sequencing problem. We start by adapting the two proposed compilation approaches in the literature and are, to the best of our knowledge, the first who directly compare them experimentally. These traditional compilation methods have, however, the disadvantage that they can cause for our problem major redundancies in the DDs. For this reason, we propose a novel construction scheme for relaxed DDs inspired by A search that provides more flexibility. In comparison to the two traditional approaches we can compile for our problem in shorter time substantially smaller DDs that yield stronger bounds. We show further how the information already contained in a previously compiled relaxed DD can be exploited during the construction of restricted DDs. With our novel approaches we are in many cases able to construct a higher quality relaxed DD and restricted DD in less than half of the time than compiling both with conventional approaches. The general approach applied here appears to be also promising for problems in other applications domains. We give further an overview of developed solution approaches for two additional optimization problems. One is a strip packing variant that is solved using a logic-based Benders decomposition. The other is a resource-constrained project scheduling problem that requires scheduling in a high temporal resolution. A so-called time-bucket relaxation of the problem is iteratively refined in the suggested solution approach.