Online algorithms with foresight for radiotherapy patient scheduling

A radiotherapy treatment consists of a given number of radiation sessions, which should start before a specified due date and have a duration that varies based on the patient category. Waiting time is the main critical issue in the management of a radiotherapy health system: the time elapsed between the first consultation and the first treatment is typically rather long and delays have the potential to damage the health status of the patients. Then, an efficient use of available linacs is crucial to ensure the success of the treatment. In this paper, we deal with a Radiotherapy Patient Scheduling (RPS) problem at the pure-online level under the blocking policy, which divides work shifts into time slots of equal duration. We propose online algorithms that enable the scheduling of a sequence of appointments for each patient, all at the same time slot each day, whenever a patient needs to commence a series of radiotherapy sessions. Considering a realistic and patient-centred operational context, the problem becomes highly challenging, even in its offline setting. We address this problem by introducing the concept of online optimisation with foresight, which is the common framework of the proposed approaches. The rationale behind foresight is to take real-time decisions under uncertainty by exploiting the partial knowledge of the optimal solution structure. A quantitative analysis shows that the proposed algorithms outperform two competitor algorithms inspired by the literature. Furthermore, the exploitation of a pattern observed in the offline solutions of the problem (implicit foresight) results to be more flexible and effective than using a solution structure given by integer linear programs on the most likely scenario (explicit foresight).