Abstract
This paper investigates a practical scheduling problem for radiotherapy patients, who are to be scheduled on different devices at different times. The treatment duration is increasing with time because of the continuously decaying effect of the radiation source, which also results in the decline of the serving ability. Therefore, the maintenance activity (replacing radiation source) is necessary to maintain the serving ability of medical institutions. The problem is to determine the schedule of all treatments and also when to have a maintenance activity, so as to minimize the maximum completion time of all the treatments on all devices. The lower bound of the problem is given in this paper. We prove that the optimal solution of the subproblem, i.e., scheduling patients on a single device, is independent of the sequence of the patients and is only related to the division of patients who are assigned before and after the maintenance, and thus, the subproblem can be converted to a two-partition problem. An improved dynamic programming algorithm is proposed to obtain an optimal scheme for this subproblem and its performance is better than other approaches. For multiple-device problem, an effective hybrid algorithm Gaussian crow search algorithm (GCSA) combined with crow search algorithm (CSA) and Gaussian distribution is proposed to assign all patients to different treatment devices. Finally, computational experiments demonstrate the effectiveness and stability of the proposed GCSA which is compared with CSA, simulated annealing (SA) and particle swarm optimization (PSO). The comparison results show that GCSA outperforms other algorithms in a feasible time.
View more >>