服务时间变动下的可重入手术调度

王 恺，陈 夏，陈丽君

（1.武汉大学 经济与管理学院；2.湖北中医药大学 信息工程学院）

0 引言

作为医院内部最为核心的系统，手术系统涉及医务人员、医疗物资和设备设施等各类手术资源，如何提升其运作效率已成为确保医院整体收益与服务质量的重要问题。手术调度需要结合手术过程和资源需求，为调度期内亟待进行的手术确定开始时间和分配各类手术资源［1～3］。病人的手术过程通常分为术前准备、手术和术后恢复阶段，依次在准备室、手术室和恢复室进行［4，5］。当前国内外的某些医院受资金、空间的限制或者希望提高床位利用率，不单独建设准备室和恢复室，而是设置更多的公共床位，可同时用于术前准备和术后恢复。美国明尼苏达州的梅奥诊所就采用了类似的作法［6］，不仅有效减少了特定时段因病人拥塞造成的床位不足，还大幅提高了护理人员的工作效率。

由于病人在术前准备和术后恢复时可进入同一区域使用床位，因此这类特殊的手术系统具有病人可重入的特点。可重入场景常见于生产制造领域，出于工艺的特殊要求，同一工件需要在一些特定的机器上进行多次操作处理，极大地增加了生产调度优化的难度［7］。目前暂未发现有学者进行过可重入手术系统的调度优化研究。

已有的医院手术调度文献大都集中在静态环境下的调度优化问题，而实际手术过程会受医护人员水平、病人病情和其它各类突发事件干扰，容易出现术前、术中和术后的服务时间偏离预期时间。因此，近年来部分学者开始关注动态环境下的手术调度问题，已有研究主要采用随机规划、鲁棒优化和模糊规划的方法进行数学建模。Molina-Pariente等［8］使用多个随机变量描述急诊病人的到达时间和手术时长，建立了用于求解手术室调度问题的混合整数随机规划模型。Addis等［9］针对考虑不确定手术时间的手术室计划与调度问题构建了鲁棒优化模型。类似地，周炳海和殷萌［10］以最小最大遗憾作为决策准则，对不确定时间下带资源约束的手术室鲁棒调度问题进行了研究。考虑到医院手术调度问题的复杂性，学者们通常使用简单的分派规则和模拟退火算法、禁忌搜索、遗传算法、蚁群算法等高效的元启发式方法进行求解［11，12］。目前关于动态环境下的手术调度研究均未同时考虑手术准备时间、手术时间和术后恢复时间的不确定性。

综上所述，本文将对考虑服务时间变动的可重入手术系统调度进行研究，以最小化病人术后恢复的平均完成时间为目标，构建医院可重入手术调度的数学优化模型，提出基于经典遗传算法与变邻域搜索的自适应混合调度算法，通过块邻域和基于轮盘赌的邻域变换策略增强算法的局部优化性能。当前研究手术调度优化的文献均未考虑术前准备与术后恢复共同占用床位资源的情况，也未同时考虑术前、术中、术后服务时间变动的情形。

1 问题描述及数学模型

1.1 问题描述

服务时间变动下的可重入手术调度问题可描述为：某医院拥有M间设备齐全的手术室，公共区域有F张可用于术前准备和术后恢复的床位，可同时为多位病人提供术前、术中和术后的医疗服务。现需要为某工作日亟需手术的N位择期病人安排手术。病人的手术过程分为三个阶段，分别为使用公共区域的床位进行术前准备、手术室手术、术后重新转移到公共区域的床位上恢复。每个阶段的实际服务时长取决于医护人员水平、手术类型和手术当天病人体征，可能会偏离预期服务时长。本问题的服务时长均采用三角模糊数来描述，即根据医院的历史统计数据来确定每位病人每个阶段最长、最可能和最短的服务时长。

考虑到生产运作管理与医疗运作管理的相似性，近年来开始有学者将生产运作管理中的理论、模型和方法用于求解手术调度问题［13］。如下图所示，多间手术室和公共区域的多张床位相当于车间里不同加工阶段的多台并行机，病人为待处理工件，术前、术中和术后的医疗服务可看作柔性流水车间（Flexible Flow Shop，FFS）的三个处理工序。由于病人会先后两次使用公共区域的床位进行术前准备和术后恢复，因此该调度问题具有可重入特性，可视为可重入FFS调度问题，属于NP难问题［14，15］。

图1 病人的手术过程

该问题的数学模型基于以下假设：（1）只对择期手术进行调度优化，而不考虑急诊手术；（2）同一病人选择不同手术室或不同床位对所需服务时长没有影响；（3）同一病人术前准备、手术和术后恢复必须连续进行；（4）术前、术中和术后各阶段所需资源（人员、药品、工具等）在开放时段内随时可用；（5）不考虑病人在手术室和公共区域床位间的转移时间。

1.2 数学模型

考虑到服务时长的变动，每位病人术前、术中、术后的服务时长与各项服务的开始和结束时间均采用三角模糊数。模型中的符号与变量定义如下：

N：病人数量；

No：手术室数量；

Np：公共区域的床位数量；

pi，1：病人术前准备时长；

pi，2：病人手术时长；

pi，3：病人术后恢复时长；

ti，1：病人术前准备的开始时间；

ti，2：病人的术前准备的结束时间；

ti，3：病人手术开始时间；

ti，4：病人手术结束时间；

ti，5：病人术后恢复的开始时间；

ti，6：病人术后恢复的结束时间；

M：充分大的正数；

基于以上定义，可以得到本文研究问题的数学模型如下：

其中，目标函数（1）为最小化某工作日全部病人术后恢复的平均结束时间；约束（2）、（4）分别保证每位病人只能使用公共区域的一个床位进行术前准备和术后恢复；约束（3）保证每位病人的手术必须在一间手术室内完成；约束（5）、（6）保证公共区域内的任一床位不能同时为多位病人提供术前准备服务；约束（7）确保每间手术室不能同时进行多台手术；约束（8）、（9）保证公共区域内的任一床位不能同时为多位病人提供术后恢复服务；约束（10）确保同一病人的术前准备、手术和术后恢复连续进行；约束（11）用于确定病人每项服务的结束时间；约束（12）确保病人术前准备时间的合法性；约束（13）规定了决策变量的取值范围。

由于上述数学模型中采用三角模糊数描述不同服务的服务时长与各项服务的开始和结束时间，目标函数的计算将涉及到三角模糊数的累加、取大、比较等操作。假设b3）均为三角模糊数，累加操作＝（a1+b1，a2+b2，a3+b3）可用于计算每位病人不同阶段的服务结束时间，取大操作＝（a1∨b1，a2∨b2，a3∨b3）可得到每位病人不同阶段的服务开始时间，比较操作则用于比较同一问题两个解（手术调度方案）的性能。对于任一三角模糊数本文的比较操作均采用以下三个通用准则［16～18］：

准则1c1（s）＝（s1+2s2+s3）／4，根据c1对和进行比较；

准则2c2＝s2，若的c1相等，则根据c2进行比较；

准则3c3（s）＝s3-s1，若上述两个准则无法区分，则根据c3进行比较。

2 基于遗传算法和变邻域搜索的自适应混合优化算法HGA-AVNS

作为一种模拟生物进化的随机搜索算法，遗传算法（Genetic Algorithm，GA）采用选择、交叉、变异操作达到种群进化［19］。变邻域搜索（Variable Neighborhood Search，VNS）则基于特定的邻域变换规则在不同的邻域中实现高效的局部搜索［19］。由于VNS可以有效避免算法过早收敛，我们提出了基于GA和VNS的自适应混合优化算法（HGAAVNS）。HGA-AVNS通过较为新颖的块邻域和基于轮盘赌的邻域变换策略来增强算法的局部搜索能力。

2.1 编码、种群初始化、个体选择

对于当日需要进行手术的n位病人，可基于服务这些病人的先后顺序进行编码。比如，编码s＝（s（1），s（2），…，s（n））中的s（k）是第k位被服务病人的编号。HGA-AVNS首先随机生成初始种群，然后通过轮盘赌方法选出较好的个体作为父代。考虑到种群中个体的目标函数值Zi为三角模糊数，我们通过准则1计算其精确值c1（Zi），并将其倒数作为个体适应度值。

2.2 交叉操作

为了更为有效地对解空间进行搜索，HGAAVNS通过两点交叉法生成子个体。如图2所示，该方法首先在父个体中随机选取cut1、cut2两个交叉点，然后子个体1直接复制父个体2中cut1、cut2间的病人，最后其它位置依次复制父个体1中未被复制的病人；子个体2也采用类似的方法生成。

图2 两点交叉示例

2.3 变异操作

为了保持种群中个体的多样性，HGA-AVNS通过插入变异生成新个体。如图3所示，对选中的个体随机选取delete和insert两个位置，将delete位的病人插入到insert位的病人之前。

图3 插入变异示例

2.4 自适应变邻域搜索

为了有效提高HGA-AVNS的局部搜索能力，本文提出了一种全新的自适应变邻域搜索（Adaptive Variable Neighborhood Search，AVNS）算法。该算法采用了6种基于块的邻域结构进行局部搜索，并通过自适应的邻域变换规则动态地选择表现较好的邻域结构。

2.4.1 基于块的邻域结构

病人术前准备和术后恢复都会使用公共区域的床位，如果因为床位不足而导致部分病人无法及时进行术前准备，则会出现即使有空闲的手术室也无法实施手术的情况。考虑到上述场景，我们把需要进行手术的病人分为等待与无等待两类。等待病人指因公共区域空闲床位不足使得所分配手术室处于等待状态的病人，无等待病人指在所分配的手术室可以连续进行手术的病人。通过将病人进行分类，可以将种群中的每个个体分解成多个病人块，其定义如下：

块：个体（病人序列）由包含n位需要进行手术的病人组成，等待病人将个体分成m个集合，即病人块。块内的第一位病人为块首，最后一位病人为块尾。在每一个块内，除了块首，其余病人全部是无等待病人。

本文研究的医院手术调度可看作生产制造领域的可重入FFS调度。对于FFS调度问题，已有研究中常用的邻域结构（Neighborhood Structure，NS）主要包括插入邻域、互换邻域与逆序邻域等。根据块的定义和调度问题常用的邻域，本文采用下面6种基于块的NS来实现局部搜索：

（1）NS1：在随机选中的一个块内使用插入操作，即在块内随机选取一位病人并将其随机插入到块内的其它位置；

（2）NS2：在随机选中的一个块内使用互换操作，即在块内随机选取两位病人并互换位置；

（3）NS3：在随机选中的一个块内使用逆序操作，即在块内将随机选取的两位病人之间的所有病人进行逆序排列；

（4）NS4：若个体中块的数量m＞1，首先从前m-1个块中随机选取一个，然后将它的块尾和后面相邻块的块首互换；否则，保持个体不变；

（5）NS5：若个体中块的数量m＞1，首先从前m-1个块中随机选取一个，然后将它和后面相邻块的块首互换；否则，保持个体不变；

（6）NS6：若个体中块的数量m＞1，首先从前m-1个块中随机选取一个，然后将它和后面的相邻块互换；否则，保持个体不变。

上述6种NS主要对块内或块间的病人进行调整，以期通过减少块的个数来降低等待病人的数量与提高手术室的利用率。

2.4.2 随机扰动和局部搜索

对于一个特定的当前解x，随机扰动过程会根据所选取的NS生成一个新的邻域解x′，从而避免HGA-AVNS的种群过早收敛。NS的选择过程可详见2.4.3邻域变换。

在对当前解x进行随机扰动后，对新的邻域解x′进行局部搜索。与随机扰动类似，该过程仍然是在当前选中的NS中进行，以期获得手术调度问题的局部最优解。HGA-AVNS采用常见的 firstimprovement局部搜索方法。该方法不断生成x′在当前邻域结构中的邻域解xn，若xn优于x，则x＝xn并更新当前局部最优解，重复上述过程直至连续迭代5次后局部最优解没有改变。

2.4.3 邻域变换

HGA-AVNS的局部搜索性能不仅取决于所使用的NS，还会受不同NS间搜索顺序的影响。经典VNS一般先将NS按照其规模与复杂度进行排序，然后根据事先定义的规则更换邻域进行局部搜索，这些规则通常不根据所生成邻域解的优劣来确定NS，往往导致局部搜索效率不高。而HGA-AVNS则使用了全新的自适应邻域变换规则，可以根据6个块邻域生成邻域解的优劣来动态选择合适的NS。

在该规则中，每次邻域变换均要考虑当前邻域的搜索效果。邻域集合｛NS1，NS2，…，NS6｝中的任一邻域NSk都有一个选中概率pk，其计算公式如下：

其中，ck和sk分别为使用Nk进行局部搜索的次数和得到更好的解的次数，m为一个非常小的正数以避免pk为零，Rk为多次通过Nk进行局部搜索时找到更好的解的比例。每个块邻域的选中概率均初始化为1／6，当所有邻域遍历一次后，pk可按式（14）～（15）进行更新，能够找到更多更好邻域解Nk的被选中的概率就越大。在各邻域的pk更新之后，我们使用轮盘赌的方法来更换邻域。

2.5 HGA-AVNS算法求解过程

步骤1初始化HGA-AVNS算法参数，主要包括HGA-AVNS的最大进化代数G1，种群规模PS，交叉率Pc，变异率Pm，AVNS的最大迭代次数G2；

步骤2随机生成由PS个个体组成的初始种群，将其中最好的个体作为当前全局最优解πb，设定HGA-AVNS中的当前迭代次数g1＝1；

步骤3执行基于轮盘赌的选择操作；

步骤4根据交叉率Pc执行两点交叉操作：

步骤5根据变异率Pm执行插入变异操作：

步骤6选出当前种群中的最优个体π，执行AVNS进行局部搜索。设定AVNS中的当前迭代次数g2＝1，令π为AVNS最优解πm的初始值。如果g2≤G2，重复步骤6.1～6.3；否则，输出；

步骤6.1邻域变换：根据式（14）更新6种NS的选择概率pk，并采用轮盘赌方法确定一种邻域结构NSk，并更新其被选中次数ck＝ck+1；

步骤6.2随机扰动：根据所选的NSk，生成π的一个邻域解π′；

步骤6.3局部搜索：根据所选的NSk，对π′进行该邻域内的局部搜索，得到局部最优解π″，则g2＝g2+1；若π″优于π，则π＝π″，sk＝sk+1；若π″优于

步骤7将AVNS得到的替代种群变异后的最差个体。若优于πb，则πb＝。同时使用精英保留规则，用πb替代种群中的最差个体；

步骤8令g1＝g1+1。若g1≤G1，将更新后的种群作为下一次迭代的输入，转至步骤3；否则，输出最优解πb。

3 实验结果与分析

为验证HGA-AVNS求解服务时间变动下可重入手术调度问题的有效性，本文先通过田口实验确定HGA-AVNS主要参数的取值，再对比HGAAVNS与其它几种算法的优化性能。所有的优化算法全部采用MATLAB 2016a实现，实验测试环境配置为InteCoreTMi7 4GHz CPU和4GB RAM。

3.1 实验数据

考虑到服务时间变动下的可重入手术调度暂无国际公认的测试算例，本文基于多家医院的历史数据与已有的手术调度研究［20］，采用以下数据生成测试算例，其中服从均值为180分钟、标准差为60分钟的对数正态分布［16］*rand（）；pi，3＝，其中服从均值为-10分钟、标准差为15分钟的对数正态分布［16］，rand（）为0-1间均匀分布的随机数。通过遍历No，Np，N的所有组合共产生4×2×2＝16个测试问题。

3.2 关键参数实验分析

HGA-AVNS为混合元启发式方法，其优化性能受到G1、PS、Pc、pm和G2等算法参数影响。本文选取一个中等规模的手术调度问题（No＝13，Np＝15，N＝30），首先使用田口实验方法对算法参数的灵敏性进行分析，然后确定HGA-AVNS上述四个参数的取值。

HGA-AVNS关键参数的因子水平为G1＝｛50，100，150，200｝、PS＝｛50，100，150，200｝、Pc＝｛0.6，0.7，0.8，0.9｝、Pm＝｛0.03，0.05，0.07，0.09｝、G2＝｛50，70，90，110｝。如表1所示，采用L16（45）正交表，共计16组典型参数组合。对于选定的中等规模问题，采用特定参数组合的HGA-AVNS分别求解10次，计算目标函数的平均值Z*，并通过准则1得到其精确值c1（Z*）。基于表1中的c1（Z*），图4描述了各参数不同取值对HGA-AVNS优化性能的影响。由图4可知，HGA-AVNS参数的最佳取值为G1＝200，PS＝200，Pc＝0.7，Pm＝0.03，G2＝70。

表1 田口实验设计和实验结果

图4 实验设计均值主效应图

3.3 算法性能实验分析

针对服务时间变动下的可重入手术室调度问题，本文将HGA-AVNS与其它三种调度算法进行了对比：（1）最短服务时长规则（Shortest Service Time，SST）：优先为手术时长短的病人提供术前、术中和术后服务；（2）经典GA：选择、交叉、变异操作和HGA-AVNS相同；（3）GA-VNS：与HGA-AVNS的唯一差别在于使用传统的邻域变换规则，即从第一个邻域NS1开始，若在某邻域NSk内进行搜索后获得的新解优于当前解，则重新回到中搜索；否则，在下一个邻域NSk+1中继续搜索。

为了更加公平地对比优化算法性能，GA和GAVNS的主要参数取值与HGA-AVNS相同。对于每个测试问题，SST只求解1次，而GA、GA-VNS和HGAAVNS分别求解10次。表2给出了16个测试问题不同优化算法的测试结果。其中，Z*为解的均值，c1（Z*）为使用准则1得到的精确值，Dev为算法性能的相对偏差。Dev的计算公式为其中和分别为SST、GA、GA-VNS和HGA-AVNS得到的解或解的均值。

通过分析表2中各优化算法的Z*、c1（Z*）和Dev，我们可以得出下面的结论：（1）按优化性能从优到劣依次为HGA-AVNS、HGA-VNS、GA、SST；（2）三种元启发式算法得到的解明显好于SST；（3）在GA、HGA-VNS和HGA-AVNS三种元启发式算法中，GA性能最差，表明对于本文所求解的手术室调度问题混合启发式算法优于单一启发式算法；（4）对于多数测试算例，HGA-AVNS求得的解要好于HGA-VNS，说明在GA和VNS的混合优化算法中引入高效的邻域变换规则能够增强算法的优化性能。

表3给出了上述几种算法的CPU运行时间（单位为秒）。对于16个测试问题，算法的平均运行时间按由短到长排序分别为SST、GA、HGAVNS、HGA-AVNS。SST是一种十分简单的分派规则，运行时间较短，但优化性能较差。GA、HGAVNS和HGA-AVNS均为元启发式算法，通过种群的不断进化实现随机搜索，优化性能较好，但是运行时间偏长。特别地，作为混合优化算法，由于HGA-VNS和HGA-AVNS在GA里嵌入了VNS来提升局部搜索性能，导致它们的运行时间比GA稍长。与HGA-VNS相比，HGA-AVNS运行时间稍短。综合表2和表3的实验数据，尽管HGA-AVNS的求解时间稍长，但是优化性能最佳。

表2 不同规模问题下SST、GA、HGA-VNS、HGA-AVNS的测试结果

表3 不同规模问题下SST、GA、HGA-VNS、HGA-AVNS的运行时间

4 结论

对于服务时间变动下的可重入手术调度问题，本文使用三角模糊数描述术前、术中和术后的服务时长，以最小化病人术后恢复的平均完成时间为目标，构建了术前和术后共用床位的可重入手术调度模型，设计了基于GA和VNS的自适应混合优化算法HGA-AVNS。为了提高HGA-AVNS的局部搜索性能，设计了六种块邻域，并采用基于轮盘赌的方法动态选择合适的邻域进行搜索。最后通过一组测试算例比较了多个优化算法的性能，验证了所提算法的优越性。

本文将可重入生产系统的特性引入至医院的手术调度问题中，不但扩大了可重入理论的应用领域，而且提高了手术系统的稳定性和医疗设施的利用率。我们尚未考虑紧急手术、医疗资源有限等情况，因此未来可以在医院动态手术条件下同时考虑不同类型的医疗资源约束，进一步加强本文所提出的模型和算法的实用性。