Rehabilitation therapy scheduling accounting for teaming requirements and therapist shortages: a branch and price approach

Abstract Physical therapy in acute care hospitals plays an important role for the rehabilitation of patients. Nevertheless, the profession must deal with staff shortages caused by a lack of qualified employees and stress-induced absenteeism. Both are results of high physical and mental workloads as well as a lack of employee retention strategies. A therapist shortage negatively affects the total number of appointments the department can fulfill daily. Furthermore, severe cases where patients require two therapists at the same time are common in acute care hospitals and contribute to the scheduling complexity. Here, one therapist takes charge of the appointment (lead), while a second therapist fulfills a support function role. This paper develops a multi-criteria optimization model for the daily rehabilitation therapy scheduling problem subject to teaming aspects and appointment priorities. We minimize preference penalties for lead and support visits and the total priority-based violation for unscheduled appointments. The problem is modeled as a vehicle routing problem with time windows and synchronization constraints. We solve the problem using a branch-and-price approach with different visit clustering methods and speed-up techniques. Computational results show the effectiveness of a randomized greedy heuristic implemented to enhance performance for generating new columns. Besides, a problem-specific clustering approach is integrated to speed up subproblems’ solution times. Our results show its high effectiveness when compared to a state-of-the-art approach derived from literature.