A column generation-based heuristic for brachytherapy patient scheduling with multiple treatment sessions considering radioactive source decay and time constraints

Imbalanced and inefficient schedules of brachytherapy treatment result in long waiting times and a large number of waiting patients, which may raise many subsequent problems. In this paper, we solve the brachytherapy patient scheduling problem with multiple treatment sessions, simultaneously considering the half-life decaying effect of radioactive sources, as well as the strict time constraints on the time interval between any two consecutive treatment sessions and the unavailable time of treatment. Patients on the waiting list are given different weights (priorities) according to the severity of their illness and waiting time. The studied problem aims to efficiently schedule patients in a rolling way to maximize the sum of the weights of the chosen patients from the current waiting list on the premise that the already arranged patients can complete their multiple treatment sessions in the future under strict time constraints. We formulate the problem as an integer programming model and develop a column generation-based heuristic approach on a set partitioning. We propose a pricing algorithm that can add many good patient plans at one iteration and a speed-up strategy to improve the performance of column generation. Computational studies are conducted on abundant test instances generated based on real-world data to demonstrate the efficiency and the high-quality solutions of the proposed approach by comparing with the integer programming model, the set partitioning model, the globally optimal solution, and the “Sessions on the Same Day Every Week” (SSEW) rule currently used in most real-world hospitals. Furthermore, we validate that the proposed approach can reduce the number of waiting patients compared with the SSEW rule. Sensitivity analysis is carried out on critical parameters, and further managerial insights are derived.