Effective operators using parallel processing for nurse scheduling by cooperative genetic algorithm

This paper proposes effective operators for cooperative genetic algorithm (CGA) to be applied to a practical nurse scheduling problem. The nurse scheduling is a very complex task. In the real hospital, the change of the schedule occurs frequently. This paper describes a technique to reoptimise such nurse schedule. CGA is superior in ability for local search, but often stagnates at the unfavourable situation because it is inferior in ability for global search. To improve this problem, we have proposed a mutation operator depending on the optimisation speed. The mutation yields small changes into the population. Then the population is able to escape from a local minimum area. However, this operator has two parameters to define itself. Therefore, we have proposed periodic mutation operator which has only one parameter. In the case which contains such changes, a more powerful operator is necessary. We propose a multi-branched mutation (MBM) operator. MBM provides natural concurrency. Therefore, we have implemented parallel processing of MBM. In many cases, when the optimisation converges on an unfavourable penalty value in the early stage of the optimisation, the final population is also unfavourable. Therefore, we propose a technique of multiplied initial populations (MIP).