护士排班问题的软约束和具体约束及其解决方法分析

© 2013年。出版社：Elsevier B.V.由美国应用科学研究所负责选择和/或同行评审可在www.sciencedirect.com在线获取ScienceDirectAASRI Procedia 4（2013）202 - 2052013年AASRI智能系统与控制具有软约束和具体约束的里卡多·索托a，b *，布罗德里克·克劳福德a，c，罗德里戈·贝特朗a，埃里克·蒙弗罗伊daValparaiso，Av. Brasil 2950，Valparaíso，Chileb Universidad Autónoma deChile，Av. Pedro de Valdivia 641，Santiago，Chilec Universidad FinisTerrace，Av. Pedro de Valdivia 1509，圣地亚哥，智利dCNRS，LINA，南特大学，2 Rue de la Houssinière，南特，法国摘要护士排班问题（NRP）处理的是在给定的医疗保健中心的日常运作的护理人员的轮班安排。这个问题被认为是复杂的，主要是由于它的组合性质，通常需要指数时间来解决。文献提出了一个大的清单，致力于解决NRP的作品，但他们中的大多数都集中在著名的NRP实例的结果的性能，只有少数地址的真实情况。在本文中，我们提出了一个研究真正的护士排班，特别是涉及到一个非常罕见的转变模式，由于适当的国家法律法规。我们引入了一个新的模型，包括软约束，可以有效地解决采用具体化的约束。© 2013作者。由Elsevier B. V.在CC BY-NC-ND许可下开放获取。由美国应用科学研究所负责选择和/或同行评审关键词：优化;约束规划;护士排班1. 介绍护士排班包括在给定的时间段内满足一组约束条件的轮班分配时间表。已知该问题具有挑战性，主要是因为变量的数量和* 通讯作者。Tel.+ 56 32 2273659;传真：.+ 56 32 2273859电子邮件地址：ricardo. ucv.cl2212-6716 © 2013作者由Elsevier B. V.在CC BY-NC-ND许可下开放获取。美国应用科学研究所负责的选择和/或同行评审doi：10.1016/j.aasri.2013.10.031Ricardo Soto等人/ AASRI Procedia 4（2013）202约束的复杂性。医院管理政策、政府法规、最小面积分配、不同的护士技能要求以及护士之间的公平性是限制问题的因素。已经提出了不同的商业和通用解决方案来解决这个问题。然而，由于从一个场景到另一个场景的各种约束，它们通常无法满足给定的要求。因此，卫生中心试图设计量身定制的解决方案，以满足其特定的政策和运作机制。护士花名册已在很大程度上研究从七十年代。来自数学规划领域的经典和精确的方法早期被用来解决这样的问题[4]。自90年代以来，元分析在排班研究中占据了重要的地位。已经提出了不同的解决方案，一些例子使用禁忌搜索[2]，模拟退火[13]，遗传算法[8]，可变邻域搜索[7]，电磁元分析[9]。在完全搜索的背景下，约束编程也强烈参与护士排班，一些例子可以在[1，6，11，10，14]中看到。然而，大多数工作都集中在有效地解决知名的情况下，致力于护士排班的真实情况下的工作是相当有限的。本文介绍了一个真实的情况下，护士排班在中型智利医疗保健中心的研究。我们以三家诊所和四家医院为样本，收集了这些卫生中心的主要特征（类似的规模，组织和护士数量）。该问题被表示为一个CSP（约束满足问题），涉及软约束和硬约束，并通过JaCoP求解器用CP（约束编程）算法求解。我们相信，这项工作将是有益的，以增加在实际情况下的护士排班，以及未来的NRP研究人员的经验。2. CPCP是一种相对现代的软件技术，致力于有效解决受约束的问题。这种范式的主要特征继承自计算机科学的不同和相关领域，如运筹学，编程语言和人工智能。在CP中，一个问题被正式地表述为CSP，它由一个有限的变量序列、相关的域集（即，）和一组约束组成。一个CSP的解是一个赋值，使得;且集合C满足[3]。3. NRP模型智利的中型保健中心采用一种特殊类型的轮班分配，称为"第四班“制度。这种制度是相当罕见的不适合与常见的8小时轮班制度中使用的大多数医院和研究论文。"第四班“制度考虑每天两班12小时：D班和N班。D对应白班（从08：00到20：00）; N对应夜班（从20：00到次日8：00）。3.1. 对护士的“第第1第2第3第4DN关闭关闭我们考虑一个28天的计划，以涵盖28种可能的组合4（一个周期内的班次数）× 7（工作日数然后，考虑到护士的设置，Ricardo Soto等人/ AASRI Procedia 4（2013）202- 205天，以及变量集，其中0=休息日，1=D，2=N，约束建模如下：D班在N班之前，N班又在休息日之前，一个N班在两天休息之前，这反过来又在D班之前，：现在，为了保证所需的护士分配和每天的护士，发生的全局约束。保 证Val在名为Vars的列表中出现两次。 表示变量的集合。然后，所需的约束为：、和。3.2. 软约束软约束允许对偏好进行建模。例如，在所研究的医疗保健中心，有护士担任高级职位，能够在时间表上提出一些偏好。由于常见的CP求解器不提供原语直接处理软约束，我们通过使用具体化的约束建模的软约束。一个具体化的约束reified（ck，Bk）如果满足约束ck，则将1（true）赋给变量Bk;否则将0（false）赋给变量B k。然后，我们的想法是最大化Bk变量的总和，如下所示，假设，其中p是偏好的数量：然后，约束满足问题自然转化为优化问题。例如，让我们考虑三个偏好：c1：护士5不喜欢在第一天休息; c2：护士2和4喜欢从白班开始。C3：11号护士喜欢在周期的第三个周末休息。这些约束可以建模如下：c 1：V 5，1 0; c2：V2，1= 1 V4，1= 1; c3：V11，20= 0 V11，21= 0.最后，我们提出三个 具体化的约束和相应的目标函数，以获得解：具体化（c1，B1）具体化（c2，B2）具体化（c3，B3）最大化JaCoP中的实现描述如下。首先，具体化约束的结果存储在一个名为B的数组中。然后，求和存储在第4行的求和变量中，然后将其施加到约束存储器中。在第6行，初始化具有域[-INF，0]的可变成本。然后，在第7行，求和的值乘以-1并赋给成本变量。这样做是因为JaCoP只最小化，因此，必须反转求和变量的值。最后，标记方法触发使用成本变量作为成本函数的分支定界算法。1.store. implement（new Reified（c1，B[1]））;2.store. implement（new Reified（c2，B[2]））; 3.4.int sum = new Sum（B，sum）;5.return（i）;6.int cost = new IntVar（store，“Cost”，-INF，0）;7.store. implement（new XmulCeqZ（summation，-1，cost））;8.boolean result = search.labeling（store，select，nrp.cost）;Ricardo Soto等人/ AASRI Procedia 4（2013）2024. 结论本文介绍了一个NRP研究的一组智利中型医疗保健中心。我们已经提出了一个模型，通过软约束处理一个非常罕见的轮班模式和护士的喜好。软约束已被建模，通过使用具体化的约束结合一个目标函数，以最大限度地满足偏好的数量。通过这种方式，模型成为JaCoP求解器中已解决的优化问题。考虑到40名护士，名册在大约20分钟内自动生成。通过考虑更大的医疗保健中心和更复杂的软约束，这里提出的方法自然可以扩展。使用元搜索和自主搜索[5，12]也将是一个有趣的研究方向。引用[1] Bourdais S，Galinier P，Pesant G（2003）. Hibiscus：A constraint programming applicationto staff scheduling in health care.在CP的程序，LNCS的第2833卷，第153斯普林格。[2] Burke E，Causmaecker PD，Berghe GV.护士排班问题的混合禁忌搜索算法。在《海豹突击队学报》，LNCS第1585卷，第187-194页。斯普林格。[3] 贝西埃角（2006年）。《约束编程手册》，第29-84页。爱思唯尔[4] B. Cheang，H. Li，长穗条锈菌A.林湾，澳-地罗德里格斯（2003年）：护士名册问题-书目调查。European Journal of Operational Research 151（3）：447-460[5] Crawford B，Soto R，Monfroy E，Palma W，Castro C，Paredes F.基于粒子群优化的选择函数超启发式算法的参数调整.专家系统应用40（5）：1690-1695。[6] Li H，Lim A，Rodrigues B（2003）.护士排班问题的混合人工智能方法。在SAC的会议记录中，第730-735页。Press.[7] Lü Z，Hao JK（2012）.护士排班的自适应邻域搜索。European Journal of Operational Research，218（3）：865[8] Maenhout B，Vanhoucke M.护士排班问题的演化方法。Computers OR，38（10）：1400[9] Maenhout B，Vanhoucke M.护士排班问题的电磁元启发式算法。J. Heuristics，13（4）：359[10] Métivier JP，Boizumault P，Loudni，S（2009）.使用软全局约束求解护士排班问题。在CP的程序，LNCS的第5732卷，第73-87页。斯普林格。[11] Pizarro R，Rivera G，Soto R，Crawford B，Castro C，Monfroy E.智利瓦尔帕莱索临床中心基于约束的护士排班。在Proceedings of HCI International 2011，第174卷，第448-452页中。斯普林格。[12] Soto R，Crawford B，Monfroy E，BuyanV（2012）.约束程序设计中使用自主搜索生成好的枚举策略混合。在ICCSA会议记录中，LNCS第7335卷，第607-617页，Springer。[13] Thomson G（1996年）。模拟退火启发式算法在非连续可用员工轮班调度中的应用。计算机与运筹学，23：275[14] Qu R，He F（2008）.护士排班问题之混合约束规划法。在SGAI的会议记录中，第211