Optimal Advance Scheduling

The dynamic assignment of patients to exam days in order to manage daily variations in demand and capacity is a long-standing open research area in appointment scheduling. In particular, the dynamic assignment of advance appointments has been considered to be especially challenging because of its high dimensionality. We consider a canonical model of dynamic advance scheduling with two patient classes: an urgent demand class, which must be served on the day of arrival, and a regular demand class, which can be served at a future date. Patients take the earliest appointments offered and do not differentiate among providers. We derive a surprising characterization of an optimal policy and an algorithm to compute the policy exactly and efficiently. These are, to our knowledge, the first analytical results for the dynamic advance assignment of patients to exam days. We introduce the property of successive refinability, which allows advance schedules to be easily computable and under which there is no cost to the system to making advance commitments to patients. We allow multiple types of capacity to be considered and both demand and capacity to be nonstationary and stochastic. This paper was accepted by Martin Lariviere, operations management.