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-centered 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).