面向医疗器械企业灭菌工艺的不同容量平行机批调度

刘雪红，张 涛，彭 兆，王 磊

(武汉理工大学 1.机电工程学院；2.湖北省数字制造重点实验室，湖北 武汉 430070)

当前我国医疗水平不断提高，医疗器械制造技术高速发展，医疗器械产品的生产面临如下现状：1) 客户对高精度医疗器械产品的个性化需求越来越高，医疗器械产品的生产模式由面向产品转变为面向客户和订单，催生了高精度医疗器械产品多品种小批量的生产模式；2) 由于当前环境问题日益突出，政府和社会大众的环保意识越来越强烈，因此企业在生产过程中，不仅要考虑产品质量、生产成本和准时交货率，还要考虑产品的社会和环境效益。为了适应社会和市场发展需求，医疗器械制造企业需要建立高准时交货率和低能耗的生产调度与控制体系。

在高精度医疗器械产品的车间生产过程中，灭菌工艺是成品出厂前的最后一道工艺，但其加工时间较长，导致在制品库存积压、产品订单频繁拖期的问题较为突出。此外，加工过程能耗较高，对企业的生产效益造成极大的影响。因此，灭菌工艺是影响产品生产进度和企业生产效益的瓶颈环节[1]。制定合理的生产和调度计划，提高灭菌车间的生产运作效率是医疗器械企业亟待解决的核心问题。

为满足灭菌工艺的要求，灭菌车间采用组批加工方式，对其调度属于平行机批调度(parallel machine batch scheduling，PMBS)问题。PMBS问题在制造业中是一类常见的批调度问题，在应用方面具有很强的实用背景，如模具热处理、机械加工、港口货运调度等领域[2]。近年来，PMBS问题的研究取得了很大的进展[3-13]。针对平行机批调度问题，目前大多研究集中在以最大完工时间为目标的调度研究，部分文献同时考虑了能耗指标和不相同平行机的约束，如加工速度或容量等。但是在医疗器械企业灭菌实际工艺生产过程中，到达时间和尺寸不同的工件在不同容量、不同加工速度的平行机上的批调度问题更为常见，而这一研究国内并无报道。

因此，本文基于医疗器械企业的实际生产需求，研究面向企业灭菌工艺生产过程的不同容量的平行机批调度问题(different capacity parallel machine batch scheduling，DCPMBS)，建立以总延迟时长、总加工能耗和机器的平均装载率为优化目标，兼顾考虑企业生产效益和社会环境效益的混合整数规划调度模型。并综合应用INSGA-III算法、EDT+MLC(earliest delivery time and machine loading capacity，交货时间越紧优先和装载容量与机器容量成比例)启发式规则和改善非支配解质量的局部搜索策略进行模型求解。

1 问题描述与建模

1.1 问题描述

在医疗器械制造的灭菌工艺生产过程中，产品在生产车间完成组装包装流程后，必须经过灭菌工艺处理达到质量标准。如图1所示，企业资源计划(enterprise resource planning，ERP)系统接收客户订单，经ERP系统处理后下发给制造执行系统(manufacturing execution system，MES)，MES根据订单的需求时间和数量，结合实时已到达的任务和未来一段时间内预测的将要到达的任务，考虑灭菌车间的加工能力，对订单进行组批，然后分配到相应的灭菌柜中加工，同时制定相应的生产计划给生产车间，灭菌完成后放入仓库等待发货。

图 1 灭菌工艺加工过程示意图Figure 1 Schematic diagram of sterilization process

1.2 问题模型

为研究DCPMBS问题，本文作如下假设。

1) 由于灭菌工艺是最后一道工序，系统能基本预测未来一定时间段内将会到达的任务、任务到达的时间、批量大小和交货时间，且任务不能进行拆分；

2) 单个任务批量均小于任意批处理机容量；

3) 灭菌车间包含一个无容量限制的缓存区，当对任务分配灭菌批后，一旦开始灭菌，不允许中断。

模型涉及的参数及其描述如表1所示。

表 1 模型参数符号及说明Table 1 Model parameter symbols and descriptions

本文以最小化总延迟时长、最小化总能耗、最大化灭菌柜平均装载率为目标函数，使用Graham[14]的三参数表示法，将DCPMBS问题表示为为此，构建多目标混合整数规划模型如下。

目标函数为

其中，约束(5)表示每个灭菌批都会且只能被分配到一个灭菌柜；约束(6)表示每个任务都会被分到一个灭菌批，每个灭菌批都会被分配到一个灭菌柜；约束(7)表示任一灭菌批k的批量大小等于该批中所有任务批量大小之和，且不超过所在灭菌柜Mi的容量Ci；约束(8)表示灭菌批的灭菌时长为其所在灭菌柜的灭菌时长；约束(9)表示灭菌批k的到达时间Tkr为灭菌批内最迟到达任务的到达时间；约束(10)表示灭菌批k的开始灭菌时间为到达时间Tkr与该灭菌柜内上一灭菌批完工时间的最大值；约束(11)表示任务j的拖期时长为0与完工时间减交货时间的最大值。

2 算法设计

Uzsoy[15]已经证实了以最小化制造跨度为目标，工件尺寸不同的单机批调度问题为NP-hard问题。而本文研究的DCPMBS问题是在单机批调度问题的基础上演化来的更为复杂的NP-hard问题，难以在多项式时间内找到最优的调度方案。考虑到本文所研究的是一个多目标优化模型，因此利用多目标遗传算法“基于参考点的非支配排序多目标优化算法(NSGA-III)”求解。NSGA-III是由Deb等[16]于2014年提出的一种基于参考点的非支配排序多目标优化算法，Jain等[17]、陈立鹏[18]和袁源[19]对该算法进行了扩展和应用。NSGA-III采用基于参考点的方法对个体进行选择，很好地解决了在面对3个及以上目标的多目标优化问题时，算法的收敛性和多样性不好的问题。因其具有较快的收敛速度以及良好的Pareto解集分布性，在生产调度领域得到广泛的关注与应用[20]。根据所研究的多目标优化问题的特性，本文提出一种改进的NSGA-III(INSGA-III)算法用于求解DCPMBS。该算法制定了新的初始种群生成规则，选择、交叉和变异策略，并加入一种局部搜索策略来提高算法的求解质量。

2.1 INSGA-III算法

求解DCPMBS问题的INSGA-III算法流程如图2所示。

图 2 INSGA-III算法流程图Figure 2 INSGA - III algorithm flow chart

2.2 编码与解码

编码规则采用基于灭菌柜的实数编码方式，以确定每个任务的加工灭菌柜。染色体长度为n，表示n个待灭菌的任务，每个位置代表相应的任务批次；以长度为m的数组表示m个灭菌柜，在基因串对应的位置赋予灭菌柜的值，表示该任务被分配到对应的灭菌柜上灭菌。

解码规则对于分配在同一台灭菌柜Mi上的任务，按顺序排列，依次将任务取出，直到满足灭菌批量小于灭菌柜容量且使灭菌批量最大化时，组成一批进行灭菌，余下的任务再进行组批。同理，其他灭菌柜上的任务也按此规则组批。图3所示为一个由3台灭菌柜、10个任务组成的编码和解码方式示 例。任 务N1、N2、N6、N10被 分 配 给 灭 菌 柜M1，N3、N5、N9被分配给灭菌柜M2，N4、N7、N8被分配给灭菌柜M3。然后逐一对分配给各自灭菌柜的任务，按照任务的排列顺序，根据灭菌柜容量进行组批，形成各自的灭菌批加工。

图 3 编码解码方式示例Figure 3 Example of encoding and decoding

2.3 初始种群的生成

为了生成高质量的初始种群，参考Pinedo等[21]提出的最长加工时间(largest processing time，LPT)规则，结合本文所提出的多目标优化中的交货延迟时长与灭菌柜的装载率，根据启发式规则EDT+MLC产生初始个体。

启发式规则步骤如下。

步骤1全部任务按照交货时间非降序排列，若交货时间相同，则按任务到达时间非降序排列，得到排序后的任务集合N。

步骤2全部灭菌柜按空闲时间顺序按非降序排列，若空闲时间相同则按照灭菌时长非降序排列，得到排序后的灭菌柜集合M。

步骤3选择任务序列中未被分配的第1个任务N1，生成1个[1,n]之间的随机数i，表示任务N1在灭菌柜Mi上灭菌。

步骤5重复执行步骤4，直到所有任务被分配完成，得到1个个体。

步骤6重复执行步骤1～5，生成初始种群。

2.4 选择策略

传统的NSGA-III采用典型的二元锦标赛选择机制。该机制有助于种群进行全局寻优。但随着种群的进化，种群的基因趋于相似，单纯使用锦标赛选择机制，会使种群产生大量相同个体，种群容易陷入局部最优，并且不利于种群的多样性增加。因此，本文采用基于精英保留策略的二元锦标赛选择机制。

步骤1首先将种群中位于第1层级的个体复制到子代中(精英保留策略)，使得优秀的基因可以直接保留到下一代。

研发基于BIM技术的设计软件主要目的是实现PKPM系列不同设计软件间数据共享、系统集成，绿色建筑设计以绿色建筑评价标准指标为依据，所以软件集成的数据核心是以绿色建筑评价标准为基准，达到软件之间数据共享的目的，从而提高建筑信息的复用率，保证数据的一致性，达到提高生产效率的目的。

步骤2将剩下的种群个体进行二元锦标赛选择，首先随机选择2个个体i和j。选择过程如下。

若Ranki＞Rankj，则选择个体j进入下一代；

若Ranki=Rankj，且NPi＜NPj，则 选 择 个 体i进入下一代；

若Ranki=Rankj，且NPi=NPj，则随机选择一个个体进入下一代。

其中，Ranki表示个体i所在非支配层级数。NPi表示个体i关联的参考点Pi所对应的关联到的个体数量。

步骤3判断选择的个体是否达到初始种群数量PopSize，若否，继续执行步骤2；否则，选择过程结束，输出下一代中的个体参加交叉变异。

2.5 交叉和变异策略

交叉策略采用部分映射交叉策略(partial-mapped crossover，PMX)。对种群中的2个个体i和j，首先产生2个交叉点，然后确定具体的基因交叉位置，规则如下。

步骤1首先生成2个随机数ri∈(0,1)、rj∈(0,1)，根据ri、rj产生的交叉点。按cpi=ceil(rin)确定交叉位置cpi、cpj，其中n为任务数量。

变异策略采用多点位随机变异策略，增加种群中基因的多样性，将不同灭菌柜中的任务进行交换，步骤如下。

步骤1对种群中参与变异的个体，首先随机产生变异任务的数量r∈[1,n]，然后根据变异任务数量，产生r个随机数ir∈(0,1)，确定具体的变异位置。

步骤2对于需要变异的任务进行灭菌柜的替换，使之变异为另一个灭菌柜编号，进而产生一个新的个体。假设产生的随机数r=3，i1=2，i2=5，i3=7，变异操作流程如图5所示。

图 4 交叉策略示意图Figure 4 Crossover strategy diagram

图 5 变异策略示意图Figure 5 Mutation strategy diagram

2.6 局部搜索策略

为了提高算法的求解效果，获得更好的Pareto解集，本文在算法中加入一种局部搜索策略，在种群进行交叉变异之后，将执行局部搜索，局部搜索策略步骤如下。

步骤1对产生的子代以比例γ随机选取进行局部搜索的个体，并分别选取个体中对各适应度值影响最大的的任务批。

步骤2将所选任务批中的灭菌柜编号，依次设定为除当前灭菌柜编号之外的其他所有灭菌柜编号，以n个适应度值和m个灭菌柜为例，则会生成至多mn-1个局部可行解。

步骤3计算适应度值，对其进行非支配排序，以提高非支配解的分布性。

以2个适应度值、2个灭菌柜为例，其局部搜索过程如图6所示。

3 仿真实验

3.1 参数设置

对不同规模(加工任务数量不同)的实例分别进行仿真实验。采用某医疗器械企业灭菌生产过程中的数据，根据企业一定周期内销售订单的规模，确定不同规模任务数量n分别为60、120和180；生产过程中，灭菌柜数量为4台，其参数信息如表2所示。以规模为60的任务批量为例，其任务批量信息如表3所示。为了更好地检验所提INSGA-III算法在求解DCPMBS问题上的有效性，将分别以NSGAIII和企业实际生产过程中所产生的目标值(actual production，AP)作为比较对象，将实验所得非支配解集作为该算法的求解结果，通过比较所获解集相应目标值的平均值作为算法评估的依据。算例中，最大迭代次数MaxIt = 100，初始种群数目PopSize=200。本实验在Matlab 2019a上实现。

图 6 局部搜索过程示意图Figure 6 Local search process diagram

表 2 灭菌柜参数信息Table 2 Parameter information of sterilization cabinet

表 3 规模为60的任务批量信息Table 3 Task batch information of size 60

3.2 实验结果

当任务规模n分别为60、120和180时，INSGAIII算法与传统NSGA-III算法求解得到的Pareto解集以及实际生产(AP)所求得的各目标值在三维坐标系中位置，如图7～9所示。在不同规模实例下获得的非支配解实验结果对比如表4～5所示，表中各目标值为10次运行结果的平均值。

图 7 Pareto解集图(n = 60)Figure 7 Pareto chart (n = 60)

图 8 Pareto解集(n=120)Figure 8 Pareto chart (n=120)

图 9 Pareto解集(n=180)Figure 9 Pareto chart (n=180)

由图7～9和表4～5可以看出，INSGA-III算法相较传统的NSGA-III算法和AP调度方式有明显的优势。INSGA-III算法在各目标值上都有明显的优化结果(表5)。当n=60时，相较传统的NSGA-III算法，INSGA-III算法在总延迟时长方面，降低12.08 d，降低比例为33.53%；在总能耗方面，降低5.02×105kw·h，降低比例为33.94%；在装载率方面，提高6.29%，提高比例为7.89%。相较实际生产(AP)，INSGA-III算法在总延迟时长方面，降低17.41 d，降低比例为42.09%；在总能耗方面，降低7.99×105kw· h，降低比例为44.99%；在装载率方面，提高10.65%，提高比例为14.13%。因此，综合考虑不同规模任务，从灭菌工艺的3个优化目标来看，INSGA-III算法具有较好的效果。

表 4 调度结果比较Table 4 Comparison of scheduling results

表 5 INSGA-III算法相较其他调度方式优化结果Table 5 INSGA-III algorithm optimizes the quantity and percentage compared with other scheduling methods

4 结论

本文主要针对医疗器械企业灭菌工艺生产过程的调度问题，提出面向灭菌工艺的不同容量平行机批调度问题的多目标优化调度模型。针对求解目标设计一种启发式规则生成初始种群，并设计一种改进NSGA-III算法求解该问题。通过算例仿真表明，改进算法在求解该问题上具有良好的性能，可为企业实际生产调度提供指导。但仍存在一些问题，之后的研究中可以考虑任务存在不相容，加工机器存在时间限制等约束，以便更好地与企业实际相结合。