Performance comparison of approximate dynamic programming techniques for dynamic stochastic scheduling

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.

PDF

___

[1] Gocgun, Y., & Ghate, A. (2012). Lagrangian relaxation and constraint generation for allocation and advance scheduling. Computers & Operations Research, 39, 2323-2336.
[2] Parizi, M. S., & Ghate, A. (2016). Multi-class, multi-resource advance scheduling with noshows, cancellations and overbooking. Computers & Operations Research, 67, 90-101.
[3] Patrick, J., Puterman, M. L., & Queyranne, M. (2008). Dynamic multi-priority patient scheduling for a diagnostic resource. Operations Research, 56, 1507-1525.
[4] 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.
[5] 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.
[6] 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.
[7] Powell, W. B. (2007). Approximate dynamic programming: solving the curses of dimensionality, Hoboken, New Jersey, USA: John Wiley and Sons.
[8] De Farias, D.P. & Roy, B.V. (2003). The linear programming approach to approximate dynamic programming. Operations Research, 51, 850-865.
[9] 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.
[10] 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.
[11] Gocgun, Y. (2019). Approximate dynamic programming for optimal search with an obstacle. Selcuk University Journal of Engineering, Science, and Technology, 7, 80-95.
[12] Gocgun, Y., & Ghate, A. (2010). A Lagrangian approach to dynamic resource allocation. Proceedings of the Winter Simulation Conference, 3330-3338.
[13] 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.
[14] Wang, Y., O’Donoghue, B., & Boyd, S. (2015). Approximate dynamic programming via iterated bellman inequalities. International Journal of Robust and Nonlinear Control, 25, 1472–1496.
[15] Li, H., & Womer, N. K. (2015). Solving stochastic resource-constrained project scheduling problems by closed-loop approximate dynamic programming. European Journal of Operational Research, 246, 20-33 2015.
[16] Nozhati, S., Sarkale, Y., Ellingwood, B., Chong, E. K. P., & Mahmoud, H. (2019). Near-optimal planning using approximate dynamic programming to enhance post-hazard community resilience management. Reliability Engineering and System Safety, 181, 116-126.
[17] Yang, X., He, H., & Zhong, X. (2019). Approximate dynamic programming for nonlinear-constrained optimizations. IEEE Transactions on Cybernetics.
[18] Al-Kanj, L., Nascimento, J., & Powell, W. B. (2020). Approximate dynamic programming for planning a ride-sharing system using autonomous fleets of electric vehicles. European Journal of Operational Research, 284, 1088- 1106.
[19] Ou, X., Chang, Q., & Chakraborty, N. (2021). A method integrating Q-Learning with approximate dynamic programming for gantry work cell scheduling. IEEE Transactions on Automation Science and Engineering, 18, 1, 85-93.
[20] Gocgun, Y., & Puterman, M. L. (2014). Dynamic scheduling with due dates and time windows: an application to chemotherapy patient appointment booking. Health Care Management Science, 17, 60-76.
[21] Akhavizadegan, F., Ansarifar, J., & Jolai, F. (2017). A novel approach to determine a tactical and operational decision for dynamic appointment scheduling at nuclear medical center. Computers & Operations Research, 78, 267–277.
[22] Wang, J., Fung, R.Y., & Chan, H.K. (2015). Dynamic appointment scheduling with patient preferences and choices. Industrial Management & Data Systems, 115(4), 700-717.
[23] Lu, Y., Xie, X., & Jiang, Z. (2018). Dynamic appointment scheduling with wait-dependent abandonment. European Journal of Operational Research, 265(3), 75-984.
[24] Saure, A., Begen, M.A. & Patrick, J. (2020). Dynamic multi-priority, multi-class patient scheduling with stochastic service times. European Journal of Operational Research, 280(1), 254–265.
[25] Gocgun, Y. (2010). Approximate dynamic programming for dynamic stochastic resource allocation with applications to healthcare. PhD Thesis. The University of Washington.