Radiation therapy patient scheduling using a column generation approach: an algorithmic framework and a single-institution study

Abstract In radiation therapy (RT), radiation from linear accelerators is used to kill malignant tumor cells. Scheduling patients for RT is difficult both due to the numerous medical and technical constraints, and because of the stochastic inflow of patients with different urgency levels. In this paper, we present a Column Generation (CG) approach for the RT scheduling problem. The model includes constraints such as different machine compatibilities and individualized patient protocols, as well as planned interruptions in treatments due to maintenance on machines. Data from Iridium Netwerk, the largest cancer center in Belgium, is used to evaluate the CG approach. The results show that using a dynamic time reservation method to handle uncertainty in future urgent patients works very well. Furthermore, the schedules generated by the CG algorithm are clinically validated and compared to historical clinical schedules for a time period of one year. The CG generated schedules are shown to decrease the average patient waiting time by 80%, improve the average consistency in appointment times by 80%, and increase the number of treatments scheduled on the best suited machine by more than 90% compared to the manually constructed clinical schedules. Thus, the CG approach to automatically generate schedules for RT can improve the quality of the schedules significantly while saving the clinic many hours of administrative work every week.