Operating rooms scheduling with a shared resource: a red-blue knapsack modeling approach

Federico Della Croce, DIGEP Politecnico di Torino, Italy (joint work with A. Grosso and V. T'kindt)

Abstract

We consider the problem of deriving a daily schedule for a set of operating rooms. In the problem, each operating room is associated to a surgical specialty and a set of surgical interventions is ready to be selected for the considered day. Each surgical intervention has a nominal duration and the overall intervention time in each operating room must not exceed the related operating room time availability.

In addition, a subset of the interventions requires the use of a shared resource among the operating rooms so that no two interventions using that shared resource can be processed simultaneously. We show that, if the number of machines is part of the input, then the problem is NP-hard in the strong sense by reduction from 3-Partition. We propose an exact approach based on a knapsack-like formulation of the problem capable of well solving in practice realistic instances of the considered problem.