A Multi-encoded Genetic Algorithm Approach to Scheduling Recurring Radiotherapy Treatment Activities with Alternative Resources, Optional Activities, and Time Window Constraints

The radiotherapy patient scheduling problem deals with the assignment of recurring treatment appointments to patients diagnosed with cancer. The appointments must take place at least four times within five consecutive days at approximately the same time. Between daily appointments, optional (imaging) activities that require alternative resources, also must be scheduled. A pertinent goal therefore is minimizing both the idle time of the bottleneck resource (i.e., the particle beam used for the irradiation) and the potential risk of a delayed start. To address this problem, we propose a multi-encoded genetic algorithm. The chromosome contains the assignment of treatments to days for each patient, information on which optional activities to schedule, and the patient sequence for each day. To ensure feasibility during the evolutionary process, we present tailored crossover and mutation operators. We also compare a chronological solution decoding approach and an algorithm that fills idle times between already scheduled activities. The latter approach outperforms chronological scheduling on real-world-inspired problem instances. Furthermore, forcing some of the offspring to improve the parent’s fitness (i.e., offspring selection) within the genetic algorithm is beneficial for this problem setting.