Abstract
Chemotherapy outpatient scheduling is a complex, dynamic, uncertain problem. Chemotherapy centres are facing increasing demands and they need to increase their efficiency; however there are very few studies looking at using optimization technology on the chemotherapy scheduling problem. We address dynamic uncertainty that arises from requests for appointments that arrive in real time and uncertainty due to last minute scheduling changes. We propose dynamic template scheduling, a novel technique that combines proactive and online optimization and we apply it to the chemotherapy outpatient scheduling problem. We create a proactive template of an expected day in the chemotherapy centre using a deterministic optimization model and a sample of appointments. As requests for appointments arrive, we use the template to schedule them. When a request arrives that does not fit the template, we update the template online using the optimization model and a revised set of appointments. To accommodate last minute additions and cancellations to the schedule, we propose a shuffling algorithm that moves appointment start times within a predefined time limit. We test the use of dynamic template scheduling against the optimal offline solution and the actual performance of the cancer centre. We find improvements in makespan of up to 20 % when using dynamic template scheduling compared to current practice.
Similar content being viewed by others
References
Canadian Institute for Health Information (2012) Wait times in Canada—a summary. Available online at: https://secure.cihi.ca/estore/productFamily.htm?pf=PFC1723
The Canadian Press (2008) Wait times for chemo still long despite more investment: Ontario report. CBC News. Available at: http://www.cbc.ca/health/story/2008/05/08/chemo-report.html. Accessed 5 July 2013
Cayirli T, Veral E (2003) Outpatient scheduling in health care: a review of literature. Prod Oper Manag 12(4):519
Erdogan SA, Denton B (2011) Dynamic appointment scheduling of a stochastic server with uncertain demand. Informs J Comput, Articles in Advance 1–17
Muthuraman K, Lawley M (2008) A stochastic overbooking model for outpatient clinical scheduling with no-shows. IIE Trans 40:820–837
Vissers J, Wijngaard J (1979) The outpatient appointment system: design of a simulation study. Eur J Oper Res 3:459–463
Cayirli T, Veral E, Rosen H (2006) Designing appointment scheduling systems for ambulatory care services. Health Care Manag Sci 9:47–58
Santibanez P, Aristizabal R, Puterman M, Chow VS, Huang W, Kollmannsberger C, Nordin T, Runzer N, Tyldesley S (2012) Operations research methods improve chemotherapy patient appointment scheduling. Jt Comm J Qual Patient Saf 38(12):541–553
Turkcan A, Zeng B, Lawley M (2012) Chemotherapy operations planning and scheduling. IIE Trans Health Care Syst Eng 2(1):31–49
Herroelen W, Leus R (2001) On the merits and pitfalls of critical chain scheduling. J Oper Manag 19:559–577
Mohring RH, Stork F (2000) Linear preselective policies for stochastic project scheduling. Math Meth Oper Res 52:501–515
Lambrechts O, Demeulemeester E, Herroelen W (2008) Proactive and reactive strategies for resource-constrained project scheduling with uncertain resource availabilities. J Sched 11(2):121–136
Billaut JC, Roubellat F (1996) A new method for workshop real time scheduling. Int J Prod Res 34(6):1555–1579
Daniels RL, Carrillo JE (1997) b-Robust scheduling for single-machine systems with uncertain processing times. IIE Trans 29:977–985
Kouvelis P, Daniels RL, Vairaktarakis G (2000) Robust scheduling of a two-machine flow shop with uncertain processing times. IIE Trans 32:421–432
Mehta SV, Uzsoy RM (1998) Predictable scheduling of a job shop subject to breakdowns. IEEE Trans Robot Autom 14(3):365–378
Van Hentenryck P, Bent R (2006) Online stochastic combinatorial optimization. MIT Press, Cambridge
Ouelhadj D, Petrovic S (2009) A survey of dynamic scheduling in manufacturing systems. J Sched 12(4):417–431
Bidot J, Vidal T, Laborie P, Beck JC (2009) A theoretic and practical framework for scheduling in a stochastic environment. J Sched 12(3):315–344
Davenport AJ, Beck JC (1999) A survey of techniques for scheduling with uncertainty. Unpublished manuscript
Davenport AJ, Gefflot C, Beck JC (2001) Slack-based techniques for robust schedules. In the Proceedings of the Sixth European Conf. Planning 7–18
Wu CW, Brown KN, Beck JC (2009) Scheduling with uncertain durations: modelling beta-robust scheduling with constraints. Comput Oper Res 36(8):2348–2356
Borodin A, El-Yaniv R (1998) Online computation and competitive analysis. Cambridge University Press, New York
Van Hentenryck P, Bent R, Mercier L, Vergados Y (2009) Online stochastic reservation systems. Ann Oper Res 171(1):101–126
Li Z, Ierapetritou M (2008) Reactive scheduling using parametric programming. Am Inst Chem Eng J 54(10):2610–2623
O’Donovan R, McKay KN, Uzsoy R (1999) Predictable scheduling on a single machine with machine breakdowns and sensitive jobs. Int J Prod Res 37:4217–4233
Rossi F, van Beek P, Walsh T (2006) Constraint programming. Chapter 1. Elsevier
Beldiceanu N, Demassey S (2010) Global constraint catalogue. http://www.emn.fr/z-info/sdemasse/gccat/. Accessed 31 October 2011
Bartak R, Salido M, Rossi F (2010) Constraint satisfaction techniques in planning and scheduling. J Intell Manuf 21:5–15
Beck JC, Fox MS (1998) A generic framework for constraint-directed search and scheduling. AI Mag 19(4):103–132
Van Hentenryck P (2008) Comet CP tutorial. UCL
Pinedo ML (2012) Scheduling: Theory, algorithms, and systems, 4th Edition. Springer
Hahn-Goldberg S (2014) Dynamic optimization addressing chemotherapy outpatient scheduling. PhD Thesis. University of Toronto, Toronto
Siegel (1956) Nonparametric statistics for the behavioural sciences. McGraw-Hill, New York
Acknowledgements
The authors would like to acknowledge the financial support provided by a Mitacs Accelerate grant, Bykart Software, and the Odette Cancer Centre.
Author information
Authors and Affiliations
Corresponding author
Additional information
A portion of this research was presented at the IIE SHS conference in February 2012, where it won the graduate student paper prize and appears in their non-published proceedings as:
Hahn-Goldberg S, Carter MW, Beck JC. Dynamic Template Scheduling To Address Uncertainty in Complex Scheduling Problems: A Case Study on Chemotherapy Outpatient Scheduling. It can be downloaded from IIEnet2.org
Rights and permissions
About this article
Cite this article
Hahn-Goldberg, S., Carter, M.W., Beck, J.C. et al. Dynamic optimization of chemotherapy outpatient scheduling with uncertainty. Health Care Manag Sci 17, 379–392 (2014). https://doi.org/10.1007/s10729-014-9268-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10729-014-9268-0