基于改进变邻域搜索算法的成型机分批重调度优化

徐立云，程 赞，宓 宏，李爱平

（1. 同济大学机械与能源工程学院，上海200092；2. 浙江衢州联州致冷剂有限公司，浙江衢州324000）

磁性材料是一类非常重要的基础功能材料，被广泛应用于家用电器、电子通讯、医疗保健等行业领域［1］。某企业磁性材料生产线主要包括：球磨、成型、烧结、研磨和检分五道工序，除球磨过程以外均为离散型生产，是典型的多阶段、多工序、多设备的混合式生产过程。各个工序之间时间和数量的协调复杂，其中成型工序是利用成型机将细粉压制成瓦形的毛坯件，其生产调度不仅要考虑模具规格以及自身产能的限制，还要考虑工单优先级、粉料库中的粉料情况和下游窑炉的产能限制。现有成型工序的生产调度方案由人工采用Excel表格手动安排，由于调度主观性大，容易造成成型机资源的浪费，甚至会导致工单的延期，因此，设计合理的成型机生产调度方案对于保证工单准时交付，提高资源利用率具有重要意义。

通常成型工单的磁瓦数量很大，以千计量。如果采用合理的分批策略，将每条工单分成若干子批，并按照一定的顺序将这些子批安排到成型机上生产，则能够有效地提高生产效率和工单准时交货率［2］。不同种类的成型机加工不同规格磁瓦所需时间不同，属于非等同并行机。目前对作业车间、流水车间和并行机均有分批调度问题的研究［3］。Low等［4］研究了批量分割在车间调度中的作用，并以总成本最小和完工期最短为目标建立整数规划模型求解车间调度问题。Shim等［5］采用分支定界法求解最小化总体拖期时间的并行机分批优化调度问题。Tahar 等［6］针对考虑作业分批和切换时间的并行机调度问题，建立线性规划模型并采用改进的启发式算法求解。史青涛［7］采用改进遗传算法对制造成本和完工时间两种不同优化目标下不同分批原则对并行机分批调度方案的影响进行了研究。张震等［8］提出一种混合差分遗传算法对考虑模具约束的并行机分批调度问题进行求解，实现了分批与调度并行优化。李国臣等［9］采用先组批后调度的两阶段求解策略对考虑能耗约束的非等同并行机组批调度问题进行求解，通过与遗传算法对比验证了粒子群遗传混合算法的优越性。王海燕［10］针对并行机分批问题中的批量划分约束提出一种基于任务分配队列的实数编码方式，设计一种基于块变异、块交叉的全局搜索操作，通过算法对比验证了所提混合差分进化算法的优越性。

可以看出，已有很多学者针对静态分批调度问题展开研究，但由于成型工艺约束复杂，问题局限性很强，不能够采用通用模型进行求解，因而，很少有人研究磁性材料成型机的分批调度问题。且在已有的研究中，很少有人考虑车间设备冗余情况下生成的调度方案中设备利用率不高的问题。

实际生产过程会出现紧急插单、粉料不足、成型机故障、工单交货期改变、订单取消等事件，从而使已经制定好的计划难以执行下去。由于传统调度方法不具备应对动态扰动的能力，会导致大量生产任务延迟。这时需要采用重调度方法来改进原方案。Larsen等［11］设计了由控制器和求解器构成的重调度框架，并通过对车间调度问题的大量测试证明了该框架可用于解决车间重调度问题。Gao等［12］针对紧急插单引起的柔性车间重调度问题，设计一种离散的Jaya 算法对重调度方案的不稳定性、完工时间和机器负荷进行优化。顾泽平等［13］以最大流程时间短、工序分配均衡和设备利用率高为目标，对不确定因素扰动下的多目标柔性作业车间调度方法进行研究。Li 等［14］针对生产过程中的紧急插单、机器故障事件，提出了一种基于禁忌搜索的混合人工蜂群算法对柔性车间进行重调度，并使用一种集群分组轮盘算法优化初始种群质量。俞胜平等［15］建立了开工时间延迟下的炼钢‐连铸生产重调度模型，提出了由炉次加工设备指派和作业时间决策组成的启发式重调度方法。Mao 等［16］以效率和稳定性为优化目标，利用拉格朗日松弛算法求解了存在机器故障和加工时间扰动的炼钢‐连铸重调度问题。屈新怀等［17］采用粒子群算法对不确定扰动因素下的动态分批调度问题进行求解并获得了较好的结果，但算法稳定性有待提高。

综上所述，已有大量学者对重调度问题进行了研究，却很少有人将重调度方案的准时性和稳定性与分批调度结合起来优化。因此，本文针对成型机故障和工单交货期提前等不确定性事件，引入重调度方案偏离度和平均提前拖期时间指标，建立成型机分批重调度多目标优化模型，并设计一种改进的变邻域搜索算法对该模型进行求解。最后，结合实际案例验证所提重调度方法的可行性和算法的优越性。

1 问题描述及模型建立

1.1 问题描述

成型机分批调度问题是在考虑工单不延期、粉料库中的粉重限制、工单优先级、模具规格限制、成型机产能和下游窑炉烧结工位产能等复杂约束下，以工单平均提前完工时间最小为目标，确定各工单在成型机上加工的模数和顺序以及投产的各类成型机数量。考虑到实际生产调度中成型机故障和交货期提前导致的工单延期问题，需要寻找一种合适的重调度方法对原调度方案进行调整优化。

某磁性材料成型车间有成型机m 台，在一段时间内要完成n条工单的加工。不同成型机的模具安装能力不同，能够生产的磁瓦规格不同，其对应关系如图1所示。

图1 产品和成型机对应关系Fig. 1 Correspondence between products and molding machines

成型车间采用典型的面向订单生产模式，为避免重调度引起的频繁换模，采用最小分批原则对工单进行批量划分，即加工批量不能小于一定的数量；基于非等量分批原则对工单进行批量划分，即不固定每个工单的子批产量大小，可以更加灵活地安排生产，提高重调度方案中工单的准时交货率。根据成型生产调度过程，设计工单优先顺序原则如下：

（1）优先加工交货期早的工单；

（2）若交货期相同，则优先加工优先级高的工单；

（3）若完工期和优先级都相同，则优先加工模数少的工单。

问题基于以下假设：

（1）所有工单的生产需求计划已知；

（2）各类成型机的设备操作人员充足；

（3）成型机能够在调度初始时刻开始生产；

（4）忽略成型机换模时间对生产的影响；

（5）成型机在某一时刻只能加工一个工单；

（6）任意一台成型机一旦开始加工某个工单的子批，则在该子批完工前不能加工其他工单的子批。

本文的成型机分批重调度模型相关符号如下：

i——工单编号，i= 1，2，…，n；

j——成型机编号，j = 1，2，…，m；

xi——工单i的磁瓦类型；

yj——成型机j的类型；

pi——工单i的优先级；

Di——工单i的总模数；

gi——工单i的每模投粉量；

τi——工单i的预定交货期；

Oi——工单i加工顺序，满足Oi≤n；

qij——工单i在成型机j上的子批大小；

Qmin——工单子批最小值，通常为定值；

Q——工单的批量分配矩阵；

wxy——x 类型磁瓦在y 类型成型机上每模加工时间，若为0，则表示由于安装模具的限制，x类型磁瓦不能在y类型成型机上生产；

t——时间周期，d；

cit——工单i在时间t的生产模数；

Fit——工单i在时间t的可用库存粉重；

td——每台成型机日最大开工时间；

tij——工单i在成型机j上的子批完工时刻；

tij*——重调度后工单i在成型机j上的子批完工时刻；

isj——时间s结束时成型机j正在生产的工单；

G——下游烧结工位日最大产能，即窑炉每天所能烧成最大模数。

1.2 重调度模型建立

考虑到重调度触发条件和对原调度方案影响的不同，重调度方法分为维持原调度、局部重调度和完全重调度［18］。其中局部重调度是指在设备状况出现变化时，对局部受影响的子批进行微调，调度效率高；当工单需求出现变化时，局部重调度难以生成较优的方案，采用完全重调度可以重新整理全局资源调度，获得更好的重调度结果。因此，本文基于以上两种重调度方法提出一种多层次重调度方法，即在成型机故障时采用局部重调度，在工单交货期提前时采用完全重调度。同时，为了评估重调度方案的合理性，不仅需要考虑重调度方案的准时性，还应考虑其稳定性。基于以上分析，成型机分批重调度模型建立过程如下。

（1）决策变量

根据磁瓦与成型机类型对应规则确定每条工单在各台成型机上生产的子批。决策变量为工单的批量分配矩阵Q

当成型机发生故障时，原调度方案中成型机正常生产的时间被占用，将停产时间段所影响的部分工单对应的虚拟工单进行再分批，此时决策变量为虚拟工单的批量分配矩阵Q1。

当工单交货期变化时，应从触发时间点开始整理所有工单待生产数量和所有成型机正常加工时间，并以此作为初始数据重新进行分批，此时决策变量为所有工单的批量分配矩阵Q2。

（2）约束条件

其中，

式（2）表示磁瓦只能在具有相应模具安装能力的成型机上生产；式（3）表示对于每个工单i，分配在各成型机上的子批大小之和等于该工单的总产量；式（4）表示工单i在成型机j上的子批完工时间等于安排在成型机j上生产的所有不晚于i的工单加工时间之和；式（5）表示工单i分配在所有成型机上的子批均不能出现延误；式（6）表示成型机生产所需的粉料重量不能超过粉料库中现有的库存粉重；式（7）表示截止到时间s，所有成型机生产的总产量不应超过s时下游烧结工位的总产能；式（8）表示为避免成型机在短时间内频繁换模，工单分配到成型机上的子批产量不能小于规定的最小值；式（9）表示成型机每日产能约束，即每台成型机每日所安排的加工时间总和不应超过日最大加工时间。

（3）目标函数

在以往的文献中，经常把工单提前完工时间定义为最晚完工子批的完成时间与工单预定交货期的差值，虽然能保证工单准时交付，却忽略了其他子批提前完工造成的在制品库存累积问题。同时在设备数量较多而工单较少的情况下，容易导致工单分散，降低设备利用率。因此，为了在满足需求的前提下选择更少的加工设备，本文将工单i的提前完工时间定义为工单i所有子批的提前完工时间之和，即因此不考虑扰动时的目标函数为

为了评估重调度方案的合理性，首先定义方案偏离度和平均提前拖期时间两项衡量重调度方案好坏的指标。

方案偏离度d等于重调度前后所有子批的完工时间偏差绝对值之和，见式（11），用来衡量重调度方案的稳定性。d越大，说明方案调整越大。

平均提前拖期时间h等于每台成型机上各个子批的提前拖期时间的加权平均，用来衡量调度准时性。同时为了体现工单拖期的严重性，引入惩罚因子e，见式（12）。通过增大e值可以获得拖期时间更少的重调度方案。

合理的重调度方案应同时兼顾工单准时性和调度稳定性。综上所述，本文所研究的成型机分批重调度问题属于多目标优化问题。采用加权系数法求解该优化模型，引入变量v表示方案偏离度的权重，重调度目标函数为

2 算法设计

针对本文提出的成型机分批重调度问题，传统的邻域搜索算法容易陷入局部最优，同时单一邻域结构难以满足实际生产中提前和拖期的不同需求。为解决此问题，设计一种改进的变邻域搜索算法（VNS），搜索过程中能够在约束范围内通过切换不同的邻域结构以拓宽搜索范围，提高收敛速度和跨过局部最优的概率。

2.1 初始解构造

个体初始化流程图见图2所示。种群初始化采用二元锦标赛选择策略。初始化大量个体组成临时种群，每次从临时种群中选择两个个体，将较优个体放入初始种群，直至初始种群规模达到预先设定的大小。

图2 个体初始化流程图Fig. 2 Flow diagram of individual initialization

个体采用随机方法初始化增加了邻域搜索起点的多样性，避免算法陷入局部最优。种群采用二元锦标赛方法初始化能够保证在选择较好个体的同时，允许部分较差的个体进入种群，使搜索能够从一个较高的起点开始，提高算法的收敛速度。

2.2 邻域结构设计

2. 2. 1 转移邻域

假设成型机j1和j2均能生产工单i，将工单i在成型机j1和j2上的子批重新分配，称为工单i的子批转移，子批转移示例如图3 所示。子批转移通常针对工单i，将成型机j1上子批部分产量转移到成型机j2上或反向转移，从而产生两个新邻居。

图3 子批转移示例图（单位：模）Fig. 3 Example of sub-batch transfer（unit:pattern）

初始的子批转移量选取为批量最小单元step，通过随机确定工单i以及成型机j1和j2来选择转移邻域，然后生成该个体在此邻域内的两个邻居，通过比较两个邻居的约束情况和目标函数大小决定局部搜索方向，朝该方向不断搜索直至两个邻居均不满足约束或均劣于个体，此时该邻域上个体已达到局部最优。

2. 2. 2 叠加邻域

将成型机j1上已分配的所有工单子批全部转移到成型机j2上的操作，称为子批叠加。子批叠加示例如图4所示。

图4 子批叠加示例图（单位：模）Fig. 4 Example of sub-batch superpose（unit:pattern）

子批叠加的优点在于能够迅速将各个工单分散的批量集中起来，大幅降低工单平均提前完工时间，同时使整个种群朝着使用更少成型机的方向不断演化。但子批叠加会导致被叠加成型机j2上的生产任务迅速增加，容易违反工单不延期约束；同时如果成型机无法加工某些子批对应的工单，则新的个体无法满足成型机加工能力约束。因此，子批叠加很大概率上不能生成满足约束的新个体。

针对成型机批量调度约束和编码方式特点定义了两种邻域结构：转移邻域和叠加邻域。子批叠加用以迅速提高个体质量，子批转移用以进行更精细的搜索，避免搜索过快而导致丢失最优解。

2.3 邻域搜索策略

2. 3. 1 基于概率接受的局部搜索

为提高种群多样性，在搜索过程中并不每次都接受邻域内的最优解，而是保存收敛过程中产生的所有个体，从最优个体开始逐个往前选择，每次选择时以预先设定的概率Pa来判断是否接受该个体作为邻域搜索的结果，具体流程如图5所示。

图5 基于概率的局部搜索流程图Fig. 5 Flow diagram of local search based on probability

2. 3. 2 变步长搜索

为提高邻域搜索的收敛速度，在进行转移邻域搜索时，采用变步长的搜索方式。首次邻域搜索时，采用初始步长step 判断搜索方向并进行搜索，第二次迭代搜索时步长为2*step，后续每次搜索时步长翻倍，不断迭代直至无法找到更优个体；此时退回上次搜索起点，并重新使用初始步长step继续迭代，当使用step搜索也无法发现更优个体时，搜索结束。

综上所述，改进的变邻域搜索算法流程图如图图6所示。

图6 改进变邻域搜索算法流程Fig. 6 Flow diagram of improved VNS algorithm

3 案例分析

3.1 案例数据

某磁性材料工厂成型车间一共有12台3种类型的成型机，车间布局见图7所示。

图7 成型车间布局图Fig. 7 Layout of molding workshop

不同类型成型机由于能够安装的模具类型不同，具备不同的加工能力。各类成型机加工不同磁瓦对应的时间见表1，其中“0”表示该磁瓦不能在此类型成型机上生产。每台成型机每天最多工作10 h，下游烧结工位能提供的最大日产能为5 400模。以一批成型工序的工单作为案例进行分析，这批工单开始生产时间为6月7日，工单的最晚预定交货期为6月13日，工单参数见表2。

表1 各类成型机加工时间Tab. 1 Processing time of various molding machines

表2 工单参数Tab. 2 Parameters of work order

3.2 调度方案分析

为验证所提方法的有效性，采用Matlab 2016编写程序。在生成调度方案之前，首先需要确定批量最小单元step的大小，由于磁片的模数以千计量，为了分析不同的step 值对重调度结果的影响，分别选取step= 10，50，100进行实验，为了加快算法收敛过程，其余参数选取为种群大小popSize= 100、迭代次数mIter = 3 000、局部搜索接受概率Pa= 0.95。运行程序，3 种不同step 下的目标函数收敛曲线如图8所示，可以看出，当step= 50 时，目标函数平均提前完工时间的收敛速度最快，收敛于427 min，远小于step= 10 和step= 100 的收敛结果。因此，本次实验选取批量最小单元step= 50。

图8 不同step下的收敛过程Fig. 8 Convergence process in different steps

初始化VNS 算法参数：批量最小单元step= 50，局部搜索接受概率Pa= 0.95，种群大小popSize= 500，最大迭代次数mIter = 3 000。算法连续运行30次，取最好收敛结果。

采用本文优化目标函数求解得到的调度甘特图如图9 所示。分批调度方案如表3 所示。采用传统目标函数求解得到的分批调度方案如表4所示。甘特图中同一工单的多个子批以标号区分，如1‐2的含义为1号工单的第2个子批，可以看出所有工单均能满足交货期要求。

两种方案启动的成型机数量和成型机平均利用率对比结果如表5 所示。可以看出，在磁性材料成型车间这类存在设备冗余的车间中，采用本文提出的成型机分批调度模型在降低成型机使用数量，减少空闲待机时间，提高成型机平均利用率方面能够取得更好的效果。

图9 调度方案甘特图Fig. 9 Gantt chart of scheduling scheme

表3 优化目标函数下工单分批方案Tab. 3 Batching scheme of work order in optimized objective function 模

表4 传统目标函数下工单分批方案Tab. 4 Batching scheme of work order in traditional objective function 模

表5 分批调度方案对比Tab. 5 Comparison of batching scheduling schemes

为了验证本算法的优越性，同时采用传统邻域搜索算法和改进VNS算法对本问题进行求解，前者参数选取如下：批量最小单元step= 50，种群大小popSize= 500，最大迭代次数mIter = 3 000；后者参数选取同前者，且增设两种邻域结构，即转移邻域和叠加邻域，接受概率Pa= 0.95。两者的目标函数值收敛曲线对比如图10所示。可以看出，相比于传统邻域搜索算法，改进VNS 算法收敛速度更快，全局寻优能力更强。

下面验证考虑成型机故障和交货期提前情况下重调度方案的有效性。

图10 算法收敛过程对比Fig. 10 Comparison of algorithm convergence processes

在6 月12 日开始生产之前成型机M5、M7、M8发生故障，持续1 h。由图9可知，受影响的子批为4‐1、5‐1 和5‐2，对应的虚拟工单4' 和5' 的产量分别是60模和120模。

由于考虑成型机故障进行局部重调度时仍处于计划阶段，未对制造资源做出分配，所以不考虑重调度的稳定性，取目标函数中v= 0；同时应尽量避免重调度造成的工单拖期，设置拖期时间惩罚因子e=5，目标函数如下式：

由于受影响模数较少，取step= 10，其余参数不变，求解得出虚拟工单分批方案见表6，甘特图如图11 所示。可以看出，在考虑成型机故障的情况下采用局部重调度可以迅速对原方案进行局部调整，耗费较少的计算成本即可得出较优的重调度策略。

表6 虚拟工单分批方案Tab. 6 Batching scheme of virtual work order 模

当成型生产过程中发生交货期提前事件时，应采用完全重调度方法。在6月7日生产5 h后突然出现工单提前交付事件，2号工单和3号工单预定交货期从6 月10 日提前到6 月9 日。此时重新整理成型机资源和需求，结果见表7。

图11 局部重调度方案甘特图Fig. 11 Gantt chart of local rescheduling scheme

表7 更新后的工单参数Tab. 7 Updated parameters of work order

为尽量避免工单拖期，设置拖期时间惩罚因子e= 5。权重v的取值大小取决于决策时的偏向，当重调度偏向于减少制造资源变动时，应设置较大的v；当重调度偏向于工单平均提前拖期时间较少时，应设置较小的v。为验证不同决策目标的影响，分别取v为0. 3和0. 7进行实验，采用改进VNS算法进行求解，两个完全重调度工单分批方案分别见表8 和表9，对应的甘特图分别如图12和图13所示。

表8 完全重调度v=0.3时工单分批方案Tab. 8 Batching scheme of global rescheduling at v=0.3 模

表9 完全重调度v=0.7时工单分批方案Tab. 9 Batching scheme of global rescheduling at v=0.7 模

图12 完全重调度v=0.3时甘特图Fig. 12 Gantt chart of global rescheduling at v=0.3

图13 完全重调度v=0.7时甘特图Fig. 13 Gantt chart of global rescheduling at v=0.7

可以看出，两种方案的2号、3号工单均能在6月9日完成交付，从而证明了本文提出的多层次重调度方法的有效性。计算两种方案的方案偏离度d和平均提前拖期时间h，对比结果见表10。

表10 重调度方案对比Tab. 10 Comparison of rescheduling schemes

扩大v的采样点，不同v下的方案偏离度和平均提前拖期时间分别见图14和图15所示。从表10和图14、15可以看出，当v较小时，方案偏离度较大，重调度时成型机调整成本较高，但方案准时性较好；当v较大时，方案偏离度较小，调整成本较低，方案稳定性好，但是较高的提前拖期时间会增加成型与烧结间的库存成本。在实际成型生产过程中，计划人员可根据重调度的具体需求，权衡稳定性和准时性的重要程度，选择合适的权重进行重调度决策。

图14 不同v下的方案偏离度Fig. 14 Scheme deviation at different v values

图15 不同v下的平均提前拖期时间Fig. 15 Average early delay time at different v values

4 结语

本文针对实际生产中成型机故障和工单交货期提前两类事件，采用最小分批原则和非等量分批原则对成型工单进行批量划分，引入重调度稳定性和准时性指标，建立数学模型，在VNS 算法中设计转移邻域和叠加邻域两种结构进行变换搜索。最后通过实例验证了所提重调度方法能够在保证所有工单准时交付的基础上，提高成型机利用率，为工厂的实际生产决策提供参考。