Scheduling of Patients in Emergency Departments with a Variable Neighborhood Search

The dynamic scheduling of patients to doctors in an emergency department environment is tackled in this work. We consider the case in which patients arrive dynamically during the working hours, and the objective is to minimize the weighted tardiness. We propose a greedy heuristic based on priority queues and a general variable neighborhood search (GVNS). In the greedy heuristic, patients are scheduled by observing their urgency, while in the GVNS, the schedule is optimized every time a patient arrives. The GVNS uses six neighborhood structures and a variable neighborhood descent to perform the local search. The GVNS also handles the static problem whose solution can be used as a reference for the dynamic one. Computational results on 80 instances show that using the GVNS better approximates the static problem, besides giving an overall reduction of 66.8% points over the greedy heuristic.