2. 红云红河(烟草)集团有限责任公司昆明卷烟厂, 云南 昆明 650202
2. Kunming Cigarette Factory, Hongyun Honghe Tobacco (Group) Co. Ltd., Kunming 650202, China
0 引言
并行机调度问题(parallel machine scheduling problem，PMSP)是一种经典调度问题，广泛应用于卷烟加工、注塑成型和纺织生产等行业中。根据并行机调度中机器性能的差异，可将并行机调度问题划分为相关并行机调度问题和不相关并行机调度问题(unrelated parallel machine scheduling problem，UPMSP)，与此同时考虑在实际生产加工过程中，批量加工方式占比更多，相比单工件并行机调度问题的研究，不相关并行机批量调度问题(unrelated parallel machine batch scheduling problem，UPMBSP)求解难度更大且更具有实际研究价值。
现如今关于并行机调度问题的研究往往以单目标优化为主，以最小化最大完工时间[1-9]为目标的并行机调度研究最多，其次是最小化加权完工时间[10]、总能耗[11-12]、总拖期时间[13-16]、总加权交货时间[17]、总运输时间[18]及总成本[19-20]等，而在实际工况下优化目标通常不唯一，多目标优化问题会导致整个问题变得更加复杂，现有文献中对多目标并行机调度问题的研究主要有：最小化完工时间、流水时间及延迟时间[21]、最小化总延迟时间与总能耗[22-24]、最小化最大完工时间与生产成本[25]等，然而上述文献均采用单工件生产方式，缺少对于分批调度[26-27]的应用研究，因此本文结合实际生产，将批量生产过程中工件种类切换次数[28]作为优化目标之一，通过对切换次数的优化，以降低因频繁切换工件种类而导致非生产用时的增加。与此同时，假设所有并行机在同一时刻开始加工生产，供能系统会均衡的为每台机器提供能源，若某台或多台机器停止运行则会出现供能不稳定的现象，为降低能源损耗，保证所有工作人员在岗时间一致性，本文提出车间内所有机器统一启停这一指标作为另一个优化目标，下文将该指标描述为启停评价函数。
综上所述，本文将从生产实际出发，考虑机器加工约束的不相关并行机调度问题中多个目标即工件种类切换次数和启停评价函数，为提高车间总生产效率，各机器在同一时刻同时启动，且每台机器可加工工件种类数量不唯一，当工件种类切换次数减少时，将会导致启停评价函数受到影响，使得相应优化目标函数彼此冲突，因此需要在实际加工生产中充分考虑，从而增加了问题的求解难度。对于研究工件种类切换次数和启停评价函数的多目标不相关并行机分批调度问题具有理论意义和实际工程价值。
1 问题描述考虑机器加工约束的不相关并行机分批调度问题描述：有n个种类的工件J1，J2，…，Jn，每个种类工件的加工数目N1，N2，…，Nn，由m台不相关并行机M1，M2，…，Mm加工，各类工件可分为若干个批次，同一批次内工件种类相同，批次数目用Bi表示，各批次包含的工件批量数为Sil，工件可以在指定的几台并行机上完成加工，每个种类的工件Jj在不同的并行机上加工时间TkjP各不相同，主要取决于并行机Mk的加工性能，加工过程中主要考虑工件种类切换次数以及机器启停评价函数两个优化目标，以下针对本文所选优化目标函数进行描述，各参数意义如表 1所示。
| 参数 | 含义 |
| m | 并行机数目 |
| n | 工件种类数目 |
| Ni | 工件i加工数目，i∈{1，2，…，n} |
| Bi | 工件i批次数目，i∈{1，2，…，n} |
| Sil | 工件i第l批次工件批量数目，i∈{1，2，…，n} |
| Mkj | 并行机k加工工件j则为1，否则为0 |
| Tmax | 最后完工机器完工时间 |
| Tk | k机器完工时间 |
| TkjS | k机器加工j种类工件的开始时间 |
| TkjP | k机器加工j种类工件的加工时间 |
| TkjE | k机器加工j种类工件的结束时间 |
| Dkj | k机器加工j种类工件的计划产量 |
| j | 工件种类编号，j∈{1，2，…，n} |
| k | 机器编号，k∈{1，2，…，m} |
工件种类切换次数是指某一机器在生产加工过程中因更换工件种类而统计的切换次数，即该机器在分批加工时，批次切换的次数。所有机器切换工件加工种类的次数和即为工件种类切换次数，这里用H表示：
|
(1) |
其中，
|
启停评价函数表示为各机器与最后完工机器完工时间差值的和，这里用Q表示：
|
(2) |
其中，Tmax表示最后完工机器所用加工时间即最大完工时间，Tk表示Mk机器完工时间。
综上所述，本文考虑的目标函数：
|
(3) |
|
(4) |
此外，应同时满足如下约束条件：
|
(5) |
|
(6) |
|
(7) |
|
(8) |
|
(9) |
|
(10) |
|
(11) |
式(5)保证同一类型工件在各批次加工时的批量和等于该工件加工总量；式(6)表示同类型工件在同一时刻可由一台或多台并行机同时加工；式(7)表示每种类型的工件都可以至少由一台并行机加工完成；式(8)表示总完工时间由最后完工机器决定；式(9)表示同一台并行机在同一时刻只能加工生产一个工件；式(10)表示每个工件加工时不可中断；式(11)表示加工过程中，各类工件的加工数量是已知的，开始加工后则不可更改。
2 面向UPMBSP的多目标启发式狼群算法目前，在车间调度智能优化算法的研究中，狼群算法[29]广泛应用于车间调度[30]、作业调度[31]、模具模台分配[32]等领域，印证了该算法具有较好的性能表现。针对本文提出的车间调度问题，考虑狼群算法并行性以及较好的全局搜索能力等特点，提出多目标启发式狼群算法(multi-objective heuristic wolf pack algorithm，MOHWPA)进行求解，该算法是在狼群算法的基础上，引入两阶段搜索概率变化机制，并对狼群算法中智能行为机制重新设计，结合分批调度特征，设计新型编解码方式及分批调整学习机制，解决不相关并行机分批调度问题。接下来将对MOHWPA进行详细描述。
2.1 编码及解码考虑工件种类切换次数和启停评价函数两个目标的不相关并行机分批调度问题由工件分批、批次排序、机器分配三个方面组成，提出一种不规则实数矩阵编码方式，该编码中矩阵的行、列分别由机器数目和工件种类决定，矩阵中每一个实数的整数部分表示加工机器编号，实数所在列决定加工工件种类，小数部分决定工件在该机器上的加工数量。在种群生成时，个体编码均根据编码原则及约束条件生成，以确保个体编码的合理性。如图 1(a)所示，以4台并行机加工3种工件为例，由问题规模决定实数矩阵编码为4行3列，图中所示4×3矩阵为一个完整的编码。
|
| 图 1 编码方式及LRLS示意图 Fig.1 Encoding and LRLS schematic |
图 1(a)中编码含义：第一列表示A类工件在M1、M3与M4上加工，若A类工件加工数量为NA，则M1加工A类工件的个数为(0.6/(0.2+0.4+0.6))NA，同理可知其它种类工件在各机器上的加工数量。
解码过程为：根据不规则实数矩阵编码方式，确定各类工件加工批次、批量及排序。
2.2 初始种群产生本文采用3种方式相融合生成初始种群，分别是随机搜索方式(random search method，RSM)，列表反向学习策略(list-based reverse learning strategy，LRLS)和基于机器加工效率的启发式策略(heuristic strategy based on machine processing efficiency，HSBMPE)。3种方式生成的种群个体数目之比为RSM∶ LRLS∶HSBMPE=x∶x∶1(总规模为2x+1)，x为迭代过程中的种群规模，以下针对3种方式进行说明。
RSM：根据上文所提出编码方式随机生成x个个体。
LRLS：根据每种工件可加工机器编号列表对随机生成的x个个体进行反向学习。反向学习策略的变化过程如图 1(b)所示。例如A类工件在进行反向学习时，工件若在M3上加工，将可用机器列表编号降序排列，对应位置编号即为反向学习后机器编号，M3机器对应M2机器，小数位按照取相反数后再加1的方式进行反向学习。
HSBMPE：考虑不相关并行机调度问题中，各类工件在各机器上的加工效率各不相同，提出基于机器加工效率的启发式策略，该策略是在生成初始种群时为每种工件选择加工效率最高的机器，加工数量按照机器数目进行均分。若工件j在机器Mk上加工效率为PkjE，则该方法的伪代码如算法1所示。
算法1 HSBMPE
Input：n，m
Output：Mkj
1： initialize：j⊂n，k⊂m
2： for k=1，2，…，m；j=1，2，…，n do
3： if find max PkjE then
4： Mkj=1
5： else
6： Mkj=0
7： end if
8： end for
上述3种初始种群融合的方式增加了初始种群的多样性，相关证明详见本文3.3节。
2.3 MOHWPA智能行为机制设计通过上述方法生成初始种群，考虑多个优化目标，在寻优过程中根据Deb等[33]提出的方法，对初始种群进行Pareto分级，根据等级不同进行排序并保留前x个种群进行狼群分类。
狼群分类：首先随机选择Pareto前沿面上的一个个体定义为头狼；其次根据探狼比例因子γ随机选取[x/(γ+1)，x/γ]之间整数ε做为探狼个体数目，其中x表示当代种群中个体总数；最后在排序后的个体中选取前ε个个体为探狼，剩余个体即为猛狼。该分类方式研究的主要目的是选出较优个体带领其余个体在其解空间内朝着最优个体方向进行搜索，以减少因盲目搜索而导致搜索时间过长的问题。
游走机制：人工狼在分类后，探狼个体执行游走机制，首先考虑到本文构建的不相关并行机分批调度模型是离散模型，在个体执行游走机制时不规定游走步长，与此同时引入两阶段搜索概率变化机制，改变游走概率PWander，即迭代初期与后期的游走概率分别为PWander1、PWander2，该步骤的目的是游走初期使个体多样性增加，游走后期使个体趋于稳定状态；其次，变异后个体编码小数位由两种方式生成，其一是随机生成，其二是设置为常量c，小数位决定了每种工件的加工数量，是分批调度问题的重要组成部分，随机方式生成的小数位编码能使个体编码多样性增大，从而为分批调整学习机制做充足的准备。游走机制示意图如图 2所示。
|
| 图 2 游走机制示意图 Fig.2 The schematic diagram of walking mechanism |
召唤机制：分类后的猛狼编码中每一列代表工件加工种类，由于猛狼个体要以较快的速度接近最优个体，因此召唤时局部邻域搜索方法即把每个种类的编码看成一个整体，在该种群中随机找另一个个体进行相应编码交换。鉴于在交换过程中整个种类工件的编码保持不变，进而使较优的机器分配及工件分批方案保留下来，使其更好的执行围攻机制。召唤机制示意图如图 3所示。
|
| 图 3 召唤机制示意图 Fig.3 The schematic diagram of calling mechanism |
围攻机制：将游走后的探狼个体与召唤后的猛狼个体同时进行围攻行为，执行全局邻域搜索，即选择个体中的某一个或多个种类的编码和对应头狼中的编码进行交换，围攻机制示意图如图 4所示。
|
| 图 4 围攻机制示意图 Fig.4 The schematic diagram of siege mechanism |
由于上述方法中针对分批过程优化较少，本文提出一种分批调整学习机制(batch adjustment learning mechanism，BALM)，将围攻后的种群与初始种群共同进行非支配排序与Pareto分级，挑选种群中前x个个体执行分批调整学习机制，下面2.4节将对该机制做详细介绍。
2.4 分批调整学习机制该策略由两个部分组成，其一是调整可用机器数量，即编码中整数位；其二是对工件加工数量进行调整，即调整编码中小数位，以解决不相关并行机分批调度问题中的工件数量分批优化问题。
重置随机数α∈(0，1)，β∈(0，1)，根据随机变量α、β和常量δ进行以下操作。
分批调整学习机制伪代码如算法2所示。
算法2 BALM
Input：α，β，δ
Output：Adjusted coding
1： initialize：α，β randomly；δ=constant
2： if α≤δ then
3： find(kfirst，klast，jfeasible)
4： if β≤δ then
5： Mkfirstjfeasible=1
6： else
7： Mklastjfeasible=0
8： end if
9： if β≤δ then
10： random increase DMkfirstjfeasible
11： else
12： random decrease DMklastjfeasible
13： end if
14：end if
1) 若α≤δ，则执行变整数位调整，目的是调整机器加工工件类型范围；若随机数β≤δ，在最先完工机器kfirst对应的可加工工件类型范围内，随机且不重复增加一种工件类型jfeasibale，若随机数β>δ，在最后完工机器klast对应的可加工工件类型范围内，随机减少一种工件类型jfeasibale，整个调整过程中工件的加工数量通过随机方式确定。
2) 若α>δ，则执行变小数位调整，目的是优化工件分批数量；若随机数β≤δ，则增加最先完工机器kfirst上所有类型工件的加工数量Dkfirstjfeasible，若随机数β>δ，则减少最后完工机器klast上所有类型工件的加工数量Dklastjfeasible。
在执行分批调整学习机制时，调整小数位的过程中会有一定概率造成编码不再合法，即编码整数位超出机器编号可用范围，针对此情况调整该工件类型所有编码，直至编码合法化为止。
2.5 算法步骤算法流程图如图 5所示。
|
| 图 5 MOHWPA流程图 Fig.5 The flowchart of MOHWPA |
MOHWPA的主要步骤描述如下：
Step 1 采用3种方法(RSM、LRLS、HSBMPE)融合生成初始种群。
Step 2 将初始种群根据非支配排序，进行Pareto分级，同等级的个体计算拥挤度，根据Pareto等级以及拥挤度淘汰多余个体，将非支配个体存储在外部空间Ω中。
Step 3 外部空间Ω中个体进行狼群分类操作。
Step 4 根据游走、召唤机制对分类后的探狼和猛狼种群进行相应的局部搜索。
Step 5 根据围攻机制对游走和召唤后的种群进行全局搜索，并将搜索后种群送入外部空间Ω中。
Step 6 全局搜索后的种群根据BALM进行调整，调整后的种群送入外部空间Ω中。
Step 7 对外部空间Ω中个体进行非支配排序，淘汰多余个体。
Step 8 满足终止条件，则终止程序，否则转至Step 3。
在Pareto淘汰及保优过程中，考虑到优化目标中工件种类切换次数的目标函数值为整数，Pareto分级时会把相同工件种类切换次数的个体归类为同一等级，而这些个体中启停评价函数值越小越好，因此，若工件种类切换次数值相同，则保留启停评价函数值最小个体，使算法计算复杂度降低。
MOHWPA具有以下特点：
1) 3种初始种群的构建方式，增加种群多样性。
2) 分别对探狼和猛狼个体采用差异化局部邻域搜索方式同时进行搜索，提高搜索效率。
3) 两种搜索方式(围攻机制、分批调整学习机制)对全局进行邻域搜索，扩大可行解搜索范围。
4) 改进整数解Pareto非支配排序保优策略降低了算法的计算复杂度。
3 计算实验为验证本文所提算法求解以工件种类切换次数和启停评价函数为目标的不相关并行机分批调度问题的性能，本文根据实例问题进行了大量仿真优化实验，该问题来自某大型卷烟厂，该卷烟厂卷包车间为典型的不相关并行机分批调度问题，有机组32台，对应的供丝风管数有17个，每台机组的加工能力各不相同，与加工的卷烟品牌具有相关性，每个风管连接一定数量的机组，符合本文中所研究考虑机器加工约束的不相关并行机分批调度问题模型，实验中考虑卷烟品牌切换次数即工件加工种类切换次数，以及启停评价函数两个优化目标。
所有测试实验均用Plant Simulation软件建立仿真模型，Simtalk 2.0语言编写优化算法程序，仿真与优化模型框架如图 6所示。
|
| 图 6 仿真优化模型框架 Fig.6 Simulation optimization model framework |
本文将Pareto非支配解的个数NS(单位：个)，反世代距离IGD、解间距SP、运行时间RT(单位：s)作为评价算法的性能指标，其中反世代距离和解间距的定义如下。
反世代距离IGD：反世代距离表示的是真实Pareto前沿面上的解与Pareto前沿面上解的欧氏距离，不仅可以反映算法的收敛性而且还可以反映算法的多样性，反世代距离值越小说明算法的综合性能越好。
|
(12) |
式(12)中，
解间距SP：反映算法多样性的重要指标，解间距越小表明算法解的多样性越好，解间距的计算方法为
|
(13) |
式(13)中，
为了使MOHWPA发挥到最佳状态，使参数设置更加严谨科学，本文采用正交实验对算法迭代过程中种群规模x、探狼比例因子γ、两阶段搜索概率变化机制中概率参数PWander1及PWander2进行设计，正交实验中算例选用某卷烟厂卷包车间3日生产计划，生产加工3种品牌卷烟，并以反世代距离IGD值作为性能参考指标。考虑迭代初期游走概率越大越能增加种群多样性，迭代后期为了保持种群整体稳定性而调低游走概率，并结合文[30]设计如表 2中各因素水平；根据L9(34)正交表设计九组实验如表 3所示；每组实验中算法迭代次数Gmax=150，且运行3次取平均值，记录实验结果数据如表 3中IGD所示。
| 参数 | 水平 | ||
| 1 | 2 | 3 | |
| x | 20 | 30 | 40 |
| γ | 1 | 2 | 3 |
| PWander1 | 0.7 | 0.8 | 0.9 |
| PWander2 | 0.3 | 0.4 | 0.5 |
| 编号 | 水平 | IGD | |||
| x | γ | PWander1 | PWander2 | ||
| 1 | 1 | 1 | 1 | 1 | 30.8 |
| 2 | 1 | 2 | 2 | 2 | 22.2 |
| 3 | 1 | 3 | 3 | 3 | 21.0 |
| 4 | 2 | 1 | 2 | 3 | 15.8 |
| 5 | 2 | 2 | 3 | 1 | 12.7 |
| 6 | 2 | 3 | 1 | 2 | 11.8 |
| 7 | 3 | 1 | 3 | 2 | 12.3 |
| 8 | 3 | 2 | 1 | 3 | 20.8 |
| 9 | 3 | 3 | 2 | 1 | 17.5 |
根据正交实验表格中IGD的值计算出各参数的响应值如表 4所示，最终得出在MOHWPA中参数设置如下：每代保留个体数x=30，探狼比例因子γ=3。两阶段搜索概率变化机制中前0.5Gmax次迭代中游走概率PWander设置为PWander1=0.9，剩余迭代中游走概率PWander2=0.4。
| 水平 | x | γ | PWander1 | PWander2 |
| 1 | 24.67 | 19.63 | 21.13 | 20.33 |
| 2 | 13.43 | 18.57 | 19.6 | 15.43 |
| 3 | 16.87 | 16.77 | 15.33 | 19.2 |
| 极差 | 11.24 | 2.86 | 5.8 | 4.9 |
| 等级 | 1 | 4 | 2 | 3 |
假设采用两种编码方式生成初始种群，分别是随机方式与采用RSM+LRLS+HSBMP的方式，两种方式均生成2x+1个个体，该算例来自某卷烟厂卷包车间3日生产计划，生产加工3种品牌卷烟，迭代过程中种群规模已由正交实验得出，即x=30，独立重复实验10次取最优，所得到的个体两个目标函数适应度箱型图如图 7和图 8所示。
|
| 图 7 不同方式产生的个体F1值箱线图 Fig.7 Box-plot of individual F1 values generated in different ways |
|
| 图 8 不同方式产生的个体F2值箱线图 Fig.8 Box-plot of individual F2 values generated in different ways |
不同方式产生的个体F1值箱线图如图 7所示，虽然工件种类切换次数范围不变，但在25%~75%的值中，3种方式融合的初始种群占比更多；通过图 8可以看出，3种方式融合生成的初始种群个体启停评价函数值范围更广。由此可知，3种方式融合的方法生成的初始种群更具有多样性，从而有利于种群的迭代搜索。
3.4 对比实验设计对于多目标算法的研究，NSGA-Ⅱ有较快的运行速度和较好的收敛性能，是应用最广泛的多目标算法之一，而MODE也是一种在解决多目标问题上具有较优性能的多目标算法[34]，因此本文通过NSGA-Ⅱ、MODE与MOHWPA3种算法进行对比实验，对比算法中参数的选择参考文[34]，实例问题中假设连接同一风管的机组同时进行加工，且实验过程中不考虑机器故障检修时间。
为了更好地验证MOHWPA在解决UPMBSP时的求解性能，将该实验划分为小、中、大三种规模，每种规模具体设计如下：小规模数据来自3 d和7 d的生产计划，中规模数据来自10 d和15 d的生产计划，大规模数据来自25 d和30 d的生产计划，且每种规模各完成3个品牌和5个品牌产品的加工，根据各种规模实际算例进行仿真优化实验。由于每组实验独立运行1次有其随机性，因此将每组实验独立运行20次取最优解集。将实验结果根据各评价指标统计后填入表 5，表中编号D表示天数，CP表示卷烟品牌数目。30D5CP实际算例实验结果如表 6所示，并绘制Pareto解集散点图如图 9所示，与此同时列出优化后解集的最大完工时间如表 7所示。根据不同规模问题实验结果绘制箱线图，如图 10、图 11所示。
| 规模 | 编号 | NSGA-Ⅱ | MODE | MOHWPA | |||||||||||
| NS | IGD | SP | RT | NS | IGD | SP | RT | NS | IGD | SP | RT | ||||
| 小规模 | 3D3CP | 2 | 11.25 | 0.00 | 32.25 | 3 | 2.75 | 6.33 | 34.50 | 5 | 2.75 | 4.09 | 31.33 | ||
| 3D5CP | 5 | 19.86 | 13.30 | 35.02 | 4 | 6.14 | 0.20 | 34.75 | 8 | 0.43 | 8.21 | 33.50 | |||
| 7D3CP | 4 | 10.40 | 22.53 | 38.40 | 6 | 16.80 | 22.53 | 38.67 | 6 | 10.00 | 57.93 | 34.25 | |||
| 7D5CP | 3 | 5.67 | 134.51 | 44.50 | 2 | 66.67 | 0.00 | 46.00 | 5 | 23.00 | 80.19 | 43.67 | |||
| 中规模 | 10D3CP | 3 | 46.67 | 52.82 | 38.08 | 3 | 8.33 | 108.25 | 40.50 | 4 | 11.67 | 9.82 | 36.25 | ||
| 10D5CP | 8 | 96.33 | 21.83 | 45.33 | 4 | 99.33 | 2.50 | 44.82 | 5 | 0.00 | 62.61 | 40.88 | |||
| 15D3CP | 2 | 76.50 | 0.00 | 43.40 | 2 | 114.50 | 0.00 | 46.40 | 2 | 0.00 | 0.00 | 41.13 | |||
| 15D5CP | 7 | 69.20 | 206.45 | 49.06 | 5 | 17.60 | 48.21 | 51.05 | 5 | 11.20 | 48.23 | 50.04 | |||
| 大规模 | 25D3CP | 3 | 210.50 | 20.98 | 47.33 | 2 | 54.00 | 0.00 | 49.25 | 3 | 21.75 | 18.49 | 48.33 | ||
| 25D5CP | 6 | 128.20 | 213.87 | 52.80 | 2 | 178.80 | 0.00 | 51.06 | 6 | 13.40 | 64.31 | 50.25 | |||
| 30D3CP | 2 | 25.75 | 0.00 | 50.75 | 3 | 47.75 | 20.10 | 49.33 | 4 | 1.75 | 6.03 | 50.34 | |||
| 30D5CP | 4 | 207.25 | 179.11 | 55.60 | 4 | 359.75 | 205.90 | 57.40 | 4 | 0.00 | 363.96 | 56.50 | |||
| 均值 | 4 | 75.63 | 72.12 | 44.38 | 3 | 81.04 | 22.35 | 45.31 | 5 | 8.00 | 60.32 | 43.04 | |||
| 序号 | NSGA-Ⅱ | MODE | MOHWPA | |||||
| F1/次 | F2/h | F1/次 | F2/h | F1/次 | F2/h | |||
| 1 | 0 | 2 326.11 | 0 | 2 085.93 | 0 | 1 419.68 | ||
| 2 | 1 | 2 156.16 | 3 | 1 672.80 | 2 | 616.58 | ||
| 3 | 2 | 859.08 | 4 | 1 344.89 | 4 | 379.90 | ||
| 4 | 4 | 379.90 | 8 | 903.45 | 6 | 346.81 | ||
|
| 图 9 算例30D5CP的Pareto解集 Fig.9 Pareto solution of the 30D5CP problem |
| 单位: d | |||||||||||||||||||||||||||||
| 序号 | 最大完工时间 | ||||||||||||||||||||||||||||
| NSGA-Ⅱ | MODE | MOHWPA | |||||||||||||||||||||||||||
| 1 | 29.08 | 24.63 | 22.61 | ||||||||||||||||||||||||||
| 2 | 23.29 | 23.34 | 28.06 | ||||||||||||||||||||||||||
| 3 | 21.34 | 25.86 | 22.24 | ||||||||||||||||||||||||||
| 4 | 22.24 | 24.63 | 21.34 | ||||||||||||||||||||||||||
| 均值 | 23.99 | 24.615 | 23.56 | ||||||||||||||||||||||||||
|
| 图 10 12组算例IGD值统计箱线图 Fig.10 Statistical box diagram of IGD values for 12 cases |
|
| 图 11 12组算例SP值统计箱线图 Fig.11 Statistical box diagram of SP values for 12 cases |
从不同规模实例仿真结果中可以得出以下结论，对于小规模算例，MOHWPA算法的Pareto非支配解集中，解的个数均多于其它两种算法，说明MOHWPA在小规模不相关并行机调度问题中能搜索到更多前沿解，从而可以提供更多调度方案。而在中规模算例中，MOHWPA解集的平均IGD值为5.7，相较于其它两种算法，其IGD平均值低，由此可知，在中规模不相关并行机调度问题中，MOHWPA的解综合性能较好。此外，在大规模算例中，Pareto非支配解集个数和IGD值均优于其它两种算法。与此同时，如图 9和表 7所示，MOHWPA中的个体启停评价函数指标更低、最大完工时间也得到一定的优化，由于算法设计时针对不相关并行机分批调度问题，且分批调整学习策略又能进一步做出针对性的调整，从而使MOHWPA在求解大规模问题上能发挥出更大的优势。
从整体上分析可以得出以下结论，首先，从前沿解的个数NS这一角度分析，MOHWPA相比另外两种算法平均提升46%，能得到较多的前沿解，在此基础上根据30D5CP实际算例实验结果数据绘制的Pareto非支配解散点图可以观察出MOHWPA前沿解相比其它算法更接近真实Pareto非支配解，使得MOHWPA的解集不仅在数量上表现出其优越性，其最优解集的质量也优于其它算法。其次，对比IGD值计算得出，MOHWPA的IGD值比其它算法平均低90%，依据IGD箱线图(图 10)也能得出，MOHWPA的IGD值总体偏低，因此可以说明MOHWPA相比NSGA-Ⅱ、MODE有着更好的综合性能。最后，比较3种算法SP值并结合统计箱线图(图 11)可以得出，MOHWPA的SP均值相比NSGA-Ⅱ平均降低20%，MODE的解间距值整体更小，说明MODE的解分布更加均衡。综合考虑以上因素得出MOHWPA的最优解集多样性相对较优。对比RT值可以看出，3种算法运行时间大致相同，结合表 7分析出，MOHWPA每个解集中的个体最大完工时间均可保证在规定的生产周期内完成加工任务，从而保证了算法的有效性。
综上所述，MOHWPA在求解不相关并行机分批调度问题时展现出较好的综合性能，在保证解集质量与运行时间的前提下使最优解个数增多，为调度人员提供更多可选调度方案。
4 结论本文设计一种多目标启发式狼群算法，针对考虑工件种类切换次数，以及启停评价函数的多目标不相关并行机分批调度问题进行求解。结合该问题特点，设计了不规则实数矩阵编码方式，算法融合了列表反向学习、基于机器加工效率的启发式策略以及两阶段搜索概率变化机制等，寻优过程中融入一种分批调整学习机制，有效防止算法陷入局部最优。通过实例仿真对比实验，本文所提算法相比于NSGA-Ⅱ、MODE算法具有更好地Pareto非支配寻优搜索能力，在解决该类车间调度问题上具有一定的有效性和优越性。
| [1] |
YEPES-BORRERO J C, VILLA F, PEREA F, et al. GRASP algorithm for the unrelated parallel machine scheduling problem with setup times and additional resources[J]. Expert Systems with Applications, 2020, 141. DOI:10.1016/j.eswa.2019.112959 |
| [2] |
LEI D, LIU M. An artificial bee colony with division for distributed unrelated parallel machine scheduling with preventive maintenance[J]. Computers & Industrial Engineering, 2020, 141. DOI:10.1016/j.cie.2020.106320 |
| [3] |
亓祥波, 朱云龙, 张丁一. 求解PFSP的双种群协同学习算法[J]. 控制与决策, 2017, 32(1): 12-20. QI X B, ZHU Y L, ZHANG D Y. Double population co-learning algorithm for permutation flow-shop scheduling problems[J]. Control and Decision, 2017, 32(1): 12-20. DOI:10.13195/j.kzyjc.2015.1568 |
| [4] |
JOVANOVIC R, VOβ S. Fixed set search application for minimizing the makespan on unrelated parallel machines with sequence-dependent setup times[J/OL]. Applied Soft Computing, 2021, 110[2021-11-05]. https://www.sciencedirect.com/science/article/pii/S1568494621004440. DOI: 10.1016/j.asoc.2021.107521.
|
| [5] |
KIM J, KIM H J. Parallel machine scheduling with multiple processing alternatives and sequence-dependent setup times[J]. International Journal of Production Research, 2021, 59(18): 5438-5453. DOI:10.1080/00207543.2020.1781278 |
| [6] |
LEI D, YI T. A novel shuffled frog-leaping algorithm for unrelated parallel machine scheduling with deteriorating maintenance and setup time[J]. Symmetry, 2021, 13(9). DOI:10.3390/sym13091574 |
| [7] |
LI K, CHEN J, FU H, et al. Parallel machine scheduling with position-based deterioration and learning effects in an uncertain manufacturing system[J/OL]. Computers & Industrial Engineering, 2020, 149[2021-12-10]. https://linkinghub.elsevier.com/retrieve/pii/S0360835220305556. DOI: 10.1016/j.cie.2020.106858.
|
| [8] |
韩忠华, 朱伯秋, 史海波, 等. 基于改进蝙蝠算法的柔性流水车间排产优化问题研究[J]. 计算机应用研究, 2017, 34(7): 1935-1938. HAN Z H, ZHU B Q, SHI H B, et al. Study for flexible flow shop scheduling problem based on advanced bat algorithm[J]. Application Research of Computers, 2017, 34(7): 1935-1938. DOI:10.3969/j.issn.1001-3695.2017.07.003 |
| [9] |
轩华, 郑倩倩, 李冰. 带不相关并行机和有限缓冲MHFS调度的混合启发式算法[J]. 控制与决策, 2021, 36(3): 565-576. XUAN H, ZHENG Q Q, LI B. Hybrid heuristic algorithm for multi-stage hybrid flow shop scheduling with unrelated parallel machines and finite buffers[J]. Control and Decision, 2021, 36(3): 565-576. |
| [10] |
贺俊杰, 张洁, 张朋, 等. 基于长短期记忆近端策略优化强化学习的等效并行机在线调度方法[J]. 中国机械工程, 2022, 33(3): 329-338. HE J J, ZHANG J, ZHANG P, et al. Related parallel machine online scheduling method based on proximal policy optimization with long short-term memory (LSTM-PPO) reinforcement learning[J]. China Mechanical Engineering, 2022, 33(3): 329-338. DOI:10.3969/j.issn.1004-132X.2022.03.009 |
| [11] |
SABERI-ALIABAD H, REISI-NAFCHI M, MOSLEHI G. Energy-efficient scheduling in an unrelated parallel-machine environment under time-of-use electricity tariffs[J/OL]. Journal of Cleaner Production, 2020, 249[2021-12-21]. https://linkinghub.elsevier.com/retrieve/pii/S0959652619342635. DOI: 10.1016/j.jclepro.2019.119393.
|
| [12] |
XIAO Y, ZHENG Y, YU Y, et al. A branch and bound algorithm for a parallel machine scheduling problem in green manufacturing industry considering time cost and power consumption[J/OL]. Journal of Cleaner Production, 2021, 320[2021-11-12]. https://linkinghub.elsevier.com/retrieve/pii/S0959652621030638. DOI: 10.1016/j.jclepro.2021.128867.
|
| [13] |
PEREZ-GONZALEZ P, FERNANDEZ-VIAGAS V, GARCÍA M Z, et al. Constructive heuristics for the unrelated parallel machines scheduling problem with machine eligibility and setup times[J]. Computers & Industrial Engineering, 2019, 131: 131-145. |
| [14] |
ARIK O A, SCHUTTEN M, TOPAN E. Weighted earliness/tardiness parallel machine scheduling problem with a common due date[J/OL]. Expert Systems with Applications, 2021, 187[2021-09-18]. https://linkinghub.elsevier.com/retrieve/pii/S0957417421012719. DOI: 10.1016/j.eswa.2021.115916.
|
| [15] |
WANG X, LI Z, CHEN Q, et al. Meta-heuristics for unrelated parallel machines scheduling with random rework to minimize expected total weighted tardiness[J/OL]. Computers & Industrial Engineering, 2020, 14[2021-12-03]. https://linkinghub.elsevier.com/retrieve/pii/S0360835220302394. DOI: 10.1016/j.cie.2020.106505.
|
| [16] |
DIANA R O M, DE SOUZA S R. Analysis of variable neighborhood descent as a local search operator for total weighted tardiness problem on unrelated parallel machines[J/OL]. Computers & Operations Research, 2020, 117[2021-11-24]. https://www.sciencedirect.com/science/article/pii/S0305054820300034. DOI: 10.1016/j.cor.2020.104886.
|
| [17] |
MÖNCH L, SHEN L. Parallel machine scheduling with the total weighted delivery time performance measure in distributed manufacturing[J/OL]. Computers & Operations Research, 2021, 127[2021-12-07]. https://www.sciencedirect.com/science/article/pii/S0305054820302434. DOI: 10.1016/j.cor.2020.105126.
|
| [18] |
陈魁, 毕利. 改进粒子群算法在考虑运输时间下的FJSP研究[J]. 系统仿真学报, 2021, 33(4): 845-853. CHEN K, BI L. Research on FJSP of improved particle swarm optimization algorithm considering transportation time[J]. Journal of System Simulation, 2021, 33(4): 845-853. |
| [19] |
LIU X, CHU F, ZHENG F, et al. Parallel machine scheduling with stochastic release times and processing times[J]. International Journal of Production Research, 2021, 59(20): 6327-6346. DOI:10.1080/00207543.2020.1812752 |
| [20] |
王柏琳, 李铁克, 王海凤. 安装时间和机器受限的订单接受与并行机调度[J]. 工程科学学报, 2019, 41(4): 528-538. WANG B L, LI T K, WANG H F. Order acceptance and scheduling on parallel machines with setup time and machine-eligibility constraints[J]. Chinese Journal of Engineering, 2019, 41(4): 528-538. |
| [21] |
裴小兵, 张睿, 于秀燕. 混合萤火虫算法求解多目标置换流水车间调度问题[J]. 信息与控制, 2020, 49(4): 478-488. PEI X B, ZHANG R, YU X Y. Hybrid firefly algorithms for multi-objective permutation flow shop scheduling problem[J]. Information and Control, 2020, 49(4): 478-488. |
| [22] |
SOLEIMANI H, GHADERI H, TSAI P W, et al. Scheduling of unrelated parallel machines considering sequence-related setup time, start time-dependent deterioration, position-dependent learning and power consumption minimization[J/OL]. Journal of Cleaner Production, 2020, 249[2021-12-07]. https://linkinghub.elsevier.com/retrieve/pii/S0959652619342982. DOI: 10.1016/j.jclepro.2019.119428.
|
| [23] |
雷德明, 潘子肖, 张清勇. 多目标低碳并行机调度研究[J]. 华中科技大学学报(自然科学版), 2018, 46(8): 104-109. LEI D M, PAN Z X, ZHANG Q Y. Researches on multi-objective low carbon parallel machines scheduling[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2018, 46(8): 104-109. |
| [24] |
潘子肖, 雷德明. 基于问题性质的分布式低碳并行机调度算法研究[J]. 自动化学报, 2020, 46(11): 2427-2438. PAN Z X, LEI D M. Research on property-based distributed low carbon parallel machines scheduling algorithm[J]. Acta Automatica Sinica, 2020, 46(11): 2427-2438. |
| [25] |
YEPES-BORRERO J C, PEREA F, RUIZ R, et al. Bi-objective parallel machine scheduling with additional resources during setups[J]. European Journal of Operational Research, 2021, 292(2): 443-455. |
| [26] |
HAM A. Flexible job shop scheduling problem for parallel batch processing machine with compatible job families[J]. Applied Mathematical Modelling, 2017, 45: 551-562. |
| [27] |
LIU S, PEI J, CHENG H, et al. Two-stage hybrid flow shop scheduling on parallel batching machines considering a job-dependent deteriorating effect and non-identical job sizes[J/OL]. Applied Soft Computing, 2019, 84[2021-12-28]. https://linkinghub.elsevier.com/retrieve/pii/S156849461930482X. DOI: 10.1016/j.asoc.2019.105701.
|
| [28] |
李丹, 周延辉, 周明, 等. 基于遗传算法的卷烟换牌排产与优化设计[J]. 烟草科技, 2019, 52(5): 94-99. LI D, ZHOU Y H, ZHOU M, et al. Scheduling of cigarette brand change and its optimization based on genetic algorithm[J]. Tobacco Science & Technology, 2019, 52(5): 94-99. |
| [29] |
吴虎胜, 张凤鸣, 吴庐山. 一种新的群体智能算法——狼群算法[J]. 系统工程与电子技术, 2013, 35(11): 2430-2438. WU H S, ZHANG F M, WU L S. New swarm intelligence algorithm-wolf pack algorithm[J]. Systems Engineering and Electronics, 2013, 35(11): 2430-2438. |
| [30] |
谢锐强, 张惠珍. 求解置换流水车间调度的离散狼群算法[J]. 控制工程, 2020, 27(2): 288-296. XIE R Q, ZHANG H Z. Discrete wolf pack algorithm for permutation flow shop scheduling problem[J]. Control Engineering of China, 2020, 27(2): 288-296. |
| [31] |
何李, 陶翼飞, 罗俊斌, 等. 基于两阶段狼群算法的AS/RS作业集成优化[J/OL]. 中国机械工程. (2021-12-08)[2022-02-25]. http://kns.cnki.net/kcms/detail/42.1294.TH.20211207.1300.010.html. HE L, TAO Y F, LUO J B, et al. The job integrated optimization of automated storage/retrieval systems based on two-stage wolf pack algorithm[J/OL]. China Mechanical Engineering. (2021-12-08)[2022-02-25]. http://kns.cnki.net/kcms/detail/42.1294.TH.20211207.1300.010.html. |
| [32] |
韩忠华, 刘约翰, 李曼, 等. 改进狼群算法求解模具在模台上组合分配问题[J]. 系统仿真学报, 2021, 33(1): 127-140. HAN Z H, LIU J, LI M, et al. Improved wolf pack algorithm for distribution of molds on molds table[J]. Journal of System Simulation, 2021, 33(1): 127-140. |
| [33] |
DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. |
| [34] |
周炳海, 顾佳颖. 考虑多资源约束的非等效并行机节能调度算法[J]. 东北大学学报(自然科学版), 2019, 40(3): 403-408. ZHOU B H, GU J Y. An energy-saving scheduling algorithm for non-identical parallel machines with multi-resource constraints[J]. Journal of Northeastern University (Natural Science), 2019, 40(3): 403-408. |