An implementor-adversary approach for uncertain and time-correlated service times in the nurse-to-patient assignment problem

Parameter uncertainty is common to several optimization problems, especially in health care where patients’ conditions and service times are highly uncertain. Moreover, in Home Health Care services, where patients are treated over a long time horizon, their clinical condition may change and result in uncertain but also highly time-correlated service times. To include time-correlated uncertain parameters is a difficult task in robust optimization. It has been only marginally addressed, especially in the health care management literature. In this paper, we address the nurse-to-patient assignment problem in Home Health Care services under three types of continuity of care, focusing on uncertain and time-correlated service times. In the literature, this problem has been tackled with stochastic programming, robust optimization, and heuristics; however, service times at different time periods have been treated as independent so far. We propose a robust assignment model that accounts for the time-dependency of patients’ service times, with either constant or increasing overtime cost, and an approach based on the implementor-adversary framework to solve it. Service times are modeled as stochastic parameters and time-correlation is included by limiting the difference in the service time requested by the same patient in two consecutive time periods. The goals are to minimize the cost of staff overtime and the number of reassignments that impair patients’ continuity of care. Results from a relevant realistic case show that the approach does not always converge, but the robust solutions provided, under suitable parameters for the uncertainty description, always outperform the deterministic ones even without full convergence.