Real-time scheduling of semi-urgent patients under waiting time targets

Semi-urgent patients arrive at an emergency department and visit the physician after triage. Patients right after triage should be served within a maximum allowable waiting time; whereas in-process patients need to be served as soon as possible to avoid adverse events. The physician must determine which one to be served next. To deal with this problem, a Markov decision process (MDP) is proposed for real-time scheduling. The wait of patients right after triage incurs a non-decreasing marginal waiting cost in their lateness, whereas the wait of in-process patients incurs linear cost function. The objective is to minimise the total weighted waiting cost. The properties of the MDP model are analysed. In the special case of long examination time and common treatment rate for all patients, we prove the multimodularity of the value function and the optimality of state-dependent threshold policies. Based on these properties, efficient heuristic policies and an approximate dynamic programming (ADP) policy are proposed. A threshold policy, which is defined by the function of expected tardiness of patients right after triage, is found to excel in all experiments, with average gaps less than 0.7% from the optimal control in small-size instances and 0.18% from ADP in real application.