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: | Ghate Archis, Salemi Parizi Mahshid |
Keywords: | combinatorial optimization, programming: markov decision, programming: dynamic |
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.