Appointment scheduling algorithm considering routine and urgent patients

• We derive solutions for appointment scheduling with routine and urgent patients with no-show.
• For deterministic service time, an exact method is proposed to find the optimal schedule.
• For exponentially service time, a property is presented to show the objective is not multimodular.
• A heuristic algorithm based on shifting policies is developed to give an upper bound.
• Experiments are conducted to illustrate how the critical factors affect service efficiency.

This paper derives a solution approach to solve the outpatient appointment schedule problem for given numbers of routine and urgent patients considering a no-show probability to minimize the weighted sum of average patient wait time, physician idle time and overtime. An exact deterministic service time method is proposed to find the optimal schedule. An exponentially distributed service time property is presented to show that the objective function for routine and urgent patients is not multimodular, and consequently a local search algorithm based on multimodulary does not guarantee global optimality. Thus, a heuristic algorithm based on two kinds of shifting policies (HE-TKS) is developed to solve the appointment schedule, which gives a local optimal solution as an upper bound for the optimal schedule. Numerical experiments are conducted to illustrate how the critical factors affect service efficiency of the clinic in practice. It reveals that lower no-show probability, smaller interval lengths, shorter service times, and more urgent patients will benefit both patients and clinics.