求解多场景护士分配问题的扰动变异遗传算法

Algorithmic solution for nurse assignment problem based on GA with perturb mutation

针对当前经典的护士排班问题中的一个重要分支——护士分配问题,分析了病人护理等级的特点、护士和病人的配合关系、护士技术职称等方面对护士的工作负荷的影响,建立了一个改进的随机规划模型,使模型更符合中国医院的情况。然后根据问题解的结构,设计了一个扰动变异遗传算法,在解内部的每一个向量以一定概率添加扰动实现变异。实验结果显示,与最新的随机贪心算法、基于Bender's分解的启发式算法对比,扰动变异遗传算法能在30 min内得到更高质量的解,为护士每班次减少超过8.9%的工作负荷。特别地,在求解多场景、多约束,而且解的优势并非块状连续的护士分配问题中,扰动变异遗传算法优势更加明显。

Focusing on nurse assignment problem,this paper firstly analyzed nurse assignment problem in aspects of patient-nurse relations,nurses＇ professional titles,patients＇ nursing grades.An improved stochastic programming model was built which was more suitable for hospitals in China.Then according to the solution structure of the problem,a Genetic Algorithm with Perturb Mutation（PMGA） which was added on every vectors among the solution with a probability was designed.Compared to random greedy algorithm and Bender＇s decomposition based greedy algorithm in experiment,PMGA results were more effective than other methods in solving nurse assignment problem within 30 minutes and it would reduce workload more than 8.9% for each nurse in a shift.Especially,GA with perturb mutation was more efficient in solving multi-scenario,multi-trap nurse assignment problems which have solutions without field continuity.