Numerical results reveal that the direct search-based ADP outperforms others in the majority of problem sets generated.
📌 3 Key Takeaways
🎯
Objective & Hypothesis:This paper focuses on the performance comparison of several approximate dynamic programming (ADP) techniques.
📊
Key Findings & Data:In particular, we evaluate three ADP techniques through a class of dynamic stochastic scheduling problems: Lagrangian-based ADP, linear programming-based ADP, and direct search based ADP.
💡
Conclusion & Impact:Numerical results reveal that the direct search-based ADP outperforms others in the majority of problem sets generated.
🔬Design:Research Article
📍Scope:Comprehensive Sample
⚙️Variables:Domain Parameters
Abstract
This paper focuses on the performance comparison of several approximate dynamic programming (ADP) techniques. In particular, we evaluate three ADP techniques through a class of dynamic stochastic scheduling problems: Lagrangian-based ADP, linear programming-based ADP, and direct search based ADP. We uniquely implement the direct search-based ADP through basis functions that differ from those used in the relevant literature. The class of scheduling problems has the property that jobs arriving dynamically and stochastically must be scheduled to days in advance. Numerical results reveal that the direct search-based ADP outperforms others in the majority of problem sets generated.
🔖
Cite This Article
GÖÇGÜN, Y. (2022). Performance comparison of approximate dynamic programming techniques for dynamic stochastic scheduling. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), Cilt: 11 - Sayı: 2, 178–185. https://ajindex.com/articles/440555
Gocgun, Y., & Ghate, A. (2012). Lagrangian relaxation and constraint generation for allocation and advance scheduling. Computers & Operations Research, 39, 2323-2336
Parizi, M. S., & Ghate, A. (2016). Multi-class, multi-resource advance scheduling with noshows, cancellations and overbooking. Computers & Operations Research, 67, 90-101
Patrick, J., Puterman, M. L., & Queyranne, M. (2008). Dynamic multi-priority patient scheduling for a diagnostic resource. Operations Research, 56, 1507-1525
Saure, A., Patrick, J., Tyldesley, S., & Puterman, M. L. (2012). Dynamic multiappointment patient scheduling for radiation therapy. European Journal of Operational Research, 223, 573-584
Maxwell, M.S., Henderson, S. G., & Topaloglu, H. (2013). Tuning approximate dynamic programming policies for ambulance redeployment via direct search. Stochastic Systems, 3(2), 322-361
Gocgun, Y. (2018). Dynamic scheduling with cancellations: An application to chemotherapy appointment booking. An International Journal of Optimization and Control: Theories and Applications, 8, 2, 161-169
Powell, W. B. (2007). Approximate dynamic programming: solving the curses of dimensionality, Hoboken, New Jersey, USA: John Wiley and Sons
De Farias, D.P. & Roy, B.V. (2003). The linear programming approach to approximate dynamic programming. Operations Research, 51, 850-865
De Farias, D. P. & Roy, B. V. (2004). On constraint sampling in the linear programming approach to approximate dynamic programming. Mathematics of Operations Research, 29(3), 462–478
Shechter, S. M., Ghassemi, F., Gocgun, Y., & Puterman, M. L. (2015). Technical note – trading off quick versus slow actions in optimal search. Operations Research, 63(2), 353–362
Gocgun, Y. (2019). Approximate dynamic programming for optimal search with an obstacle. Selcuk University Journal of Engineering, Science, and Technology, 7, 80-95
Gocgun, Y., & Ghate, A. (2010). A Lagrangian approach to dynamic resource allocation. Proceedings of the Winter Simulation Conference, 3330-3338
Yin, J., Tang, T., Yang, L., Gao, Z., & Ran, B. (2016). Energy-efficient metro train rescheduling with uncertain time-variant passenger demands: an approximate dynamic programming approach. Transportation Research, Part B, 91, 178-210
Wang, Y., O’Donoghue, B., & Boyd, S. (2015). Approximate dynamic programming via iterated bellman inequalities. International Journal of Robust and Nonli