Heuristic Approaches for the Home Health Care Staff Scheduling Problem

Abstract

The increasing demand for community-based healthcare services requires efficient scheduling of caregivers to ensure high-quality, consistent care for clients while minimizing costs. This thesis addresses the challenge of creating optimal schedules for Personal Support Workers (PSWs) in supportive housing complexes, focusing on maximizing consistency for clients and reducing reliance on external staffing agencies. The problem is formulated as a Mixed Integer Linear Programming (MILP) model, incorporating specific objectives and constraints that assign PSWs to patient requests. Exact methods such as Branch and Bound (B&B) and Branch and Cut (B&C) were initially explored but, due to the complexity of the problem, these proved incapable of providing timely solutions. To overcome this, heuristic approaches, including Logic-Based Benders Decomposition and Lagrangian Relaxation were employed, where the solution process was stopped prematurely, effectively truncating the solution. As a case study, the proposed model is applied to Nucleus Independent Living (NIL), an organization based in Oakville, which aims to improve its scheduling practices for at-home and supportive housing services. The computational results demonstrate that Benders Decomposition outperforms Lagrangian Relaxation, achieving a solution within 0.2% of the best result obtained by the commercial solver GUROBI.