A decomposition-based approach for multi-level appointment planning and scheduling

We study the scheduling of appointments for population-based breast cancer screening, considering different patient types in view of their stochastic no-show behaviour and service duration. The associated multi-level problem under study comprises both tactical planning decisions, assigning patients in advance to a mammography machine at a dispersed unit and appointment day, and operational scheduling decisions, stipulating the appointment time for patients. To mitigate the impact of operational variability, performance is safeguarded by optimising the minimum performance associated with defined chance constraints relative to the minimum number of performed screenings and the maximum patient wait time, resource idle time and overtime. We develop a decomposition method that iterates between tactical and operational decision levels with feedback loops. The tactical problem is reformulated as a deterministic mixed-integer quadratic-constrained programming problem and solved via a heuristic that defines a promising solution region based on problem-specific estimates. The operational problem is solved via Sample Average Approximation and decomposition of patient sequencing and appointment time assignment decisions. Computational results show that the developed decomposition-based procedure with feedback and the phase-specific methodologies are superior in terms of time and solution quality compared to alternative methods.