03 December 2019
Vienna University of Technology
Learning Systems Department
Matthias Horn

In modern particle therapy for cancer treatment, carbon or proton particles are accelerated in cyclotrons or synchrotrons to almost the speed of light and from there directed into a treatment room where a patient is radiated. A number of differently equipped treatment rooms is available and the particle beam can only be directed into one of these rooms at a time. In this talk we introduce the "Job Sequencing with One Common and Multiple Secondary Resource" problem that arises in the context of scheduling patients in such particle therapy facilities. We propose a novel anytime A* algorithm, which uses an advanced diving mechanism based on beam search and local search to find good heuristic solutions early. An extensive experimental evaluation on two types of problem instances shows the effectiveness of the A* algorithm. It typically yields either optimal solutions or solutions with an optimality gap of less than 1%.