Dynamic scheduling with cancellations: an application to chemotherapy appointment booking

Yasin Göçgün


We study a dynamic scheduling problem that has the feature of due dates and time windows. This problem arises in chemotherapy scheduling where patients from different types have specific target dates along with time windows for appointment. We consider cancellation of appointments. The problem is modeled as a Markov Decision Process (MDP) and approximately solved using a direct-search based approximate dynamic programming (ADP) tehnique. We compare the performance of the ADP technique against the myopic policy under diverse scenarios. Our computational results reveal that the ADP technique outperforms the myopic policy on majority of problem sets we generated.


Dynamic scheduling; Markov decision processes; Approximate dynamic programming

Full Text:



Gocgun, Y., & Puterman, M. L. (2014). Dynamic scheduling with due dates and time windows: an application to chemotherapy patient appointment booking. Health Care Manag Sci., 17, 60-76.

Green, L. V., Savin, S., & Wang, B. (2006). Managing Patient Service in a Diagnostic Medical Facility. Operations Research, 54, 11-25.

Cardoen, B., Demeulemeester, E., & Belien, J. (2010). Operating room planning and scheduling: A literature review. European Journal of Operational Research, 201, 921-932.

Hulshof, P., Kortbeek, N., Boucherie, R., Hans, E., & Bakker, P. (2012). Taxonomic classification of planning decisions in health care: a structured review of the state of the art in OR/MS. Health Systems, 1, 129-175.

Gocgun, Y., Bresnahan, B., Ghate, A., & Gunn, M. (2011). A markov decision process approach to multi-category patient scheduling in a diagnostic facility. Artificial Intelligence in Medicine, 53, 73-81.

Kolisch,R., & Sickinger, S. (2008). Providing radiology health care services to stochastic demand of different customer classes. OR Spectrum, 30, 375-395.

Min, D., & Yih, Y. (2010). An elective surgery scheduling problem considering patient priority. Computers and Operations Research, 37, 1091-1099.

Patrick, J., Puterman, M. L., & Queyranne, M. (2008). Dynamic multi-priority patient scheduling for a diagnostic resource. Operations Research, 56, 1507-1525.

Lamiri M., Xie X., Dolgui, A., & Grimaud, F. (2008). A stochastic model for operating room planning with elective and emergency demand for surgery. European Journal of Operational Research, 185, 1026-1037. Dynamic scheduling with cancellations: an application to chemotherapy appointment booking 169

Liu, N., Ziya, S. & Kulkarni, V. G. (2010). Dynamic scheduling of outpatient appointments under patient no-shows and cancellation. Manufacturing and Service Operations Management, 12, 347-364.

Saure, A., Patrick J., Tyldesley, S., & Puterman, M.L. (2012). Dynamic multi-appointment patient scheduling for radiation therapy. European Journal of Operational Research, 223, 573-584.

Geng, N., & Xiaolan, X. (2016). Optimal dynamic outpatient scheduling for a diagnostic facility with two waiting time targets. IEEE Transactions on Automatic Control, 61, 3725-3739.

Tsai, P. J., & Teng, G. (2014). A stochastic appointment scheduling system on multiple resources with dynamic call-in sequence and patient no-shows for an outpatient clinic. European Journal of Operational Research, 239, 427-436.

Turkcan, A., Zeng, B., & Lawley, M. (2012). Chemotherapy operations planning and scheduling. IIE Transactions on Healthcare Systems Engineering, 2, 31-49.

Goldberg, S., Carter, M., Beck, J., Trudeau, M., Sousa, P., & Beattie, K. (2014). Dynamic optimization of chemotherapy outpatient scheduling with uncertainty. Healthcare Management Science, 17, 379-392.

Goldberg, S., Beck, J., Carter, M., Trudeau, M., Sousa, P., & Beattie, K. (2014). Solving the chemotherapy outpatient scheduling problem with constraint programming. Journal of Applied Operational Research, 6, 135-144.

Alvarado, M. & Ntaimo, L. (2018). Chemotherapy appointment scheduling under uncertainty using meanrisk stochastic integer programming. Healthcare Management Science, 21, 87-104.

Parizi, M. S., & Ghate, A. (2016). Multi-class, multiresource advance scheduling with no-shows, cancellations and overbooking. Computers Operations Research, 67, 90-101.

Kleywegt, A. J., & Papastavrou, J. D. (1998). The Dynamic and Stochastic Knapsack Problem. Operations Research, 46, 17-35.

Powell W. B. (2007). Approximate Dynamic Programming: Solving the curses of dimensionality. John Wiley and Sons.

Adelman, D. (2003). Price-directed replenishment of subsets: methodology and its application to inventory routing. Manufacturing and Service Operations Management, 5, 348-371.

Adelman, D. (2004). A price-directed approach to stochastic inventory routing. Operations Research, 52, 499-514.

De Farias, D. P., & Roy, B. V. (2004). The linear programming approach to Approximate Dynamic Programming. Operations Research, 51, 850-865.

Bertsekas, D., & Tsitsiklis, J. (1996). Neuro-Dynamic Programming. Athena Scientific.

Sutton, R. S. & Barto, A. G. (1998). Reinforcement Learning. MIT Press.

Chang, H. S., Fu, M. C., Hu, J., & Marcus, S. I. (2007). Simulation-based algorithms for Markov Decision Processes. Springer.

Gocgun, Y. (2018). Approximate dynamic programming for optimal search with an obstacle (Submitted).

Maxwell, M. S., Henderson, S. G., & Topaloglu, H. (2013). Tuning Approximate Dynamic Programming Policies for Ambulance Redeployment via Direct Search. Stochastic Systems, 3, 1-40.

DOI: http://dx.doi.org/10.11121/ijocta.01.2018.00469


  • There are currently no refbacks.

Copyright (c) 2018 Yasin Göçgün

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.


   ithe_170     crossref_284         ind_131_43_x_117_117  Scopus  EBSCO_Host    ULAKBIM   PROQUEST   ZBMATH more...