Modelling and solving generalised operational surgery scheduling problems

The term 'surgery scheduling' is used to describe a variety of strategic, tactical and operational scheduling problems, many of which are critical to the quality of treatment and to the efficient use of hospital resources. We consider operational surgery scheduling problems. The exact problem formulation varies substantially between hospitals or, even, hospital departments. In addition, the level of detail varies between different planning situations, ranging from long term patient admission planning to the very detailed scheduling of a particular day's surgeries. This diversity makes it difficult to design general scheduling methods and software solutions that can be applied without extensive customisation for each application. We approach this challenge by proposing a new generalised model for surgery scheduling problems. We show how this model extends the multi-project, multi-mode resource constrained project scheduling problem with generalised time constraints, including some extensions that to our knowledge have not been previously studied. Furthermore, we present a search method for solving the proposed model. The algorithm uses on-line learning to balance computational loads between a construction and an improvement method, both working on high level solution representations. An adapted schedule generation scheme is used to map these to concrete schedules. We perform computational experiments using realistic problem instances from three surgery scheduling planning situations at a medium sized Norwegian hospital; day scheduling, week scheduling and admission planning. The results show that the algorithm performs well across these quite different problems without any off-line customisation or parameter tuning.