Efficient Solution Methods for Patient Assignment in Medical Day-care Units

Abstract

The increasing demand for outpatient cancer treatments has led to the widespread adoption of Medical Day-care Units (MDCUs), where efficient patient scheduling is essential for optimizing resource utilization and ensuring high-quality care. This thesis investigates the patient appointment scheduling problem in MDCUs, formulated as a resource-constrained parallel-machine multi-server job scheduling problem. The objective is to maximize clinic capacity (measured by the number of patients served) while maintaining operational feasibility and, in extended cases, minimizing patient waiting times. A series of mixed-integer linear programming (MILP) models are developed to address different variants of the problem. The first, a base model, explicitly represents each patient’s treatment and resource requirements. To improve scalability, a type-based model aggregates patients by treatment type, significantly reducing computational complexity while preserving scheduling accuracy. A genetic algorithm (GA) is then introduced as a metaheuristic approach for solving large-scale instances efficiently, complemented by a rolling horizon heuristic that dynamically updates solutions across overlapping planning periods. Finally, a deferral-penalized two-stage MILP is proposed for the extended problem: Stage 1 solves the type-based model to x optimal throughput capacity, and Stage 2 minimizes total waiting time subject to a deferral-penalty term controlled by a tunable coefficient that charges accumulated wait for every unscheduled patient, trading throughput against distributional fairness in patient denials. Simulation results on small, medium, and large problem instances (up to 1000 patients, 6 nurses, 5-day horizons) show that all four solution methods significantly outperform a FIFO baseline, as confirmed by one-sided Wilcoxon signed-rank tests at = 005. The type-based model consistently dominates the base MILP model in both solution quality and computational efficiency, and the genetic algorithm and rolling horizon heuristic yield near-optimal results for large-scale scenarios at substantially reduced runtimes. For the extended problem, a moderate penalty of 5 achieves meaningful distributional fairness, halving the concentration of denials among long-waiting patients relative to pure throughput maximization, without imposing the full rigidity of FIFO ordering. Overall, this research provides an integrated framework of exact and heuristic methods that enhance the efficiency, scalability, and fairness of patient scheduling in outpatient medical settings. Future work includes incorporating fatigue-aware nurse capacity constraints, stochastic programming extensions for patient no-shows and cancellations, and reinforcement learning or column-generation approaches for adaptive large-scale deployment.