Multi-class, multi-resource advance scheduling with no-shows, cancellations and overbooking

Multi-class, multi-resource advance scheduling with no-shows, cancellations and overbooking

0.00 Avg rating0 Votes
Article ID: iaor201530012
Volume: 67
Issue: 4
Start Page Number: 90
End Page Number: 101
Publication Date: Mar 2016
Journal: Computers and Operations Research
Authors: ,
Keywords: combinatorial optimization, programming: markov decision, programming: dynamic
Abstract:

We investigate a class of scheduling problems where dynamically and stochastically arriving appointment requests are either rejected or booked for future slots. A customer may cancel an appointment. A customer who does not cancel may 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. The system receives a reward for providing service; and incurs costs for rejecting requests, appointment delays, and overtime. Customers are heterogeneous in all problem parameters. We provide a Markov decision process (MDP) formulation of these problems. Exact solution of this MDP is intractable. We show that this MDP has a weakly coupled structure that enables us to apply an approximate dynamic programming method rooted in Lagrangian relaxation, affine value function approximation, and constraint generation. We compare this method with a myopic scheduling heuristic on eighteen hundred 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.

Reviews

Required fields are marked *. Your email address will not be published.