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
Year of publication: |
2017
|
---|---|
Authors: | Salemi Parizi, Mahshid ; Ghate, Archis |
Publisher: |
[S.l.] : SSRN |
Description of contents: | Abstract [papers.ssrn.com] ; Abstract [doi.org] |
Saved in:
Extent: | 1 Online-Ressource |
---|---|
Type of publication: | Book / Working Paper |
Language: | English |
Notes: | Nach Informationen von SSRN wurde die ursprüngliche Fassung des Dokuments January 15, 2015 erstellt Volltext nicht verfügbar |
Other identifiers: | 10.2139/ssrn.2550560 [DOI] |
Source: | ECONIS - Online Catalogue of the ZBW |
Persistent link: https://www.econbiz.de/10014036510
Saved in favorites
Similar items by person
-
Multi-class, multi-resource advance scheduling with no-shows, cancellations and overbooking
Parizi, Mahshid Salemi, (2016)
-
Approximate policy iteration for dynamic resource-constrained project scheduling
Parizi, Mahshid Salemi, (2017)
-
Adaptive serach with stochastic acceptance probabilities for global optimization
Ghate, Archis, (2008)
- More ...