• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

J4 ›› 2013, Vol. 35 ›› Issue (5): 149-153.

• 论文 • Previous Articles     Next Articles

Genetic algorithm with variable neighborhood search
to solve nurse rostering problem         

HU Lianmin1,2,ZHANG Jiuhua1,CHANG Yongyun3,HUANG Han3   

  1. (1.Department of Physics and Electrical Engineering,Leshan Teachers College,Leshan 614000;
    2.School of Computer Science and Engineering,South China University of Technology,Guangzhou 510006;
    3.School of Software Engineering,South China University of Technology,Guangzhou 510006,China)
  • Received:2012-05-03 Revised:2012-08-16 Online:2013-05-25 Published:2013-05-25

Abstract:

Nurse rostering problem is one of multiconstrained problems with many traps. Therefore neither traditional approaches nor heuristic methods can find the optimal solution for the problem. This paper studied and solved the nurse rostering problem by applying a hybrid method that combines genetic algorithm (GA) and variable neighborhood search (VNS). In this method, GA generates a new nurse roster by adding judgment rules and control policies. VNS algorithm operates on the steps of initialization, crossover and mutation with constraints, and separation of solution space. Finally, the experiment results of 20 nurse rostering problems indicate that, within the same runtime, the method of GA+VNS outperforms the method of IP+VNS which is internationally known as the newest approach.

Key words: nurse rostering problem;genetic algorithm;variable neighborhood search