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

开篇：润墨网以专业的文秘视角，为您筛选了一篇求解多场景护士分配问题的扰动变异遗传算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

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

关键词：护士分配问题；遗传算法；扰动变异

中图分类号： TP302；TP18

文献标志码：A

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

HU Lian-min1，2*， HONG Xu-dong2， HUANG Han2

1.School of Physics and Electronic Engineering， Leshan Normal College， Leshan Sichuan 614000， China；

2.School of Software， South China University of Technology， Guangzhou Guangdong 510006， China

Abstract：

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.

英文关键词　Key words：

nurse assignment problem；Genetic Algorithm （GA）；perturb mutation

0 引言

卫生部“2005—2010年中国护理事业发展规划纲要”[1]要求，医疗床位与护士比例应为1∶0.4 ～ 1∶0.6。根据统计，我国医院床护比平均值为1∶0.46，仍未达到国际要求；行业对护理人才的需求量呈上升趋势；对助产、老年护理和重症监护护理等方面需求呈上升状态[2]。由于医疗机构的复杂性，护士分配问题常常具有各种各样的约束条件，而良好的分配方案有助于提高护士的服务质量[3-4]。

Punnakitikashem等[5] 在2006年提出一种基于优化的护士分配原型，把护士规划分为4个阶段，即护士预算、护士调度、护士重调度、护士分配。其中，护士分配即本文所讨论的多场景护士分配问题，处理在每个班次内把护士分配到病人的过程，目的是把超额工作负荷减到最小。Sundaramoorthi等[6] 提出数据整合模拟模型（SIMulation to evaluate Nurse-patient Assignments， SIMNA）来评估护士—病人的分配，利用树状模型和内核密度评估从医院数据中提取出供评估的数据，并在一所医院的数据中实现了数据提取和分析。Punnakitikashem等[7]对护士分配问题建立了基于随机整数规划模型，实验结果说明该方法效果比一般的随机分配或者启发式的分配效果要好。Schaus等[8]提出了新生婴儿到护士的分配方法，目标是在满足各方面约束的情况下，平衡护士的工作负荷。

综上所述，国内外对护士分配问题的算法求解研究较少，该问题是护士排班问题的扩充，关注到了微观上对护士和病人之间的分配关系，这对于护理质量有着更直接的关系。国内外研究也较少涉及微观角度的护士分配问题，较多从宏观角度关注护士排班问题的研究。因此，提出一种普适的、高效的算法来解决护士分配问题是目前学术界关注的热点。