Optimal outpatient appointment scheduling with emergency arrivals and general service times

In this paper we study the problem of deciding at what times to schedule non-emergency patients when there are emergency arrivals following a non-stationary Poisson process. The service times can have any given distribution. The objective function consists of a weighted sum of the waiting times, idle time and overtime. We prove that this objective function is multimodular, and then use a local search algorithm which in that case is guaranteed to find the optimal solution. Numerical examples show that this method gives considerable improvements over the standard even-spaced schedule, and that the schedules for different service time distributions can look quite different.