Operating theatre planning

N patients must be planned in an operating theatre over a medium term horizon (one or two weeks). This operating theatre is composed of several operating rooms and of one recovery room where several beds are available. Each patient needs a particular surgical procedure, which defines the human (surgeon) and material (equipment) resources to use and the intervention duration. Additive characteristics must be taken into account: hospitalisation date, intervention deadline, etc. The patient satisfaction and resource efficiency are sought. These two criteria are, respectively, modelled by hospitalisation costs, i.e. the patient stay duration, and the overtime costs, i.e. the resource overloads. We propose to solve this problem in two steps. First, an operating theatre planning is defined. It consists in assigning patients to operating rooms over the horizon. Second, each loaded operating room is scheduled individually in order to synchronise the various human and material resources used. This paper focuses on the first step, i.e. the operating theatre planning, which defines a general assignment problem, i.e. a NP hard problem. In order to solve heuristically this problem, an assignment model with resource capacity and time-window additive constraints is proposed. Integrating most of the constraints in the cost objective function, an extension of the Hungarian method has been developed to calculate the operating theatre planning. This primal-dual heuristic has been successfully experimented on a wide range of problem test data. (C) 2003 Elsevier Science B.V. All rights reserved.