Optimization methods for joint capacity and appointment scheduling problem with walk-in patients

摘要

This paper develops the joint capacity and appointment scheduling model considering both no-show and walk-in patients with the objective of minimizing the total revenue of all patients minus the cost incurred by patients' waiting, physician's idleness and overtime. Under the assumption of deterministic service time and monotonic non-decreasing convex function of waiting and overtime cost, the objective is proved as multimodular function, based on which an exact algorithm converging to the optimal schedule is proposed. Numerical experiments indicate that all the optimal solution will overbook the first interval, and the percentage of overbooked intervals, objective, idleness, tardiness and waiting time of the patients are all very sensitive to the no-show and walk-in probability.