8. Advance Patient Appointment Scheduling

This chapter describes the use of the linear programming approach to approximate dynamic programming as a means of solving advance patient appointment scheduling problems, which are problems typically intractable using standard solution techniques. Starting from the linear programming approach to discounted infinite-horizon Markov decision processes, and employing an affine value function approximation in the state variables, the method described in this chapter provides a systematic way of identifying effective booking guidelines for advance patient appointment scheduling problems. Two applications found in the literature allow us to show how these guidelines could be used in practice to significantly increase service levels for medical appointments, measured as the percentage of patients booked within medically acceptable wait times, and thus to decrease the potential impact of delays on patients’ health.