A SAT approach for solving the nurse scheduling problem

Nurse scheduling problem (NSP) represents a subclass of constraint satisfaction problems (CSP), involving a set of constraints. The problem is highly constrained and difficult to solve. The goal is to find high quality shift assignments to nurses satisfying constraints related to labor contract rules, requirements of nurses as well as the employers in health-care institutions. The constraints are classified as hard and soft, depending on their importance. In this paper, a real case of a cyclic nurse rostering problem is introduced. dasiaCyclicpsila means that the generated roster can be repeated indefinitely if no further constraint is introduced. In earlier investigation we saw that simulated annealing performed better than other local search techniques. In this paper we have converted NSP to a satisfiability problem(SAT) and applied GSAT to solve it. We show that GSAT incorporated with a tabu list has outperformed other methods, like, simulated annealing and genetic algorithm in almost all instances.