带连续式批处理机的可重入混合流水车间调度

吴秀丽，曹 铮

(北京科技大学 机械工程学院，北京 100083)

0 引言

冷拔无缝钢管主要应用于石油运输、航空航天以及汽车制造等行业中，被人们称为工业的“血管”。冷拔无缝钢管的生产过程存在多道次重入的特征，在一个道次中包括酸洗、修磨、冷拔、退火等环节。其中冷拔阶段是工艺流程中加工时间最长的阶段，在该阶段往往有多台并行机同时进行加工。除此之外，在冷拔后的退火阶段，需要使用退火炉来消除应力，会消耗大量的能源。在企业实际生产中，常用的退火炉有环形加热炉和辊底式炉等，这些退火炉具有连续式批处理机的特征，工件在连续式批处理机上加工时依次进入和离开。因此，这类冷拔生产过程可以被建模为带连续式批处理机的可重入混合流水车间调度问题(Re-entrant Hybrid Flow shop Scheduling Problem with Continuous Batch Processing Machines, RHFSP-CBPM)。目前,无缝钢管的冷拔生产仍依赖于传统的人工排产方式，智能化程度不高，从而导致生产周期长、环保压力大的问题。因此，对冷拔生产过程进行智能调度，提高生产效率的同时减少能耗，具有非常重要的现实意义。

早在1988年，GUPTA等[1]就已证明了混合流水车间调度问题是NP难问题，而冷拔无缝钢管的生产过程除了符合混合流水车间调度问题的特征外，还具有可重入调度和连续式批调度的特征，这使得它的求解更加困难。截至目前，同时考虑可重入调度和批调度的研究还较少，JIA等[2]将半导体晶圆的制造过程抽象为带时间窗的可重入批处理机调度问题进行了研究；林刚[3]将模具热制造过程抽象为两阶段流水车间调度问题，同时考虑了并行批处理机和可重入工件；顾涛[4]研究了无缝钢管生产过程中的周期式退火炉作批处理机的可重入批离散机流水车间调度问题。以上研究考虑了批处理机在各种可重入调度问题中的应用，建立了优化模型和优化算法进行求解，但是仍有研究空间。上述研究中，批处理机的类型都是周期式批处理机，缺少对其他类型批处理机的研究，并且批处理机缓冲区因素的影响也没有被考虑。因此，有必要对RHFSP-CBPM进行研究。目前，分别对可重入混合流水车间调度问题(Re-entrant Hybrid Flow shop Scheduling Problem, RHFSP)和批调度问题的研究都有较为丰富的成果，这些成果可以作为研究RHFSP-CBPM问题时的重要参考。

RHFSP近年引起了国内外学者的广泛关注，可重入调度问题的特点是工件需要在同一个加工阶段多次加工，常见于半导体制造[2]、冷拔无缝钢管[5-6]和电路板印刷制造[7]等行业中。在对RHFSP的研究中，对于单目标问题，CHAMNANLOR等[8]研究了带时间窗约束的RHFSP，结合遗传算法和蚁群算法来最小化完工时间；ZHANG等[9]研究了具有机器可用性约束的RHFSP问题，考虑了总延误的最小化，对离散差分进化算法进行了改进；ZHOU等[10]研究了以总加权完工时间最小为目标的RHFSP问题，并设计了基于集成模型的混合差分进化算法。

在进一步的研究中，更为复杂的目标函数被考虑在内，例如，CHO等[11]以生产效率和客户满意度为目标，设计了多层遗传算法和启发式算法进行了求解；YING等[12]提出一种迭代帕累托贪婪算法，求解具有最小化完工时间和总延误双目标的RHFSP。除了时间相关的指标外，为了实现低碳制造，满足节能减排的需求，越来越多的研究开始考虑能耗相关的指标。董君等[13]对考虑可再生能源的可重入混合流水车间调度问题进行了研究，同时考虑了生产中的制造阶段和检测修复阶段，以完工时间、碳排放和总拖期为目标，设计了基于樽海鞘群和带精英策略的快速非支配排序遗传算法(fast elitist Non-dominated Sorting Genetic Algorithm,NSGA-Ⅱ)的混合算法进行求解。GENG等[14]考虑了机器的开关控制策略，以最大完工时间、最大延误和空闲能耗为目标，提出了一种改进的多目标多阶段优化算法求解RHFSP。并且,在进一步的研究中，他们还研究了考虑多时间因素的绿色可重入混合流水车间调度问题，以完工时间和总能耗为目标，提出一种混合文化基因算法进行求解。上述研究考虑了多种生产环境下的可重入调度问题的求解，提出了一系列智能算法，对完工时间能耗等指标进行了优化[15]。在冷拔无缝钢管的生产过程中，主要的能耗来源于退火过程，而退火炉除了高能耗的特征外，还有批处理的特征，这也是需要考虑的因素。

在批调度问题的研究中，批处理机可以分为两大类：周期式批处理机、连续式批处理机，其中周期式批处理机的研究更多。目前对周期式批处理机调度的研究中，单目标问题的研究以完工时间目标为主，考虑了批处理机的不同能力[16-17]，针对作业的不同规模、释放时间、动态到达等特征进行了研究[18-19]。在进一步的研究中，更多的目标函数被考虑在内。在考虑作业交货期的研究中，延误时间往往会作为完工时间之外的另一个目标函数[20-21]。在考虑成本问题的研究中，能耗[22]、运输成本[23]和机器采购成本[24]与完工时间结合作为多目标优化的指标。上述研究考虑了机器和作业的多种特征，并设计了有效的启发式算法对各类目标进行求解。

在对连续式批处理机的研究中，赵玉芳等[25]针对钢铁行业加热炉对管坯的加热过程，提出一种新的连续型批处理机调度问题，并给出了一批工件的加工时间的计算方式，以保证批处理机同时加工的工件不超过其容量。在进一步的研究中，赵玉芳等[26-27]考虑了释放时间约束和链式约束等条件，并使用动态规划算法对单机连续型批调度问题进行了求解。上述对于连续式批处理机的研究，侧重于组批和工件的排序，仅考虑了批处理一个阶段。因此，对连续式批处理机的研究在问题约束上以及求解方法上都还有进一步的研究空间。

上述研究中，分别考虑了可重入工件和批处理机对调度的影响，开发了智能算法进行求解。在可重入混合流水车间调度问题的研究中，没有考虑重入工件对组批的影响；在批调度问题的研究中，缓冲区大小的影响未被研究。因此，对于可重入调度和批调度的研究还有很大的探索空间。本文以无缝钢管的冷拔生产过程为研究背景，将工件可重入的特征与连续式批处理机相结合，建立RHFSP-CBPM的优化模型，开发了一个改进的基于分解的多目标进化算法(Improved Multi-objective Evolutionary Algorithm based on Decomposition, IMOEA/D)。本文的主要贡献如下：①综合考虑可重入工件、连续式批处理机和缓冲区3方面的特点，建立了数学优化模型；②提出了IMOEA/D，设计了一种针对缓冲区约束和批处理机容量约束的解码策略，在迭代过程中根据种群多样性选择局部搜索策略或多样性增强策略，并对非支配解集进行局部搜索来提高解的分布性；③讨论了连续式批处理机的合适缓冲区大小；④根据批处理机内的实时工件数量，设计了工件的灵活等待时间，在尽可能减少等待时间的同时，保证了批处理机同时加工的工件不超过其容量。

1 带连续式批处理机的可重入混合流水车间调度优化模型

1.1 问题描述

随着钢管企业生产自动化水平的不断发展，连续式退火炉的应用也越来越常见，连续式退火炉常用的有环形加热炉、辊底式炉等，这类退火炉在加工一批工件时采用的是传动的方式，工件在批处理机内连续移动，受热均匀，能够较好地保证退火质量。连续式退火炉和周期式退火炉的工作原理对比如图1所示，连续式退火炉在加工的过程中，一个批次内的钢管依次匀速地进入退火炉，并且在加热完后依次离开，离开后即可进行后续的加工流程；周期式退火炉在加工过程中，一个批次内的钢管同时进入和离开机器，离开机器后所有钢管同时可用。

RHFSP-CBPM可以描述为：混合流水车间包含多个加工阶段，每个阶段包含多台加工能力不同的并行机，工件在每个加工阶段都可在任一并行机上加工。在整个工艺流程中，工件要按照顺序经过这些加工阶段，且在某些加工阶段需要重复加工，从第一个加工阶段到最后一个加工阶段的完整流程称为一个重入道次，在不同的道次工件的加工时间不同。在一个道次的所有加工阶段中，最后一个阶段是批处理阶段，其他阶段均为离散加工阶段。批处理阶段对应的加工机器是连续式批处理机，在连续式批处理机前存在缓冲区，用于存放待批处理的工件；离散加工阶段对应的加工机器是离散机。如图2所示为RHFSP-CBPM的示意图。

为了简化问题，作出如下假设：

(1)工件之间相互独立，互不影响。

(2)所有工件在零时刻都可以被加工。

(3)工件到达机器的搬运时间以及在机器上的准备时间都包含在加工时间内。

(4)机器在加工过程中不允许中途停止或插入其他工件。

(5)连续式批处理机的容量和缓冲区大小已知，离散机上缓冲区大小无限。

(6)连续式批处理机在第一个工件开工时开机，在最后一个工件完工时关机。

(7)连续式批处理机的加工功率和空闲功率已知，且加工过程中功率恒定。

1.2 符号定义

本文用到的符号定义如表1所示。

表1 符号定义

1.3 数学模型

(1)目标函数

式(1)表示RHFSP-CBPM的优化目标，即最小化最大完工时间和批处理机的总能耗。

(1)

(2)约束条件

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

Rii′k∈{0,1},∀i,i′,k。

(18)

式(2)是次序柔性约束，对于同一工件的先后两道工序，后道工序必须在前道工序完工后才能开始加工；式(3)表示在离散机上任意两个工件加工时间不重叠；式(4)表示工序柔性约束，在任意时刻，一个工件只能在一台机器上进行加工；式(5)反映了工件的道次约束，工件只能完成前一个道次的所有工序后才能开始下一道次的加工；式(6)表示工序的完工时间的计算公式；式(7)表示在任意时刻，批处理机内同时加工的工件数不超过批处理机容量；式(8)表示批处理机上批次的次序约束，只有前一批次的所有工件完成加工后，后一批次才能开始加工；式(9)表示在任意时刻，批处理机缓冲区内等待的工件数不超过批处理机容量；式(10)表示一个批次的完工时间的计算公式；式(11)表示批次内每个工件的加工时间等于该批工件中处理时间最长的工件所需的时间；式(12)表示一批工件的开始时间等于该批最早开始加工的工件的开工时间；式(13)表示一批工件总加工时间的计算公式；式(14)表示批处理机上一批工件的加工能耗的计算公式；式(15)表示批处理机加工两批工件间的空闲能耗的计算公式；式(16)～式(18)表示决策变量的取值范围。

2 IMOEA/D

2.1 算法描述

早在1988年，混合流水车间调度问题就被证明是NP难的问题[1]，RHFSP-CBPM在其基础上考虑了工件可重入的特征以及连续式批处理机加工的特征，使得问题的求解更加困难。在对NP难问题的求解中，智能算法一直有着良好的表现[28-29]，2007年ZHANG等[30]首次提出基于分解的多目标进化算法(MOEA/D)，在近年来的研究中，MOEA/D及其相关的改进算法在求解各类优化问题上都表现出了良好的性能[31]。

MOEA/D的原理是将多目标问题拆解为单目标问题，然后同时进行求解，分别逼近Pareto前沿。MOEA/D得到的解在分布范围和均匀性上有良好的表现，但是MOEA/D在收敛过程中，种群的多样性随着迭代次数的增加逐渐降低，算法可能陷入局部最优。为了有效解决该问题，设计了IMOEA/D算法，在迭代过程中根据多样性的好坏来采用局部搜索或多样性增强策略，在提高算法局部搜索能力的同时避免陷入局部最优。算法的流程图如图3所示。

算法具体步骤为：

步骤1随机产生初始种群，计算初始种群适应值，进行非支配解排序得到第一代非支配解集。

步骤2判断是否满足终止条件，若满足则转步骤9，否则进入步骤3。

步骤3给种群中的每一个个体分配子问题的权重向量。

步骤4在该个体的邻域随机选择两个不相同的邻居，依次进行交叉变异，得到子代个体。

步骤5计算子代个体适应值，使用切比雪夫方法更新邻域个体及其适应值，更新非支配解集。

步骤6根据邻域个体适应值是否相同来计算邻域多样性。

步骤7若邻域多样性好，则对邻域个体进行局部搜索；若邻域多样性差，则采用邻域多样性增强策略，采用随机生成或邻域内个体交叉的方式产生新的邻域个体。

步骤8计算局部搜索或多样性增强产生的新个体的适应值，并更新对应的邻域个体，返回步骤2。

步骤9对非支配解集进行局部搜索，更新最终的非支配解集。

步骤10输出最终的非支配解集。

2.2 算法详细设计

2.2.1 编码与初始化

根据RHFSP-CBPM特点，采用工序染色体的编码方式[32]。工序染色体用于确定各工件的工序的加工顺序。工序染色体由工件编号组成，染色体的长度等于所有工件的总工序数，工件编号第几次出现就代表是第几道工序。在工序染色体中一个工件的编号可能出现多次，因此采用原始编码序号结合随机排列序号的方式来初始化一条染色体，以4个工件3道工序的问题为例，初始化染色体的过程如图4所示。

首先根据工件数和工序数，确定原始编码序号，其中蓝色表示第一道工序；橘色表示第二道工序；绿色表示第三道工序。然后根据染色体长度，生成原始编码序号对应位置的随机排列序号，该序号用于决定原始编码序号在染色体中的实际位置，结合这两个序号得到最终生成的染色体。

2.2.2 解码

在对染色体的适应值进行评估时，需要使用相应的解码算法。RHFSP-CBPM的难点在于批处理阶段，需要将合适的工件组批的同时，保证同时加工的工件数量不超过批处理机容量，并在批处理机前缓冲区等待的工件数不超过缓冲区容量。因此，提出了针对缓冲区大小约束的紧前工序后移调度规则和针对批处理机容量约束的工件等待时间计算公式，并设计了如下解码算法，在满足约束条件的同时最小化这两个目标。

(1)紧前工序后移调度规则

连续式批处理机在对一批工件进行加工时，工件通过传动的方式进入批处理机，因此连续式批处理机的前置缓冲区往往是有限的。在解码过程中，当工件到达批处理机时，需要判断工件能否立即开始加工。若能立即开始加工，则不占用缓冲区资源；若工件到达后无法立即开始加工，则需要在缓冲区中进行等待；若缓冲区已满，工件无法在缓冲区中等待，则需要将当前工件的紧前工序进行后移，使得工件到达批处理机时缓冲区未满，或工件能够立即开始加工。

以极端情况下缓冲区容量为0为例，使用紧前工序后移调度规则调整调度方案的过程如图5所示。其中阶段C是连续式批处理阶段，阶段A和B是离散加工阶段，机器C1是连续式批处理机。当前的染色体是“1-2-3-1-2-3-1-3-2”，在图5a调度方案中，工件2的工序2-3占用了红色部分的缓冲区，违背了缓冲区容量为0的约束条件，因此需要对该工序的紧前工序2-2进行后移。调整后的调度方案如图5b所示，此时3个工件完成阶段B的加工后都可以立刻在机器C1上加工，符合缓冲区容量为0的约束条件。

(2)工件等待时间计算方法

工件在连续式批处理机上加工时，由于加工同一批工件时，辊子转速是相同的，所以一批内各工件的批处理时间是相同的，都等于这批中处理时间最长的工件的处理时间；同一批中工件的进入、处理和离开都是连续的。连续式批处理机的容量是有限的，为保证批处理机同时加工的工件数不超过其容量，提出了一种批次内工件等待时间的计算方法。

在解码过程中，根据批处理机内工件的开工时间和完工时间，实时判断批处理机内的工件数量，当新的工件到达批处理机时，计算工件最早能够开始加工的时刻和工件到达时刻的差值，若该差值大于零，则将该差值作为工件的等待时间。假设批处理机容量为b，一个批次内有k个工件，每个工件记为Ti(i=1,2,…k)，批次内工件加工时间为Pc，批次内工件的到达时间为Ai，批次内工件的开工时间为Si，完工时间为Fi。此外，给定一个工件间的最小等待时间Pmin=0.15Pc。批次内工件Ti的等待时间Pi计算公式如式(19)所示，这种等待时间计算方式使得工件能够尽快进入到批处理机中，并且满足了批处理机的容量约束。

(19)

(3)解码算法

对工件工序染色体解码的详细步骤如下：

步骤1依次获取工件工序染色体上的每一个基因，判断其代表的是哪个工件的哪一道工序，计算其所处的阶段。

步骤2若该工件处于离散加工阶段，则转步骤3；若该工件处于批处理加工阶段，则转步骤4。

步骤3遍历该工序所处阶段的所有并行机，使用间隙插空法[32]寻找能够插入的空隙，记录每个机器上该工序的完工时间，转步骤5。

步骤4遍历批处理机上的所有批次，寻找加工时间不小于当前工序的批次，并按照从小到大排序。依次判断当前工件与批次内工件能否进行组批。若能组批，则转步骤6；否则，转步骤7。

步骤5标记能够最早加工完该工序的机器，作为最终选择的机器，将该工序安排到机器上进行加工。返回步骤1，直到所有的基因对应的工序都被加工完毕。

步骤6将该工序加入到最早能够完工的批次中，根据缓冲区约束和批处理机容量约束调整开工时间。返回步骤1，直到所有的基因对应的工序都加工完毕。

步骤7使用间隙插空法[32]寻找批处理机上的所有空隙，将该工序插入到最早能完工的空隙中，该工序对应的工件作为新批次的第一个工件。返回步骤1，直到所有的基因对应的工序都被加工完毕。

解码算法的伪代码如下。

算法1解码算法。

1：依次获取染色体上的每一个基因，计算对应工序所处的阶段k；

2：ifk∈离散加工阶段then

3： 遍历该阶段的所有并行机Mk，寻找能够插入的空隙；

4： 记录每个机器上该工序的完工时间FMk；

5： 将该工序安排到FMk最小的机器上进行加工，返回步骤1；

6：else

7： 遍历批处理机上的所有批次b；

8： 如果能加入到现有批次中，则insert=1，否则insert=0；

9： ifinsert=1 then

10： 将该工序加入到最早能够完工的批次中，返回步骤1；

11： else

12： 将该工序安排到批处理机上的最早能插入的批次空隙中。返回步骤1；

13： end

14：end

15：解码完毕。

2.2.3 交叉和变异

在IMOEA/D中，合适的交叉和变异算子能够提高算法的全局搜索能力。对于工序编码的染色体而言，直接进行片段交叉会产生非法染色体，在交叉后还需要对其进行合理化的操作，并在交叉过程中父代的特征可能因为合理化而遭到破坏。因此，提出分解-交叉-还原的染色体交叉方式，来避免非法染色体的出现，其中交叉方式采用两点映射式交叉(Two-point Mapping crossover operation, TMX)[33]。在分解的过程中，按照阶段对工序编码染色体进行分解，得到每一个阶段内工件加工的顺序，对父代两条染色体的分解过程如图6所示。

按阶段对父代染色体分解后，再针对每个阶段的染色体片段采用两点映射式交叉，交叉过程如图7所示，黑色箭头所在位置为选择的两点。在交叉过程中，染色体1的两点间片段需要根据染色体2对应的次序来映射，而染色体2的两点间片段需要根据染色体1对应的次序来映射，交叉前后的染色体片段如图7所示，这样的映射交叉方式不会得到非法的染色体片段，保证了染色体的可行性。

在对每个阶段的染色体片段进行交叉后，再根据基因在原染色体上的位置进行还原，得到最终交叉后的染色体。以染色体1第一段交叉后还原为例，还原的过程如图8所示，黄色片段是交叉后得到的片段，根据原本在染色体中所在的位置，将其还原到染色体中，得到交叉后的子代染色体。

为提高算法的局部搜索能力，设计了如下变异操作。在变异过程中，若对某个或者某一段基因进行变异，可能会产生非法解，因此，采用基于工件的变异方式，选择两个不同的工件，将其对应的所有基因位置进行互换，得到新的染色体。变异过程如图9所示，其中黑色箭头指向选择的工件序号。

2.2.4 根据多样性的邻域更新

在迭代过程中，根据对当前个体邻域的多样性进行计算，若多样性好，则对邻域个体以一定概率进行局部搜索；若多样性差，则进行多样性增强。在邻域多样性的计算过程中，需要对邻域个体进行对比，因为染色体长度较长，对每个基因点位进行对比需要花费很长时间，所以采用邻域个体的适应值作为比较对象。这样的对比方式能够节省多样性计算的时间，并且能够反映解空间上邻域个体的多样性。

邻域更新的具体步骤如下：

步骤1获取邻域个体的所有适应值集合，建立空集合non_repeat_set，进入步骤2。

步骤2遍历所有邻域个体的适应值，若该适应值在集合non_repeat_set中，则访问下一个个体适应值；若该适应值不在集合non_repeat_set中，则将其加入到该集合。遍历完后进入步骤3。

步骤3计算non_repeat_set的大小，该集合表示所有不重复的个体，若该集合小于邻域大小的一半，则认为邻域多样性差，进入步骤4；否则，转步骤5。

步骤4标记适应值不在集合non_repeat_set中的邻域个体，用随机生成的个体替换该邻域个体。

步骤5遍历邻域中的个体，对当前个体生成一个0到1范围内的随机数，若大于局部搜索概率，则进入步骤6；否则，对下一个个体进行判断。

步骤6计算当前非支配解集中个体的拥挤度，随机选择拥挤度最大的一个个体与邻域个体进行交叉，交叉方式与2.2.3节中相同，返回适应值更优的一个个体作为新的邻域个体。

3 数值实验

3.1 实验环境

IMOEA/D算法在Intel Core i5 2.7 GHz CPU、16 GB RAM、Windows 10操作系统和Python编程环境下进行计算。

3.2 实验数据

针对RHFSP-CBPM，结合冷拔生产的特征，设计算例集进行实验，算例生成规则如表2所示，其中数量单位均为个，时间单位均为min，功率单位均为kW。

表2 算例表

3.3 实验设计

为验证优化模型的正确性和算法的优越性，设计了如下5个实验：

(1)IMOEA/D参数优化实验。设计正交试验确定算法参数。

(2)缓冲区大小对比实验。对比不同缓冲区大小的影响，确定连续式批处理机的合适缓冲区大小。

(3)工件等待时间对比实验。对比批次内工件等待时间的不同计算方式，验证考虑批处理机容量约束解码的有效性。

(4)算法策略验证实验。对比使用策略前后的算法对算例求解的效果，验证提出的策略的有效性。

(5)IMOEA/D性能验证实验。将设计的IMOEA/D与其他算法对比，验证IMOEA/D的优越性。

3.4 实验结果

3.4.1 IMOEA/D参数优化实验

IMOEA/D算法的参数对实验结果具有一定的影响，为了确定实验参数的大小，设计了如下的四因素三水平的正交试验。如表3所示，其中参数有：邻域大小与种群大小的比例关系(T)、交叉概率(Pc)、变异概率(Pm)，以及局部搜索概率(Pl)。选取按照表2规则生成的第一个实验算例进行正交试验，该算例有10个工件，6道工序，并且工件重入了1次，记为P10_6_1。

对比不同参数水平下的解的质量，需要将一组非支配解转化为一个综合目标值，计算综合目标值的计算方法详见文献[29]。对算例P10_6_1在不同参数水平下进行求解，得到的正交试验结果如表3所示。

结合表3正交试验结果，IMOEA/D算法的参数设置如下：种群规模(N)100，迭代次数(S)50次，邻域占比(T)为0.15，交叉概率(Pc)为0.9，变异概率(Pm)为0.2，局部搜索概率(Pl)为0.5。后续实验中IMOEA/D算法均使用上述参数设置。

表3 参数正交试验

3.4.2 缓冲区大小对比实验

在连续式退火炉的应用场景中，其往往有传送带状的前置缓冲区，来满足工件连续进入的需求。在现有考虑缓冲区大小的调度问题研究中，一般将缓冲区大小设置为批处理机容量的倍数或者其他固定值，仅将其作为一个约束条件，而未考虑该缓冲区大小是否合适。缓冲区大小对比实验将缓冲区分为5个等级进行对比，各等级缓冲区大小如表4所示，其中B是批处理机容量。

表4 缓冲区各等级大小

使用与3.4.1节中相同的算例P10_6_1进行实验，在每种缓冲区等级下，取IMOEA/D算法运行10次后得到的非支配解作为最终解。实验结果如图10和图11所示，在等级1的零缓冲约束下得到的调度方案，能耗和完工时间远大于另外4个等级。在实际生产中，除了少数工艺要求严格的零缓冲/等待约束，大部分情况下都是存在一定缓冲区的。在缓冲区等级为2和4时，得到的解具有较为良好的分布性，但是在整个解空间上，等级3和5得到的解更优。可以看到，在缓冲区等级3下，缓冲区大小等于批处理机容量大小，此时得到的解与无限缓冲的最为接近，综合表现较好，在图11箱线图的对比中，也可以看出等级3和5的分布最为接近。

缓冲区在生产过程中会占用一定的空间资源和生产资源，同时缓冲区的大小也会对调度的完工时间和能耗造成影响。在保证生产效率的同时，尽可能降低缓冲区的成本，能够给企业带来更大收益。实验结果表明，当缓冲区大小等于批处理机容量大小时，调度方案的效果已经接近无限缓冲的情况了，因此将缓冲区容量设置成批处理机容量大小较为合适。后续实验缓冲区大小均采用上述设置。

3.4.3 工件等待时间对比实验

除了2.2.2节解码中提出的工件等待时间计算方式外，赵玉芳等[25]在单机连续型批调度问题中，也提出了一个批次加工时间的计算公式，批次内工件间的等待时间等于该批次加工时间除以批处理机容量。为了验证本文的计算方式的有效性，使用算例P10_6_1，分别在解码中使用两种计算方式进行求解。实验结果如图12所示，其中计算方式1使用了式(20)的计算公式，计算方式2使用了文献[25]的公式。

3.4.4 算法策略验证实验

为了验证算法提出的策略的有效性，分别在完整算法策略、不使用多样性判断后的局部搜索和不使用多样性判断后的邻域更新策略这3种情况下进行对比实验。仍然使用P10_6_1算例作为测试算例，实验结果如图13所示，在多样性判断中，若仅采用一种策略，得到的解较为接近，但是都明显劣于采用二者结合的策略得到的解。在综合使用两种策略后，最终非支配解集的完工时间和能耗目标都得到了优化。

3.4.5 IMOEA/D性能验证实验

为了验证IMOEA/D的性能，选用MODE算法、MOPSO算法和经典的多目标算法NSGA-Ⅱ作为对比算法，其中MODE算法是文献[34]提出的求解带缓冲区批调度问题的MODE算法，MOPSO算法是文献[4]提出的求解可重入批调度问题的V-NSPSO算法。分别使用4种算法求解表2生成的10个算例。

使用超体积(HV)指标来比较不同算法的综合性能，选用坐标原点作为参考点，将Pareto集归一化后，计算Pareto集与参考点围成的区域体积大小，得到HV值。四种算法的HV指标对比结果如表5所示，其中加粗的表示最优结果，IMOEA/D算法在大部分算例中表现出了较好的综合性能。

表5 算法HV指标对比结果

使用世代距离(GD)指标比较不同算法的收敛性，选用参考点坐标原点作为参考点，将Pareto集归一化后，计算Pareto集与参考点的平均最小距离，平均距离越小的收敛性越好。GD指标对比结果如表6所示，IMOEA/D算法在大部分算例中都表现出最好的收敛性。

表6 算法GD指标对比结果

使用反转世代距离(IGD)指标比较不同算法得到的解的多样性，计算每个参考点到最近的解的距离的平均值，IGD值越小，说明解的多样性越好。由于问题没有已知的最优Pareto前沿，因此采用ISHIBUCHI等[35]提出的方法，通过分解的方式生成一组Pareto前沿面，来辅助计算IGD指标。最终得到的IGD指标对比结果如表7所示，IMOEA/D算法在大部分算例都表现出较好的多样性。

表7 算法IGD指标对比结果

将IMOEA/D依次与另外3个算法的各指标计算值进行Wilcoxon符号秩检验，设置置信水平α=0.05，若所求得P值小于其给定的显著性水平，则拒绝零假设，H值为1。Wilcoxon符号秩检验结果如表8所示，检验结果表明，IMOEA/D求解10个算例的各指标结果与另外3个算法有显著差异，IMOEA/D得到的Pareto解集在大部分情况下明显优于另外3种算法。

表8 Wilcoxon符号秩检验结果

为了直观展现调度结果，使用IMOEA/D求解算例P10_6_1得到的一个Pareto解的甘特图如图14所示。图中机器12-15是冷拔阶段的冷拔机，机器16是批处理阶段的连续式批处理机。每个矩形色块代表一个工序在机器上加工，色块内的数字表示对应的工件-工序编号。在整个调度过程的离散加工阶段，冷拔机上工件的加工时间占据了大部分的完工时间；而在批加工阶段，工件在批处理机上依次进入和离开。可以看到，调度结果中，连续式批处理机的利用效率很高，算例P10_6_1的批处理机容量为4，甘特图中每一个批次都达到了满批，并且没有违背缓冲区和批处理机容量的约束。根据上述实验对比结果可知，所提出的IMOEA/D算法能够有效地求解RHFSP-CBPM问题。

4 结束语

本文将无缝钢管的冷拔生产过程抽象为带连续式批处理机的可重入混合流水车间调度问题。首先，综合考虑缓冲区和批处理机容量等约束条件，为该问题建立了数学优化模型，以优化完工时间和批处理机能耗。然后，设计了IMOEA/D作为多目标优化算法进行求解。根据问题的可重入特征设计了基于工序的编码，考虑缓冲区大小约束和批处理机容量约束设计了解码算法，开发了针对染色体的交叉变异算子，并根据邻域多样性设计了局部搜索和多样性增强策略。最后，进行了5个实验。通过正交试验确定了算法的最佳参数设置；通过缓冲区大小对比实验确定了批处理机缓冲区的合适大小，当批处理机缓冲区大小等于批处理机容量，能够在保证得到较好调度方案的同时节约缓冲区资源；通过工件等待时间对比实验表明了本文设计的等待时间计算方式的有效性，在满足批处理机容量的情况下，工件能够更及时地进入批处理机，进而减少批处理机能耗；通过算法策略验证实验，证明了所提算法改进策略的有效性。在最后一个实验中，通过与不同算法的比较，验证了IMOEA/D相对其他算法的优越性，所提出的IMOEA/D能够有效求解RHFSP-CBPM。

在进一步的研究中，可以考虑其余工艺阶段的工件准备时间和缓冲区大小约束，以及更有效的智能算法的开发。