带并行批处理机的柔性作业车间调度问题研究

刘 蓉，周 林，王 朝，唐红涛，张海涛

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

作业车间调度问题(job shop scheduling problem, JSP)是先进智能制造领域研究中基础且重要的问题，是对生产过程进行作业计划和协调。先进的调度方法能为企业提高生产效益，其主要任务是在特定的约束下，确定工件的加工顺序和加工设备，以保证所选定的生产目标最优。柔性作业车间调度(flexible job shop scheduling problem ,FJSP)作为JSP的拓展，增加了加工机器选择的柔性，每个机台在每个时刻最多只能加工一个工件。在带有并行批处理的柔性作业车间调度问题中，约束更为复杂，求解更为困难。在该问题中，每个单处理机在每个时刻最多只能加工一个工件，但每个并行批处理机允许同时加工多个工件且同一批次的工件加工时间相同[1]。在工程上，带有并行批处理的柔性作业车间调度问题多存在于半导体企业及传统铸造企业，因此针对该问题寻求有效的调度机制和求解方案具有重要的应用价值。

柔性作业车间调度属于NP-Hard问题[2]，在汽车装配、纺织、化工材料加工及半导体制造等方面得到了广泛的应用[3]。启发式算法具有算法简单、通用性强、求解效率高等优点，被广泛应用于求解车间作业调度问题，如遗传算法(GA)[4]、粒子群优化算法(PSO)[5]、人工蜂群算法(ABC)[6]、灰狼算法(GWO)[7]等。对于柔性作业车间调度问题的研究出现了大量的研究成果，如在优化算法研究方面，ZHANG等[8]提出了一种有效的遗传算法来解决FJSP问题，能有效减少完工时间；XU等[9]设计了一种有效的教与学优化算法(TIBO)，并验证了其求解FJSP问题的优越性。在FJSP应用模型研究方面，SHEN等[10]考虑了带顺序相关调整时间的柔性作业车间调度问题；雷德明[11]研究了低碳策略下的柔性作业车间调度问题； ANDRADE-PINEDA等[12]考虑了双资源约束情况下的柔性作业车间调度问题。

对于在FJSP基础上引入批处理机的研究相对较少，如LI等[13]针对多台单处理机和一台批处理机的调度问题，提出了一种组合蚁群优化算法来求解该问题。HAM[14]以半导体行业为生产背景，提出带有并行批处理机的柔性作业车间调度问题，考虑了兼容的工件簇及工件间具有不同优先级的情况。LIAO等[15]研究了单机与并行机的集成并行分批调度问题，并根据优化的结构特性和分批规则，提出了一种新的带有变邻域搜索的人工免疫系统算法(AIS-VNS)。由于多台并行批处理机和单处理机对工件进行反复访问，增加了问题求解的难度，故针对该类问题的相关研究较少。因此笔者针对带有并行批处理机的柔性作业车间调度问题，构建了混合整数数学模型，设计了基于改进遗传算法的求解方法。在算法中，设计了分块式集成解码方法，在一次解码中解决工序排序、机器配置和工件组批3个子问题。基于聚类的选择算法保证了种群的多样性，基于关键路径的局部搜索算子能有效改善算法的局部搜索能力。最后，通过仿真实验来验证所提算法解决此类问题的可行性和有效性。

1 问题描述及模型构建

1.1 问题描述

原始的柔性作业车间调度问题(FJSP)可描述为n个工件(J1,J2,…,Jn)在m个加工资源(M1,M2,…,Mm)上加工，每个工件的加工工序都是确定的且不尽相同，每道工序可选择多个加工资源。每个加工资源都是单处理机，即每个加工资源在同一时刻只能加工一个工件。研究的目的是确定每道工序的加工资源、加工顺序及加工开始时间来使得整个调度系统的优化指标达到最优，故该组合优化问题可以分为两个子问题：①加工机器配置子问题，即确定每道工序在哪个加工机器上加工；②工件的工序排序子问题，即对分配好加工机器的工序进行排序。

在汽车模具铸造生产过程中，部分机器具有并行批处理的加工能力，其他则属于柔性作业车间中的单处理机范畴。汽车模具铸造生产调度问题可描述为带有并行批处理机的柔性作业车间调度问题，耦合了柔性作业车间的复杂性和并行批处理机的加工特点。在该问题中，部分单处理机被并行批处理机替代，即加工资源能同时加工多个工件，且加工的开始时间和结束时间相同。在并行批处理机加工时，属于该批所有工件的加工时间与该批的工件数量和吨位有关(加工时间不定)。此外，每个并行批处理机的加工能力有限，每批工件的尺寸不尽相同，且不能超过并行批处理机的加工能力(考虑差异工件尺寸)。在实际生产过程中，考虑到加工工艺约束，单处理机和批处理机有着不重叠性，即某个工件的工序的多个可选资源集中不会同时存在单处理机和批处理机，且可选集合中所有机器的加工能力相同。因此，该组合优化问题的划分可在原始两个子问题中增加一个子问题：并行批处理机的批次计划，即工件组批。

1.2 模型构建

(1)基本假设条件。①同一工件的同一工序在同一时刻只能被一台机器加工；②单处理机和批处理机有着不重叠性；③每道工序一旦开始就不能被中断；④不同工件的工序之间没有先后次序约束，同一工件的工序之间有先后次序约束；⑤所有工件在零时刻都可以被加工；⑥不同工件之间具有相同的优先级。

(2)模型参数说明。Ji表示第i个工件,i=1,2，…,n；Mk表示第k个机器,k=1,2,…,m；Wi表示第i个工件的重量；Oij表示第i个工件的第j道工序,j=1,2,…,Ni；Mij表示第i个工件的第j道工序的可选机器集；Sij表示工序Oij的加工开始时间；Cij表示工序Oij的完工时间；Bp表示并行批处理机p的加工批次集合，p表示该机器是并行批处理机；Cp表示并行批处理机p的加工能力；Tbp表示批处理机p的第b次任务的加工时间，b表示批次任务；Pijk表示工序Oij在单处理机k上的加工时间。

决策变量：Xijk=1表示工序Oij选择机器k，否则Xijk=0；Yij=1表示工序Oij可选机器集中有并行批处理机，否则Yij=0；Zij=1表示工序Oij可选机器集中有单处理机，否则Zij=0；Tijpb=1表示工序Oij在并行批处理机p的第b批中加工，否则Tijpb=0；Bibp=1表示并行批处理机p的第b批次任务中包含工件i，否则Bibp=0。

(3)数学模型。

(1)

s.t.

Sij+Xijk×Pijk≤Cij,∀i,j,k∈Mij

(2)

Cij≤Si(j+1),∀i,j

(3)

(4)

(5)

Yij+Zij=1,∀i,j

(6)

(7)

(8)

式(1)为该问题的优化目标，表示最小化最大完工时间；式(2)和式(3)表示工件工序加工有先后次序的约束；式(4)表示同一工件的同一工序在同一时刻只能被一台机器加工；式(5)表示如果工序Oij的可选机器集为并行批处机，则该工序能且只能被分配到一个批次b中；式(6)表示单处理机和批处理机的不重叠性；式(7)表示并行批处理机的加工时间与该批次的任务重量有关，f表示两者之间具有线性关系；式(8)表示每一批内各任务重量之和小于并行批处理机的加工能力。

2 改进遗传算法求解调度模型

带并行批处理机的柔性作业车间调度属于NP-hard问题，可行解的数量随着调度规模呈现指数级增加。混合整数规划[16]、拉格朗日松弛法[17]等一些精确方法虽然能在小规模问题中找到最优解，但是计算量大，耗时多，在求解大规模时受到限制。启发式算法虽然在求解上稳健性不足，但是其求解速度快，易于实现，计算复杂度低，也能得到满意解，故启发式算法在求解车间调度问题上得到了广泛的应用。遗传算法借用生物遗传特性，通过选择、交叉和变异等操作机制模拟生物在自然环境的遗传和进化过程，进而形成了自适应全局优化算法，具有较好的寻优能力和鲁棒性，被广泛应用于求解NP-hard问题，在车间调度方面的应用也十分广泛。为了进一步改进遗传算法的全局寻优能力，笔者设计一种基于聚类进化的群体搜索策略来增加种群的多样性。针对遗传算法存在的局部寻优能力差和“早熟”等缺陷，设计了基于关键路径的局部搜索算子来改善遗传算法的局部能力，可有效平衡遗传算法的全局探索能力和局部搜索能力。

2.1 编码和解码

染色体的编码与解码是解决调度问题的关键，编码就是将调度问题复杂的解空间用一种编码方式来表示，从而将调度问题的解空间映射到染色体的编码空间。解码并不是编码的反操作，而是将粒子编码中掺杂着调度模型的各种约束和调度信息与优化指标联系起来。

笔者采用基于机器和工序的分段编码方式，采用工序排序部分(OS)和机器选择部分(MS)来表示一个可行的调度方案。工序排序部分粒子长度为该次调度任务工序总数，对于第j次出现的工件号，就表示该工件的第j道工序；机器选择部分长度和工序排序部分一样，且顺序一一对应，每个机器码意味着该工序可选机器集的顺序号(非机器号)，这样就保证了种群可行解的产生。

分段编码能有效整合和解决工序排序和资源选择问题，但是不能直接反映并行批处理机的加工批次计划。因此，笔者设计了分块式集成解码规则来解决单处理机的工序排序和机器选择问题，以及并行批处理机的工件组批问题，从而在一次解码中得到混合活动调度方案。

为了更清晰地描述解码过程，给出一个带有并行批处理机的柔性作业车间调度算例，如表1所示。该案例中有2个工件，每个工件有5道工序。其中“—”表示该工序不可在该机器上加工，TBD表示加工时间不确定，与该批次的加工任务有关。该算例的一个可行解为:OS=[1,1,2,1,1,2,1,2,2,2],MS=[1,1,3,2,1,1,1,2,1,2]。

表1 带有并行批处理机的柔性作业车间调度算例

根据各个工件中工序是否属于批处理工序，可以将所有工序划分批处理工序块和单处理工序块。由表1可知，O12、O15、O22和O24是批处理工序，且O12和O22为同一道批处理工序，即有着相同可选加工机器集。同理，O15和O24也是同一道批处理工序。以这些批处理工序为分界线，可以将整个工序划分为工序块，如图1所示，该工序共划分为3个单处理块和2个批处理块，共5个工序块。根据各个工序块中工序与可行解的对应关系，将各个块的基因取出，按照对应的规则解码，可得到可行的活动调度方案。

图1 工序分块图

块2为批处理块，需要对该块的工序进行构建批量计划，其前驱工序块1驱动块2产生调度方案。前驱工序块的各个工件完工时间不一致，其不同完工时间对于批处理块2来说可被视为工件动态到达时间约束，又考虑到每个并行批处理机的加工能力有限(差异工件尺寸约束)，则批处理块可被视为考虑差异工件尺寸和动态到达时间的分批问题。为解决该分批问题，采用基于时间排序的任务补充分批规则，即对于每个批处理块的工序，将其前驱工序进行完工时间升序排序，依次并成一批，直到总重量超出并行批处理机的加工能力。对于批处理工序的机器选择问题，采用就近原则，即选择最快能有空闲时间机器，若有多台则随机选择一台。每个批次的加工开始时间为该批次所有任务的前驱工序最大完工时间，加工时间与每个批次的总重量呈正相关关系，即总重量越重加工时间越久。

块2中包含了工序O12和O22，前驱工序块的完工时间为[4,5],可选机器集为M4。为了方便分批，假设工件1和工件2的总重量不超过该机器的加工能力，加工时间固定为6。对该块进行分批，O12的前驱工序完工时间(4)较早先分入该批次，随后因满足机器的加工能力O22也会被划分到该批次，则O12和O22被划分为同一批次。此外，该批次的加工开始时间为前驱工序块的完工时间[4,5]中的最大值5。则块2的调度方案可描述为：O12和O22被划分为同一批次被并行批处理机M4在时刻5加工，其加工时间为6，完工时间矩阵为[11,11]。其他工序块可以按照对应的解码方式得到各自的调度方案，最终的调度甘特图如图2所示。

图2 调度算例的甘特图

2.2 选择算子

目前，遗传算法的选择算子主要有轮盘赌、随机竞争、随机联赛等方式。笔者为了拓宽种群的多样性，并避免基因特征相似的基因进行交叉造成冗余信息的传递，设计了一种聚类的选择方式。令聚类中心个数为K，具体选择操作步骤为：①将种群中个体的适应度值按照K-Means算法进行聚类分类，得到一个具有K个簇的模型，簇内的基因特征相似度较大，簇间的基因特征相似度较小；②除去最优基因所在的簇，其他簇内随机剔除个体，直至剩下的个体为种群的个体总数。

2.3 交叉算子

交叉的目的是将优良父代的信息保存下来，产生新的优良个体。为了避免相似信息的基因被冗余保存，考虑到簇间基因特征相似度较小，选择两个不同簇之间的父代进行交叉，这样就能保证种群基因信息的多样性。笔者针对工序的排序部分采用的是基于工件的POX交叉；针对机器选择部分设计了一种基于工序的机器交叉，如图3所示，具体步骤为：①随机生成变动工序集；②将P1中工序排序部分和非变动工序集对应的机器选择部分复制放在子代中；③将P2中变动工序集中对应的机器按照P1中的顺序依次插入到子代中。

图3 基于工序的机器交叉

2.4 变异算子

变异算子主要是为了增强算法的局部搜索能力，防止算法陷入局部最优解。针对工序排序部分的基因采用移位变异，即随机选择两个位置，将这两个位置的基因与其对应的机器基因一起进行位置互换。因为柔性作业调度中机器选择的柔性和加工时间的不一致，所以针对机器选择部分变异时，随机选择一个机器基因码，在此工序的机器集中选择最小加工时间的机器。针对工序部分和机器部分的两种变异算子，均能保证在变异后产生的是可行解。

2.5 局部搜索策略

遗传算法是一种自适应全局优化算法，存在局部寻优能力差和“早熟”等缺陷。在变异算子的基础上，为了进一步增强算法局部搜索能力，设计了一种基于关键路径的局部搜索策略。对于求解作业车间调度问题，关键路径直接影响一个调度方案的最大完工时间,通过扰动关键路径上的工序，有可能缩短当前种群的最大完工时间。其中，在关键路径上的工序视为关键工序，同一个机器上最大序列的连续关键工序组成关键块。

基于关键路径的局部搜索策略示意图如图4所示，虚线框内是一个关键块，针对关键块变动块首或者块尾的相对位置。在一次移动中，若当前块只有两道关键工序，则不做交换；若超过两道关键工序，则选择块首或者块尾作为移动源，随机选择与其不相邻的关键工序作为移动点，将移动源插入移动点之前或者之后，随后移动源和移动点之间的关键工序依次往前或者往后移动。

图4 基于关键路径的局部搜索策略

改进遗传算法求解模型的基本流程如图5所示。随机初始化种群，遗传算法进行全局寻优，得到全局最优解作为局部搜索算子的初始解，较好的初始解能有效保证局部搜索的性能，帮助算法跳出局部最优解，平衡全局搜索和局部搜索之间的矛盾。

图5 改进遗传算法流程图

3 仿真分析

改进遗传算法的运行环境:Intel Core i5, CPU 2.30 GHz, RAM 4.00 GB, Window 7的64位操作系统和Matlab 2015a。对比算法分别为GA算法、GA+聚类算法、GPSO算法[18],每个算法都有相关的参数设置。GA和GA+聚类两个算法的参数一致，GPSO算法的参数和文献[18]中的设置一致。改进遗传算法的参数设置为：迭代次数T=100，种群规模P=40，交叉概率Pc=0.8，变异概率Pm=0.1。

由于当前并没有标准测试算例可用来测试带并行批处理机的柔性作业调度问题，笔者以Brandimarte算例为基础，扩展成适用于带并行批处理机的柔性车间调度问题的测试算例，共生成10个测试算例，如表2所示。以算例1为例，算例规模为10个工件、6台单处理机和1台并行批处理机，批处理工序为第3道工序，该工序的可选择加工机器为M7，加工能力为80 kg，每个工件的重量为29-18-16-5-42-10-35-48-30-20。批处理工序的加工时间和该批的总重量呈正相关，如式(9)所示。前半部分表示与重量呈线性相关，后半部分表示该批每增加一个任务多花费0.5 h。

(9)

采用改进遗传算法和对比算法对10个测试算例进行测试，得到的实验结果如表3所示。为避免算法结果的偶然性，每个算例重复运行20次。为了保证公平性，其他算法的终止条件为改进遗传算法单独运行一次的时间。Cbest为20次中的最优解，Av(C)为平均值，dev表示改进遗传算法的最优解C*与4个算法中最优解C0的相对误差，其计算公式如式(10)所示，dev为0表示改进遗传算法得到的结果最优。

表2 扩展后的测试算例

表3 实验结果

(10)

由表3可知，改进遗传算法在10个算例中都取得不错的结果，获得了9个算例的最好解，相对误差都为0，且每个算例在均值的表现都有着明显的优势，具有较好的稳定性。尤其是与GA算法和GA+聚类算法相比，改进遗传算法的优势非常明显，验证了改进遗传算法的有效性。MK02_1算例最优值随迭代次数的变化曲线如图6所示，可知改进遗传算法和GA+聚类算法都增加了基于聚类的选择算子，与传统GA算相比有着更快的收敛速度，保证了种群的多样性。同时，改进遗传算法取得的最优解得到了明显改善，验证了局部搜索的有效性，能帮助算法跳出局部最优解。与GPSO算法相比，改进遗传算法在10个工件的MK01和MK02算例中有一定的优势，而在15个工件算例中改进遗传算法解的质量明显优过其他算法。

图6 MK02_1算例最优值随迭代次数的变化曲线

MK01_1算例的调度甘特图如图7所示，可知该批次计划共有4批，分别为工件{7,9}、{2,6,10}、{1,5}和{3,4,8}，均在机器M7上加工，最小完工时间为37.95 h。

4 结论

针对带有并行批处理机的柔性作业车间调度问题，以最小化最大完工时间为优化目标构建数学模型。针对问题特点，改进了遗传算法，设计了一种分块式集成解码规则，引入基于聚类的选择算子，设计了基于关键路径的局部搜索算子。仿真实验表明：①构建的混合整数模型能有效描述带有并行批处理机的柔性作业车间调度过程；②改进遗传算法易实现，高效率且能得到高质量解，能为该类调度问题提供合理有效的解决方案；③该模型贴近实际生产调度，求解方法简便高效，具有较强的实际应用价值。

图7 MK01_1算例的调度甘特图