Abstract
This study examines a patient scheduling problem with multiple appointment types and priority levels, where certain appointments must precede others and lead times play a crucial role. Although both factors significantly influence the quality of care-particularly when specialist assessments depend on timely diagnostic tests-they have been largely overlooked in existing healthcare scheduling models. To address this gap, we propose a dynamic scheduling model that explicitly incorporates appointment dependencies, lead times, and patient heterogeneity across multiple priority levels. The model reflects the real-world complexities of coordinating diagnostic and consult appointments in time-sensitive clinical settings. Using Approximate Dynamic Programming techniques, we develop an Approximate Optimal Policy (AOP) that efficiently allocates clinical resources, minimizes patient wait times, and ensures the availability of test results prior to consult appointments. We further derive a closed-form solution for the optimal approximation parameters, supported by a mathematical proof, which offers significant computational advantages. We evaluate the performance of the proposed AOP through simulation and compare it against a set of benchmark policies, including heuristics adapted from existing scheduling logic and current clinical practice. The solution is applied to a case study created based on data from a Stroke Prevention Clinic (SPC), where the complexity of care protocols and high demand present substantial scheduling challenges. The results demonstrate that the AOP consistently outperforms all benchmarks in terms of reducing wait times, ensuring timely diagnostic completion before consults, and meeting wait-time targets. We also introduce a practical, easy-to-implement heuristic called (MSP), which is derived from the AOP and designed for operational use. While simpler in structure, MSP performs comparably well and is well-suited for adoption in real healthcare settings due to its interpretability and minimal computational requirements. Finally, although the proposed approach is demonstrated in the context of an SPC, it has broader applicability to other areas such as cancer care, kidney transplant scheduling, and other complex care pathways involving interdependent appointments and prioritization.