A sample average approximation approach to stochastic appointment sequencing and scheduling

This article develops algorithms for a single-resource stochastic appointment sequencing and scheduling problem with waiting time, idle time, and overtime costs. This is a basic stochastic scheduling problem that has been studied in various forms by several previous authors. Applications for this problem cited previously include scheduling of surgeries in an operating room, scheduling of appointments in a clinic, scheduling ships in a port, and scheduling exams in an examination facility. In this article, the problem is formulated as a stochastic integer program using a sample average approximation. A heuristic solution approach based on Benders’ decomposition is developed and compared to exact methods and to previously proposed approaches. Extensive computational testing shows that the proposed methods produce good results compared with previous approaches. In addition, it is proved that the finite scenario sample average approximation problem is NP-complete.