Optimization and approximation methods for dynamic appointment scheduling with patient choices

A well-designed appointment scheduling system in healthcare should take into account patient choices in order to improve patient satisfaction. A dynamic programming model is proposed to decide which slots should be offered for patients to choose from. We characterize optimal offer sets with a simple form by using the notion of “complete set”, in which all slots with revenues higher than a certain value are offered. An approximate method making use of the complete-set policy is proposed for estimating the value associated with the system state. Experiments show that the complete-set policy is effective and efficient. The model is extended to handle a general appointment system, in which the reward depends on both patients and healthcare service providers. The complete-set policy continues to exhibit excellent performances.