《基于模拟退火的护士调度算法研究NP难问题》由会员分享，可在线阅读，更多相关《基于模拟退火的护士调度算法研究NP难问题（53页珍藏版）》请在金锄头文库上搜索。
1、基于模拟退火的护士排班算法研究摘要随着经济的发展，国内外医疗问题越来越受注。护士是医疗机构中的重要成员。护士排班是医院日常工作的重要方面。科学合理的护士排班能降低医院的人力资源成本，提高护理质量。护士排班是基层护理者的一项经常性工作，是在现有的人力资源基础上，对护理工作任务、内容、程序、人力、和时间因素通盘考虑，做出系统、科学地安排，使护理人员明确职责，工作效率得到提高，保证医院护理质量，同时降低人力资源成本 赵美玉.护理管理学M.郑州：郑州大学出版社，2004：。由于护士排班问题受各种劳动法规约束，不同护士的能力有差异以及护士有班次偏好需求，护士排班问题是极为复杂的组合优化问题，属NP难问题
2、。本文旨在利用模拟退火算法求解该问题。本文首先对护士排班问题建立整数规划模型，考虑护士级别和偏好，在减少医院成本的同时，尽量满足护士对于班次的偏好。然后探讨用模拟退火算法求解护士排班问题。详细设计了模拟退火算法，首先在不破坏一些约束的情况下（如晚班后不能接着上早班），随机产生初始解，然后用增加护士和减少班次的方法对初始解进行可行化，再在不破坏解的可行性的情况下，对排班表进行变换来产生新解，构成模拟退火的关键部分，再设计接受准则和算法参数，完成了算法的设计。最后，在C+ builder 6.0环境中进行编程实现，对湖南省某市级医院某科室的护士排班问题就行求解，取得了良好的效果。 关键字：护士排班
3、；建模；模拟退火算法Study on Nurse Scheduling Algorithm Based on Simulated AnnealingAbstractAs the rapid development of economy, health organization is highly concerned at home and abroad. Nurses are important members of health organization. Nurse scheduling is an important part of daily operation in hospital
4、s. Scientific and reasonable nurse scheduling can not only reduce the operating costs of hospitals but also improve the quality of nursing work. Nurse scheduling is a normal job of nurses at basic level, considering the nursing work, content, process, personnel, and time factors, which is making sys
5、tematic and scientific plan to make nurses clear about their work, improve the proficiency and quality of their work and reduce personnel cost. Because nurse scheduling problem is constrained by many rules of labor law and there are differences of abilities and preferences between different nurses,
6、nurse scheduling is a combination optimization problem, belonging to NP hard problem. The thesis has built the integer programming of nurse scheduling problem, considering the levels and preferences of nurses. The thesis tries to use simulated annealing method to solve the nurse scheduling problem.
7、At first, initial solution is generated randomly. At the same time, the up work time of a nurse is protected not to be broken and other constrains are concerned, for example, when a nurse gets a night shift, he cant get the morning shifts the other day. Then adding nurse and subtracting shift method
8、s are used to make the schedule feasible. In addition, much iteration is used to make the schedule better. Finally, programs are written in C+ builder environment and good result is reached. Key words: nurse scheduling, model, simulated annealing algorithm目录摘要IAbstractII1绪论11.1 选题背景和意义11.2国内外研究现状11.
9、2.1国内研究现状21.2.2国外研究现状31.3 研究内容与组织结构32 护士排班问题建模52.1 护士排班问题52.2 护士排班问题整数规划模型63 基于模拟退火的护士排班算法73.1 模拟退火算法概述73.2 基于模拟退火的护士排班算法设计93.2.2 方案可行化113.2.3 新解的产生123.2.5 接受准则143.2.4 参数设计144 基于模拟退火的护士排班算法实现与案例分析144.1 案例背景144.2 算法实现154.2.1 类的设计154.2.2 模拟退火算法实现164.3 结果分析165 总结与展望185.1 总结195.2 展望19致谢19参考文献201绪论1.1 选题
10、背景和意义 近年来，国内外医疗问题越来越受重视。护士是一种需要经过专业训练的人力资源、是医院日常运营的基础。护士排班问题也属于医疗问题的一个方面。目前世界各地（特别是在发达国家）的护士资源不足的问题越来越严重，受到了广泛重视。但是在我国管理机构对护士资源的重视度尚不够，致使很多地方出现护士严重不足的问题。护理人力资源与病人期望非常不平衡，临床护士编制严重不足，护士班次更换频繁，病人没有相对固定的护理人员，整体护理难以真正落实到位，如何通过管理合理使用人力资源，从而解决人力短缺问题，值得我们不断探讨与研究 院陆蕊,君鲍学,英王惠芬.护士排班的改进与实践J.护理管理杂志，2008，（02），23.
11、。此外，传统的护士排班方法采用手工排班方法，这样显得混乱无序，而且效率低下。随着生活水平的提高，大众对于护理工作的要求也必然随之提高。因此提高护士利用效率非常有必要。运用计算机算法生成排班表，既能提高准确度又提高了效率。从护士数量、结构、配置、分工（排班）等，实施人性化排班。提高护士工作积极性和主动性，使排班具有规律性、提高了管理效率。 护士排班是基层护理者的一项经常性工作，是在现有的人力资源基础上，对护理工作任务、内容、程序、人力、和时间因素通盘考虑，做出系统、科学地安排，使护理人员明确职责，工作效率得到提高，保证医院护理质量，同时降低人力资源成本1。护士排班问题已经成为医院管理的核心内容之
12、一。但是由于排班中存在一系列劳动法约束，外加需要考虑不同护士的能力级别差异，因此，护士排班问题是极为复杂的组合优化问题，属NP难问题，在国外深受研究关注。在解决组合优化问题时，元启发式算法能起到很好的作用。本论文用模拟退火方法研究护士排班算法。 护士排班研究属于护理研究的一部分。现代医学不断发展，对护理工作也提出了更高的要求。研究护士排班问题对于提高护理水平有重要作用，对于促进护理学与先进的医学同时前进具有重大意义。 1.2国内外研究现状 对于护士排班问题，国外的研究较早，很多人用了很多科学方法来优化，而国内的研究较少，很多都停留在手工排班方法，用算法优化的比较少。1.2.1国内研究现状 由于
13、国内的研究大部分都停留在定性方面，从排班类型，排班原则，排班方式三个方面进行总结。另外，也有少数算法的研究。李秋洁 李秋洁护理管理M北京：人民卫生出版社，2003：6061提出排班类型依照排班权利的归属分为集权式排班(由护理部负责)、分权式排班(由护士长负责)及自我排班(由护士自行排班)3种。对于排班原则，吕芳 吕芳新型的以病人为中心的排班模式对护理的影响J现代护理2001，7(6)：51一52提出以病人的需要为基本原则：以病人的护理需要为中心，适应护理工作的连续性，24 h不间断，合理有效地安排人力，护理、教学、科研须统筹兼顾; 秦玉霞等 秦玉霞，李晓星，牛娟互补增值原理在护士排班中的运用J
14、临床护理杂志，2002，l(1)：9一lO提出互补增值原则：掌握护理工作规律，分清主次缓急，合理搭配各层次人员，做到年龄、学历、资历、气质及技能互补，使工作互不重叠、互不干扰，既能保证重点，又能照顾一般; 杨玉霞 杨玉霞门诊护士排班方式的探讨J实用护理杂志，2003，19(2)：65 提出均衡平等原则：保持各班工作量的均衡，按工作量安排人力，一视同仁，各岗位轮转机会均等，使人人充分发挥效能。张萍 张萍ICU护理人员排班与人力资源利用J解放军护理杂志，2004，21(11)：78提出稳定机动原则：护理排班方式应相对稳定，护士长提前安排好下一周班次后向护士公示并上报护理部，使护士对自己的班次有预见
15、性；常备机动人员，以便随时调配归。苟艳梅等 苟艳梅，刘小敏，任秋云，等护士排班需求本在手术室排班中的作用J中华护理杂志，2002，37(1)：5556 提出人性化原则:护士并非单一角色，除工作中的职业角色外，还有社会角色，应以入为本，尽量满足护士的合理要求。对于排班方式，戴琴、周力等 戴琴，冯植重症监护病房护士工作压力源与心理健康水平的相关性研究J中华护理杂志，2002，37(7)：488489 -周力，赵琳，徐梅，等手术室实施弹性排班制度效果评价J护理管理杂志，2002，2(2)：5759提出按功能制护理模式排班实行全院统一排班的方式，按功能制护理方式分配岗位，按岗位配备护士，由白班、中班、前夜班、后夜班组成，每名护士1个班次值l d，循环进行。白班人员有45名，中午、夜班只有1名护士值班，其缺点是白班人员多、夜班人员少，遇到病重、手术病人多或抢救时难以应付，无暇顾及其他病人。该排班方式是我国医院护士排班最常用的，也是近年来要求改革的一种方式，适用于急诊、危重病人较少的五官
