An imperialist competition algorithm using a global search strategy for physical examination scheduling

Abstract

The outbreak of the novel coronavirus clearly highlights the importance of the need of effective physical examination scheduling. As treatment times for patients are uncertain, this remains a strongly NP-hard problem. Therefore, we introduce a complex flexible job shop scheduling model. In the process of physical examination for suspected patients, the physical examiner is considered a job, and the physical examination item and equipment correspond to an operation and a machine, respectively. We incorporate the processing time of the patient during the physical examination, the transportation time between equipment, and the setup time of the patient. A unique scheduling algorithm, called imperialist competition algorithm with global search strategy (ICA_GS) is developed for solving the physical examination scheduling problem. A local search strategy is embedded into ICA_GS for enhancing the searching behaviors, and a global search strategy is investigated to prevent falling into local optimality. Finally, the proposed algorithm is tested by simulating the execution of the physical examination scheduling processes, which verify that the proposed algorithm can better solve the physical examination scheduling problem.

Keywords: Flexible job shop scheduling; Global search; Imperialist competition algorithm; Local search; Physical examination scheduling; Setup time; Transportation time.