A Hybrid GA-SA for the Urgent Patients Disturbed Physical Examination Rescheduling Problem Considering Setup Time

In the practice of medical services, the occurrence of disturbance events will inevitably interrupt the pre-arranged patient visit sequence and medical resource arrangement, so rescheduling is essential. In this paper, in view of the disturbance event of urgent patients and the setup time of medical equipment that cannot be ignored, we studied the urgent patient disturbance physical examination rescheduling problem that considering setup time. The optimization goal is to minimize the sum of medical equipment’s setup time and diagnostic completion time of all patients. In this problem, multiple patients need to be examined in multiple medical equipment, and the setup time of all patients on a medical equipment are sequence-dependent which was rarely considered in the previous medical service scheduling research. One of our contributions is that when constructing the mathematical model for the problem, we first introduced the change on the original patient’s visit sequence between rescheduling and initial scheduling should be less than a given upper bound as the constraint to reduce the impact on the original patient. Another contribution is that since the problem addressed is strongly NP-hard, combined the global search performance of the Genetic algorithm (GA) and the local search performance of the Simulated Annealing algorithm (SA), we proposed a hybrid algorithm (HGA-SA) of improved GA and improved SA to solve the problem. Finally, the model and algorithm are verified through extensive simulation experiments, results show that the proposed algorithm has good performance compared with several other existing algorithms.