Genetic Algorithm with the constraints for Nurse Scheduling Problem

Nurse Scheduling Problem (NSP) is the problem that allocating the shifts (day and night shifts, holidays, and so on) for nurses under various constraints. Generally, NSP has a lot of constraints. As a result, it needs a lot of knowledge and experience to make the scheduling table with its constraints, and it has been made by the head nurse or the authority in the hospitals. Some researches for NSP using Genetic Algorithm (GA) have been reported. The conventional methods take the constraints into the fitness function. However, if it reduces the fitness value a lot to the parts of solution against the constraints, it causes useless search, because most of chromosomes are selected in the initial population or in the change by the genetic operations. And if it doesn't reduce the fitness value so much, the final solution has some parts against the constraints. Some of them are established by the Labor Standards Act or the Labor Union Act, so the solution has to be modified. As a result, it is difficult to acquire an effective scheduling table automatically. This paper studies the method of coding and genetic operations with their constraints for NSP. The exchange of shifts is done to satisfy the constraints in the coding and after the genetic operations. We apply this method to the NSP using actual shifts and constraints being used in a hospital. It shows that an effective scheduling table satisfying the constraints is acquired by this method.