Customized GRASP for rehabilitation therapy scheduling with appointment priorities and accounting for therapist satisfaction. (English) Zbl 07924480
Summary: Physical therapy in acute care hospitals plays an important role in the rehabilitation of patients. Nevertheless, the profession must deal with staff shortages caused by a lack of potential employees and absenteeism which are results of high physical and mental workloads. The therapist shortage negatively affects the total number of daily appointments the department can fulfill. For appointments that can be successfully scheduled, continuity of care with the same therapist cannot be guaranteed for individual patients. Lack of continuity of care negatively influences the therapist’s satisfaction. Therapist preferences for individual appointments in general cannot always be guaranteed when designing schedules, which also hurts satisfaction. This paper develops a multi-criteria model for the daily therapy appointment-scheduling problem. The primary objective is to minimize the total sum of priority violations for unscheduled appointments. To improve therapist satisfaction, we consider therapist preferences including continuity of care as a secondary objective. Here, our integer programming formulation aims to minimize the total sum of preference violations for scheduled appointments. We are dealing with an operational planning problem with a daily planning horizon. The operational objective is to achieve therapist schedules in at most two hours. The therapists’ schedules together need to include several hundred appointments for a planning day. Due to intractability, the developed integer program cannot provide schedules for such problem sizes. Therefore, we develop a customized Greedy Randomized Adaptive Search Procedure (GRASP) with six innovative local search operations to improve an initially constructed solution. We test the heuristic algorithm on realistic data instances. The metaheuristic provides high-quality schedules for various problem sizes in short runtimes, i.e., within minutes. Comparisons with the optimal solutions for small problem instances show very good results of the GRASP with a similar number of scheduled appointments and good adherence to continuity of care and therapist preference requirements.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C10 | Integer programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90B70 | Theory of organizations, manpower planning in operations research |
Keywords:
appointment scheduling; therapist planning; rehabilitation department in hospitals; GRASP heuristic; integer programmingReferences:
| [1] | Ahmadi-Javid, A.; Jalali, Z.; Klassen, KJ, Outpatient appointment systems in healthcare: a review of optimization studies, Eur J Oper Res, 258, 3-34, 2017 · Zbl 1380.90106 · doi:10.1016/j.ejor.2016.06.064 |
| [2] | Ait Haddadene, SR; Labadie, N.; Prodhon, C., A GRASP × ILS for the vehicle routing problem with time windows, synchronization and precedence constraints, Expert Syst Appl, 66, 274-294, 2016 · doi:10.1016/j.eswa.2016.09.002 |
| [3] | Beattie, P.; Dowda, M.; Turner, C.; Michener, L.; Nelson, R., Longitudinal continuity of care is associated with high patient satisfaction with physical therapy, Phys Ther, 85, 1046-1052, 2005 · doi:10.1093/ptj/85.10.1046 |
| [4] | Bowers, J.; Cheyne, H.; Mould, G.; Page, M., Continuity of care in community midwifery, Health Care Manag Sci, 18, 195-204, 2015 · doi:10.1007/s10729-014-9285-z |
| [5] | Bundesagentur für Arbeit (2022) Fachkräfteengpassanalyse 2021: Blickpunkt Arbeitsmarkt | Mai 2022. https://statistik.arbeitsagentur.de/DE/Navigation/Footer/Top-Produkte/Fachkraefteengpassanalyse-Nav.html. Accessed 14 Nov 2022 |
| [6] | Burke, EK; de Causmaecker, P.; Vanden Berghe, G.; van Landeghem, H., The state of the art of nurse rostering, J Sched, 7, 441-499, 2004 · Zbl 1154.90422 · doi:10.1023/B:JOSH.0000046076.75950.0b |
| [7] | Cappanera, P.; Scutellà, MG, Joint assignment, scheduling, and routing models to home care optimization: a pattern-based approach, Transp Sci, 49, 830-852, 2015 · doi:10.1287/trsc.2014.0548 |
| [8] | Cheang, B.; Li, H.; Lim, A.; Rodrigues, B., Nurse rostering problems-a bibliographic survey, Eur J Oper Res, 151, 447-460, 2003 · Zbl 1045.90027 · doi:10.1016/S0377-2217(03)00021-3 |
| [9] | Chien, C-F; Tseng, F-P; Chen, C-H, An evolutionary approach to rehabilitation patient scheduling: a case study, Eur J Oper Res, 189, 1234-1253, 2008 · Zbl 1146.90409 · doi:10.1016/j.ejor.2007.01.062 |
| [10] | Cissé, M.; Yalçındağ, S.; Kergosien, Y.; Şahin, E.; Lenté, C.; Matta, A., OR problems related to home health care: a review of relevant routing and scheduling problems, Oper Res Health Care, 13-14, 1-22, 2017 · doi:10.1016/j.orhc.2017.06.001 |
| [11] | Dohn, A.; Kolind, E.; Clausen, J., The manpower allocation problem with time windows and job-teaming constraints: a branch-and-price approach, Comput Oper Res, 36, 1145-1157, 2009 · Zbl 1162.90450 · doi:10.1016/j.cor.2007.12.011 |
| [12] | Erhard, M.; Schoenfelder, J.; Fügener, A.; Brunner, JO, State of the art in physician scheduling, Eur J Oper Res, 265, 1-18, 2018 · Zbl 1374.90002 · doi:10.1016/j.ejor.2017.06.037 |
| [13] | Feo, TA; Resende, MGC; Smith, SH, A greedy randomized adaptive search procedure for maximum independent set, Oper Res, 42, 860-878, 1994 · Zbl 0815.90121 · doi:10.1287/opre.42.5.860 |
| [14] | Fikar, C.; Hirsch, P., Home health care routing and scheduling: a review, Comput Oper Res, 77, 86-95, 2017 · Zbl 1391.90261 · doi:10.1016/j.cor.2016.07.019 |
| [15] | Gartner, D.; Frey, M.; Kolisch, R., Hospital-wide therapist scheduling and routing: Exact and heuristic methods, IISE Trans Healthc Syst Eng, 8, 268-279, 2018 · doi:10.1080/24725579.2018.1530314 |
| [16] | Girbig, M.; Freiberg, A.; Deckert, S.; Druschke, D.; Kopkow, C.; Nienhaus, A.; Seidler, A., Work-related exposures and disorders among physical therapists: experiences and beliefs of professional representatives assessed using a qualitative approach, J Occup Med Toxicol, 12, 1-9, 2017 · doi:10.1186/s12995-016-0147-0 |
| [17] | Griffith, JD; Williams, JE; Wood, RM, Scheduling physiotherapy treatment in an inpatient setting, Oper Res Health Care, 1, 65-72, 2012 · doi:10.1016/j.orhc.2012.08.001 |
| [18] | Gupta, D.; Denton, B., Appointment scheduling in health care: challenges and opportunities, IIE Trans, 40, 800-819, 2008 · doi:10.1080/07408170802165880 |
| [19] | Gurobi Optimization LLC (2022) Gurobi optimizer reference manual. https://www.gurobi.com |
| [20] | Huynh, N-T; Huang, Y-C; Chien, C-F, A hybrid genetic algorithm with 2D encoding for the scheduling of rehabilitation patients, Comput Ind Eng, 125, 221-231, 2018 · doi:10.1016/j.cie.2018.08.030 |
| [21] | Jungwirth, A.; Desaulniers, G.; Frey, M.; Kolisch, R., Exact branch-price-and-cut for a hospital therapist scheduling problem with flexible service locations and time-dependent location capacity, INFORMS J Comput, 2021 · Zbl 1492.90056 · doi:10.1287/ijoc.2021.1119 |
| [22] | Kontoravdis, G.; Bard, J., A GRASP for the vehicle routing problem with time windows, ORSA J Comput, 7, 10-23, 1995 · Zbl 0822.90055 · doi:10.1287/ijoc.7.1.10 |
| [23] | Kuiper, A.; Lee, RH, Appointment scheduling for multiple servers, Manag Sci, 68, 7422-7440, 2022 · doi:10.1287/mnsc.2021.4221 |
| [24] | Lau, B.; Skinner, EH; Lo, K.; Bearman, M., Experiences of physical therapists working in the acute hospital setting: systematic review, Phys Ther, 96, 1317-1332, 2016 · doi:10.2522/ptj.20150261 |
| [25] | Nickel, S.; Schröder, M.; Steeg, J., Mid-term and short-term planning support for home health care services, Eur J Oper Res, 219, 574-587, 2012 · Zbl 1253.90152 · doi:10.1016/j.ejor.2011.10.042 |
| [26] | Olaleye, OA; Hamzat, TK; Akinrinsade, MA, Satisfaction of Nigerian stroke survivors with outpatient physiotherapy care, Physiother Theory Pract, 33, 41-51, 2017 · doi:10.1016/j.pmrj.2010.06.015 |
| [27] | Ogulata, SN; Koyuncu, M.; Karaskas, E., Personnel and patient scheduling in the high demanded hospital services: a case study in the physiotherapy service, J Med Syst, 32, 221-228, 2008 · doi:10.1007/s10916-007-9126-4 |
| [28] | Pinedo, M., Scheduling: theory, algorithms, and systems, 2016, Cham, Heidelberg, New York, Dordrecht, London: Springer, Cham, Heidelberg, New York, Dordrecht, London · Zbl 1332.90002 · doi:10.1007/978-3-319-26580-3 |
| [29] | Podgorelec, V.; Kokol, P., Genetic algorithm based system for patient scheduling in highly constrained situations, J Med Syst, 21, 417-427, 1997 · doi:10.1023/A:1022828414460 |
| [30] | Rasmussen, MS; Justesen, T.; Dohn, A.; Larsen, J., The home care crew scheduling problem: preference-based visit clustering and temporal dependencies, Eur J Oper Res, 219, 598-610, 2012 · Zbl 1253.90154 · doi:10.1016/j.ejor.2011.10.048 |
| [31] | Rojanasoonthon, S.; Bard, J., A GRASP for parallel machine scheduling with time windows, INFORMS J Comput, 17, 32-51, 2005 · Zbl 1239.90052 · doi:10.1287/ijoc.1030.0048 |
| [32] | Schimmelpfeng, K.; Helber, S.; Kasper, S., Decision support for rehabilitation hospital scheduling, Or Spectrum, 34, 461-489, 2012 · Zbl 1239.90068 · doi:10.1007/s00291-011-0273-0 |
| [33] | Song, H.; Tucker, AL; Murrell, KL, The diseconomies of queue pooling: an empirical investigation of emergency department length of stay, Manage Sci, 61, 3032-3053, 2015 · doi:10.1287/mnsc.2014.2118 |
| [34] | van Dijk, N.; van der Sluis, E., To pool or not to pool in call centers, Prod Oper Manag, 17, 296-305, 2008 · doi:10.3401/poms.1080.0029 |
| [35] | van Dijk, N.; van der Sluis, E., Pooling is not the answer, Eur J Oper Res, 197, 415-421, 2009 · Zbl 1157.90369 · doi:10.1016/j.ejor.2008.06.014 |
| [36] | Verband der Ersatzkassen (2022) Rahmenverträge. https://www.vdek.com/vertragspartner/heilmittel/rahmenvertrag.html. Accessed 12 Apr 2022 |
| [37] | van Walraven, C.; Oake, N.; Jennings, A.; Forster, AJ, The association between continuity of care and outcomes: a systematic and critical review, J Eval Clin Pract, 16, 947-956, 2010 · doi:10.1111/j.1365-2753.2009.01235.x |
| [38] | Wichmann, MG; Volling, T.; Spengler, TS, A GRASP heuristic for slab scheduling at continuous casters, Or Spectr, 36, 693-722, 2014 · Zbl 1305.90422 · doi:10.1007/s00291-013-0330-y |
| [39] | Wirnitzer, J.; Heckmann, I.; Meyer, A.; Nickel, S., Patient-based nurse rostering in home care, Oper Res Health Care, 8, 91-102, 2016 · doi:10.1016/j.orhc.2015.08.005 |
| [40] | Zhao, L.; Chien, C-F; Gen, M., A bi-objective genetic algorithm for intelligent rehabilitation scheduling considering therapy precedence constraints, J Intell Manuf, 29, 973-988, 2018 · doi:10.1007/s10845-015-1149-y |
| [41] | Zimbelman, JL; Juraschek, SP; Zhang, X.; Lin, VW-H, Physical therapy workforce in the United States: forecasting nationwide shortages, PM R, 2, 1021-1029, 2010 · doi:10.1016/j.pmrj.2010.06.015 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
