Performance comparison of approximate dynamic programming techniques for dynamic stochastic scheduling

Yasin Göçgün

doi:10.11121/ijocta.01.2021.00987

Authors

Yasin Göçgün Istinye University https://orcid.org/0000-0003-3005-7596

DOI:

https://doi.org/10.11121/ijocta.01.2021.00987

Keywords:

dynamic stochastic advanced scheduling, approximate dynamic programming

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.

Downloads

Download data is not yet available.

Author Biography

Yasin Göçgün, Istinye University

Dr. Gocgun received his B.S. degree and M.S. degree from the Industrial Engineering Department at Bilkent University in 2003 and 2005, respectively. After completing his doctoral studies in the Industrial and Systems Engineering Department at the University of Washington in 2010, Dr. Gocgun worked as a postdoctoral fellow in the Sauder School of Business at the University of British Columbia between 2010 and 2012. After his first post-doc, Dr. Gocgun carried out another post-doc study in the Mechanical and Industrial Engineering Department at the University of Toronto between 2012 and 2014. Prior to joining the Industrial Engineering Department at İstinye University, Dr. Gocgun worked as an assistant professor in the Industrial Engineering Department at Altınbaş University between 2014 and 2020. His research interests primarily focus on dynamic stochastic optimization, operations research in healthcare, Markov decision processes, approximate dynamic programming, and scheduling. Dr. Gocgun’s research studies were published in journals such as Computers and Operations Research, European Journal of Operational Research and Healthcare Management Science.

References

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 Nonlinear Control, 25, 1472–1496.

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.

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.

Yang, X., He, H., & Zhong, X. (2019). Approximate dynamic programming for nonlinear-constrained optimizations. IEEE Transactions on Cybernetics.

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.

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.

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.

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.

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.

Lu, Y., Xie, X., & Jiang, Z. (2018). Dynamic appointment scheduling with wait-dependent abandonment. European Journal of Operational Research, 265(3), 75-984.

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.

Gocgun, Y. (2010). Approximate dynamic programming for dynamic stochastic resource allocation with applications to healthcare. PhD Thesis. The University of Washington.