Surgical scheduling under uncertainty by approximate dynamic programming

Surgical scheduling consists of selecting surgeries to be performed within a day, while jointly assigning operating rooms, starting times and the required resources. Patients can be elective or emergency/urgent. The scheduling of surgeries in an operating theatre with common resources to emergency or urgent and elective cases is highly subject to uncertainties not only on the duration of an intervention but mainly on the arrival of emergency or urgent cases. At the beginning of the day we are given a candidate set of elective surgeries with and an expected duration and a time window the surgery must start, but the expected duration and the time window of an emergency or urgent case become known when the surgery arrives. The day is divided into decision stages. Due to the dynamic nature of the problem, at the beginning of each stage the planner can make decisions taking into account the new information available. Decisions can be to schedule arriving surgeries, and to reschedule or cancel surgeries not started yet. The objective is to minimize the total expected cost composed of terms related to refusing arriving surgeries, to canceling scheduled surgeries, and to starting surgeries out of their time window. We address the problem with an approximate dynamic programming approach embedding an integer programming formulation to support decision making. We propose a dynamic model and an approximate policy iteration algorithm making use of basis functions to capture the impact of decisions to the future stages. Computational experiments have shown with statistical significance that the proposed algorithm outperforms a lookahead reoptimization approach.