A column generation approach for patient scheduling with setup time and deteriorating treatment duration

Nowadays most cancer patients are treated by radiotherapy. The treatment duration of patients will grow longer over time because of the half-life decaying effect of the radioactive source, which can be regarded as a continuous non-linear deteriorating effect. How to sequence the treatment of the patients before the radioactivity is reduced to the lowest available intensity is an important and complex problem. Meanwhile, the treatment sequence of cancer patients should not only be based on the waiting time but also on the severity of their illness. Therefore, the dual factors which reflect the severity of patients’ illness as well as waiting time should be considered. The dual factors are denoted as the treatment value of patients in this paper and we determine patients in the waiting list to be selected, assigned and sorted for treatment, so as to maximize the overall treatment value of all patients. We also consider the setup time for each time of treatment, which cannot be ignored in reality. The original problem model is difficult to solve directly, so we reformulate the original problem to a set covering problem and it is solved by a column generation approach we develop. The master problem of selecting plans for treatment blocks and subproblems of generating plans are solved by GUROBI and dynamic programming, respectively. Numerical experiments are conducted to demonstrate the efficiency of the proposed column generation approach.