Abstract

The Nurse Scheduling Problem (NSP) is a complex scheduling problem and involves a large set of constraints. Here we have incorporated the concept of Stable Marriage Problem (SMP) which has many practical applications, for example matching resident doctors to hospitals, students to colleges, or more generally to any two-sided market. In addition to the basic constraints the nurses will have their choice of shift preferences, and hospital also has own preference list of nurses on different shifts on each day. The original SMP requires all men and women to submit a complete and strictly ordered preference list - which is generally not practical, and rightly so, few relaxations have been proposed. In our problem we have allowed incomplete lists and ties –both relaxations at the same time. This enables a nurse to request only a subset of the shifts on a day and ties among preferences are also allowed. The objective is to build a high quality nurse roster satisfying all the hard constraints and minimizing the number of blocking pairs along with satisfying other soft constraints as much as possible. The problem is NP hard and we will show that Simulated Annealing incorporated with Tabu list and greedy probability has outperformed the basic Simulated Annealing in finding out near optimal solutions for real world nurse scheduling instances.