OUTPATIENT APPOINTMENT SCHEDULING WITH WALK-INS IN FIXED ARRIVAL PERIODS

We study the problem of determining an optimal appointment schedule in the presence of walk-ins arriving in a specified time interval. We first consider the problem of scheduling patients in the presence of walk-ins arriving at the start of the schedule. We show that the objective functions for the optimisation problems proposed with and without no-show behaviour are multimodular. Based on this result, we propose an efficient local search algorithm variable neighbourhood descent local search to solve the problems. Our proposed local search algorithm performs better than some other algorithms proposed in the literature. We further study the problem of determining the optimal time interval of the arrival of walk-ins to specify. Numerical studies show that an optimal schedule depends on whether the number of patients to schedule is a decision variable or a fixed constant. Furthermore, our result shows that overbooking policy is not an operational lever for mitigating the effect of no-show behaviour only, but can be used to balance the effect of random walk-ins. Moreover, our result reveals that the policy that stipulates an optimal time window of arrival of walk-ins performs better than the general random walk-in arrival policy.