Multi-Class, Multi-Resource Advance Scheduling with No-Shows, Cancellations and Overbooking

We investigate a class of scheduling problems where dynamically and stochastically arriving requests for appointments are either rejected or booked for future slots. A customer may cancel an appointment. A customer who does not cancel may, with some probability, fail to show up. The planner may overbook appointments to mitigate the detrimental effects of cancellations and no-shows. A customer needs multiple renewable resources while in service. The system receives a reward for providing service to a customer; and incurs a cost of rejecting requests, a cost for appointment delays, and a cost of overtime. Customers are heterogeneous in their arrival patterns; costs and rewards; resource consumptions; and cancellation and no-show behaviors. Such advance scheduling problems arise in healthcare, revenue management, manufacturing, telecommunications, civilian and military logistics, and high performance computing. We provide a Markov decision process (MDP) formulation of these problems. Owing to the large state- and action-spaces in this MDP, its exact solution is intractable. We show that this MDP has a special, weakly coupled structure. This enables us to apply an approximate dynamic programming method that is rooted in Lagrangian relaxation, affine value function approximation, and constraint generation. We compare the performance of this method with a myopic scheduling heuristic on eighteen hundred randomly generated problem instances. Our experiments show that there is a statistically significant difference in the performance of the two methods in 77% of these instances. Of these statistically significant instances, the Lagrangian method outperforms the myopic method in 97% of the instances