Abstract
Surgery is a significant cost driver in hospitals, and effective surgery planning is therefore critical to an efficient use of hospital resources. Surgery planning includes a variety of strategic, tactical and operational planning problems. In this paper, our focus is on operational surgery scheduling, which may be informally described as the task of assigning dates and times of surgery for each patient, while reserving capacity for these surgeries on a set of constrained physical resources. Such resources may, for example, be operating rooms, operation teams, surgeons, equipment, or post-operative bed capacity. Objectives are typically tardiness costs (overtime), hospitalisation costs, intervention costs, operating room utilisation, patient's waiting time, and patient or personnel preferences, among others. These scheduling problems are often NP-hard.The literature on surgery scheduling applications includes a range of exact and approximate solution methods. For realistic problem instances, and particularly where date assignment and surgery sequencing is combined, previous results indicate that meta-heuristic methods are the most promising. To the best of our knowledge, all meta-heuristic approaches to surgery scheduling have so far been sequential. In this paper we investigate some possibilities of using a massively parallel, «same program multiple data» (SPMD) meta-heuristic approach. We consider the first operational stage of surgery scheduling, which is the Surgery Admission Problem. This is the problem of assigning a date of surgery to each elective patient on a waiting list. The planning horizon can be anything from a few weeks to several months. The problem is described in more detail in section 2. The experiments are carried out on a Graphical Processing Unit (GPU). GPUs are affordable, easily available, and has high computational efficiency. Originally a highly specialized graphics processor, the GPU has over the last few years become a general purpose co