混合流水线调度问题(hybrid flowline scheduling problem, HFSP)是一种典型的NP-hard 问题。在实际工业中,由于存储设备、物理空间和产品特性等限制,某些特定生产阶段间的缓冲区往往是有限的,甚至不存在缓冲区。例如在苹果酒的制作过程中,过滤阶段需要去除果汁中的果肉,由于过滤机器容量有限,果汁会停留在发酵阶段等待过滤完成,而最后过滤和装瓶阶段之间则没有限制[1]。由此可以提出一种部分生产阶段间存在无限缓冲区而其他阶段间没有缓冲区的混合流水线调度问题。
根据阶段间缓冲类型的不同,有关HFSP的研究可分为4种:带无限缓冲的HFSP、阻塞HFSP、带有限缓冲的HFSP和零等待HFSP。针对带无限缓冲的HFSP,王君妍等[2]考虑工件动态到达、运输时间和机器调整时间,提出改进自适应遗传算法以最小化总加权完成时间。针对阻塞HFSP,Qin等[3]考虑族顺序相关调整时间,提出迭代贪婪算法以解决集调度的makespan问题;Missaoui等[4]考虑交货时间窗,提出迭代贪婪算法以最小化总加权延迟和提前惩罚。针对带有限缓冲的HFSP,胡蓉等[5]提出一种混合探路者算法以同时最小化makespan和总能量消耗;Lin等[6]研究了带工件序列和运输时间的可重入HFSP,提出了混合和声搜索和遗传算法的启发式算法以同时最小化makespan和平均流程时间。针对零等待HFSP,裴小兵等[7]提出一种新型混合改进遗传算法以最小化makespan;Azaiez等[8]研究了由医院手术室调度引起的带阶段灵活性的两阶段问题,提出4种下界和4个启发式以最小化makespan。
针对组合缓冲约束的调度问题,在流水线环境下,Wang等[9]考虑无限缓冲和零等待约束假设每台机器上工件加工顺序相同,提出修正迭代贪婪算法;Riahi等[1]研究了无限缓冲和不同阻塞类型组合的调度问题,提出分散搜索算法以最小化makespan。在混合流水线环境下,钟祾充等[10]将集装箱码头调度视作三阶段混合零等待HFSP,提出改进离散布谷鸟算法以最小化makespan和总作业成本。为解决以最小化makespan为目标的HFSP,轩华等[11]考虑不相关并行机环境下组合无限缓冲和零等待约束,提出一种混合离散人工蜂群算法;Zhuang等[12]将自动化集装箱码头的智能装卸设备的调度问题视作带双向流和有限缓冲的阻塞HFSP,提出一种自适应大邻域搜索算法。
综上所述,现有研究已针对阶段间具有单一缓冲约束的HFSP取得了大量的成果,而阶段间组合不同中间缓冲约束的复杂车间环境下的HFSP,尤其是多目标问题的研究则相对较少。探索节能减排机制以减少机器负载,平衡生产效率和能源消耗,对于HFSP的研究具有重要意义。
本文以最小化最大完工时间和机器总能耗为优化目标,研究不相关并行机环境下的生产阶段间既有无限缓冲情况又有阻塞情况的HFSP(multi-objective hybrid flowline energy-saving scheduling problem with combined buffer constraints, MOHFESP-CBC),并提出一种改进多目标模因算法(improved multi-objective memetic algorithm, IMOMA)以近似求解该问题。
1 问题描述与模型
1.1 MOHFESP-CBC描述
所研究MOHFESP-CBC描述如下。生产线中有N个工件需依次经过S个生产阶段,每个阶段i包含Ui(k=1,2,…,Ui)台不相关并行机。每个工件j有不同的动态到达时间记为RTj(RTj≥0),即当工件到达生产系统后才能开始加工。工件j在生产阶段i的不同机器k上的加工时间取决于该工件以及用于加工该工件的机器。当工件完成前一阶段的加工后需要经运输后到达下一阶段才能开始加工。
上述S个生产阶段中,部分阶段间不存在缓冲区,即具有阻塞约束。将有阻塞约束的相邻生产阶段的前一阶段i记入阻塞阶段集,记为W,将集合W中所包含阶段数记为s,则无限缓冲阶段数为S-s。
在实际的加工过程中,机器能耗分为加工能耗和待机能耗。为减少机器的待机时间,所有机器开始加工首道工序时开机,末道工序完工时关机,阻塞期间由于机器未进行加工,算作待机状态。调度的目标是确定工件在各阶段的加工序列及机器分配以同时最小化最大完工时间和机器总能耗。
1.2 模型构建
定义Ui为阶段i的不相关并行机数;Pijk为工件j在阶段i的机器k上的加工时间;TTi为阶段i到下一阶段的运输时间;E为机器消耗总能量;
为阶段i的机器k加工所消耗的能量;
为阶段i的机器k待机所消耗的能量;
为阶段i的机器k的加工功率;
为阶段i的机器k的待机功率;T为总计划时间,时刻t∈{1,2,…, T};r为阶段i的机器k的加工工序序号, r∈{1,2,…, mik};H为一个很大的正数。
定义决策变量CTij为工件j在阶段i的完工时间;BTij为工件j在阶段i的开工时间;
为阶段i的机器k的第r道工序的完工时间;
为阶段i的机器k的第r道工序的开始时间;Cmax为所有工件的最大完工时间;Xijk为0-1二元变量,若工件j在阶段i被机器k加工,则其值为1,否则为0;Yijt为0-1二元变量,若时刻t工件j正在阶段i上加工或阻塞,则其值为1,否则为0;Zijl为0-1二元变量,若工件j在阶段i先于工件l加工,则其值为1,否则为0。
建立具有组合无限缓冲和阻塞约束的MOHFESP-CBC的整数规划模型如下所示。
min Cmax=max CTSj;
(1)
(2)
(3)
Zijl+Zilj≤1,∀i,j≠l;
(4)
BTil+(3-Zijl-Xijk-Xilk)H≥CTij,∀i,k,j≠l ;
(5)
BT1j≥RTj,∀j;
(6)
(7)
(8)
CTij+TTi≤BTi+1,j,∀j,i<S;
(9)
(10)
(11)
Xijk,Yijt,Zijl∈{0,1},∀i,j,l,k,t;
(12)
CTij,BTij≥0,∀i,j。
(13)
其中,式(1)和式(2)表示需要优化的目标,即最小化最大完工时间和机器总能耗;式(3)表示任一工件在每个阶段仅能选取一台机器进行加工;式(4)和(5)保证了在同一台机器上的两个工件的加工非重叠性,即后一工件的开工时间不得小于前一工件的完工时间;式(6)表示每个工件在到达第一阶段之后才能开始加工;式(7)表示每个阶段任一时刻正在加工的工件数不能超过该阶段可利用的机器数;式(8)表示对于阻塞阶段集内的阶段i,工件占用该阶段某台机器的时间段;式(9)表示只有工件完成当前阶段加工并运输到下一阶段后,才能开始后续阶段的加工;式(10)表示工件在最后一个阶段完工后即可离开;式(11)表示工件在加工过程中不能中断;式(12)和(13)定义了变量的取值范围。
1.3 多目标优化问题
解决多目标优化问题通常采用基于Pareto最优解的方法,一个多目标问题可以表示为
min f(x)=min{f1(x),f2(x),…,fi(x)}。
(14)
在多目标优化问题中,一般采用解的支配性来判断两个解的优劣。假设优化目标个数为O且都为最小化目标,则对于两个解x1和x2,如果满足以下关系:fl1(x1)≤fl1(x2),∀l1∈{1,2,…,O}且fl2(x1)≤fl2(x2),∀l2∈{1,2,…,O},则称x1支配x2,当一个解不被其他任何解支配时,称其为Pareto最优解。所有Pareto最优解构成Pareto解集,在目标空间上的映射为Pareto前沿,而多目标优化问题的目标是尽可能得到更趋近于真实Pareto前沿的解集。
2 改进多目标模因算法
模因算法是进化算法的扩展,可以平衡全局搜索和局部搜索的优点。本文将NSGA-Ⅱ融入全局优化算子,并设计一种融合自适应选择邻域搜索和多目标模拟退火的局部增强搜索算子,提出IMOMA来近似求解MOHFESP-CBC。IMOMA的主要过程如图1所示。
图1 IMOMA流程图
Figure 1 IMOMA flowchart
2.1 基于不相关机器分配的矩阵编码
不相关并行机环境下的混合流水线作业使得机器的分配对于完工时间和能耗的影响更大,因此采用基于不相关机器分配的矩阵编码方案,构建包含工件加工序列和机器分配信息的N×S矩阵来表示每个可行解,行基因表示工件在各阶段加工的机器号,行顺序即为第一个生产阶段的工件加工序列,矩阵内元素UMji表示第j个位置的工件在阶段i所分配的机器号,如图2所示。
图2 基于不相关机器分配的矩阵编码
Figure 2 Matrix coding based on uncorrelated machine assignment
2.2 解码
为获取调度解,根据矩阵内工件加工序列,依次将各工件安排在首个阶段所分配机器加工,令BT1j≥RTj以满足约束(6),后续阶段基于矩阵机器号信息为各工件分配机器,考虑约束(4)、(5)按先到先加工原则依次安排各工件的加工。对于无限缓冲阶段i,当工件j在阶段i的机器k上加工完成后,根据约束(3)和(7),若时刻CTij+TTi阶段i+1上所分配机器k′空闲,则它进入阶段i+1,否则工件j进入无限缓冲区,当机器k′完成其他工件加工后,累计机器k′的空闲时间段,根据约束(9)和(11)考虑加工和运输时间,当空闲时间段为P(i+1)jk′-TTi时,工件j经运输后开始阶段i+1的加工,同时机器k′的累计空闲时间段清零。同理,对于阻塞阶段i,若工件j在时刻CTij+TTi阶段i+1上所分配机器k′空闲,则直接进入阶段i+1加工,阻塞时间为0,否则停留在当前机器k进行等待,记录机器k′的空闲时间段,直至空闲时间段为P(i+1)jk′-TTi,工件j运输至阶段i+1进行加工,根据约束(8)可得阻塞时间为BT(i+1)j-(CTij+TTi)。下面以一个N=5,S=3,U1=U2=U3=2的算例来说明解码过程,其中仅考虑无限缓冲以及考虑阻塞阶段W={2}时的算例调度对比甘特图如图3所示。
图3 仅考虑无限缓冲与考虑阻塞阶段影响的调度对比
Figure 3 Comparison of scheduling between considering infinite buffering only and considering the impact of blocking
图3体现了阻塞约束对于调度的影响,在考虑阶段2到阶段3之间有阻塞约束时,工件4在完成阶段2作业后,由于阶段3分配的机器2仍在加工,因此工件4阻塞在阶段2机器2上,直至经运输后阶段3的机器2空闲,工件4进入阶段3,工件5开始阶段2的加工,阻塞时间为2。对比仅考虑无限缓冲约束的调度甘特图,最大完工时间增加了2。
2.3 初始元胞数组
根据基于不相关机器分配的矩阵编码,每个矩阵解代表一个元胞个体,NP个元胞个体构成元胞数组。高质量的初始元胞数组对算法的结果及全局收敛性有很大的影响。混沌映射具有随机性、遍历性及规律性等特点,相比经典的Logistic混沌映射,Tent混沌映射得到的初始解具有更好的随机性、均匀性与多样性[13],因此,采用基于Tent混沌映射的混合初始化策略生成初始元胞数组,其中由Tent混沌映射方法生成NP/2数量的初始元胞数组,由随机均匀分布方法生成剩余NP/2元胞数组,具体步骤如下。
步骤1 随机生成1个初始混沌基因,按照式(15)混沌映射函数进行迭代,直至生成元胞的所有混沌基因。
(15)
式中:c为元胞序号;h为混沌基因序号;Zch∈[0,1]为混沌基因。
步骤2 将Zch按式(16)转换到解空间得到对应值Xch,对Xch进行向下取整,即得到工件在各阶段所选的机器号。
Xch=lh+Zch(uh-lh)。
(16)
式中:lb和uh分别为混沌基因h对应工序可选择机器数量的下界和上界。
步骤3 重复上述操作,直至生成NP/2数量的元胞数组。
步骤4 随机生成工件在各阶段加工机器号,考虑到机器使用的均衡性,令随机值服从[1, Ui]的均匀分布,生成余下的NP/2数量的元胞数组,共同构成最终的包含NP个元胞的初始元胞数组。
2.4 全局优化算子
2.4.1 选择策略
采用二元锦标赛选择方法选择父代元胞数组进入交配池进行交叉变异,过程如下。
步骤1 通过快速非支配排序计算出元胞数组中各元胞的非支配等级和拥挤度。
步骤2 从元胞数组中随机选择两个元胞进行比较,优先选择非支配等级高的元胞;若两者非支配等级相同,则优先选择拥挤度较高的元胞;若两者拥挤度相同,则从中任选一个。
步骤3 重复步骤2,直至选出NP个元胞作为父代元胞数组。
2.4.2 交叉变异算子
全局优化算子采用基于工件位的交叉算子和单点变异算子。
元胞数组通过交叉获得新的元胞,从而推动整个元胞数组向前进化,基于工件位的交叉算子是从父代元胞数组中随机选择两个元胞F1与F2,从中随机生成两个不重复的工件位a和b作为交叉点,交换F1、F2中a和b之间的所有行基因,从而得到两个新的子代元胞D1和D2,如图4所示。
图4 基于工件位的交叉算子
Figure 4 Crossover operator based on job position
变异操作通过随机对某些基因产生较小的扰动来生成新的元胞,采用单点变异算子,从父代元胞中随机选择一个工件位γ和阶段位β,为该位置基因所对应工序随机分配其他可用机器用以加工,如图5所示。
图5 单点变异算子
Figure 5 Single-point mutation operator
为使得算法在前期充分搜索,后期避免陷入局部最优同时保留优质信息,基于文献[14],设计一种基于参数的自适应遗传策略,使交叉概率随着迭代次数的增加而自适应降低,变异概率随着迭代次数的增加而自适应提高,交叉概率PC和变异概率PM分别为
PC=
(17)
PM=1-PC。
(18)
式中:g、G分别为当前迭代数和最大迭代数;G1为进化前期的最大迭代数,设为0.25G;G2为进化中期的最大迭代数,设为0.75G;α为进化后期的调节系数,为避免后期PC值过小,设为0.9。
2.4.3 精英保留策略
精英保留策略通过将父代与子代元胞数组合并成规模为2NP的新元胞数组,再根据非支配排序等级与拥挤度保留其中最优秀的前NP个元胞作为新一代元胞数组。
2.5 局部增强搜索算子
为提高搜索效率和解的质量,设计一种融合自适应选择邻域搜索和多目标模拟退火算法的局部增强搜索算子。
2.5.1 自适应选择邻域搜索
基于求解问题的特点设计4种邻域搜索结构来进行搜索产生新解,具体如下。
(1)N1:插入。从当前元胞中随机选择两个工件行a和b(a≠b),将行a插到行b之前。
(2)N2:逆序反转。从当前元胞中随机选择两个工件行a和b(a≠b),并反转两个行之间的基因。
(3)N3:最大负载机器变异。根据解码策略计算当前元胞解中每个机器的能耗负载,找到其中能耗负载最高的机器,将分配到该机器的随机一个加工工件分配至该阶段其他随机机器上。
(4)N4:最大负载机器重排。根据解码策略得到当前元胞解中能耗负载最高的机器,随机选择两个分配至该机器加工的两个工件a和b(a≠b),将该机器所在阶段的两工件a和b在序列中对应位置之间所有工件的加工机器重新分配。
为提高搜索效率,采用自适应策略协调不同邻域结构之间的选择。每种邻域搜索结构具有一个概率值,在执行完每次迭代的邻域搜索后更新概率值,概率更新公式为
(19)
式中:LPu为邻域搜索结构Nu被选择的概率;npu为邻域搜索结构Nu的计数变量值。
在每次完成邻域搜索后,假设当前执行的是N1,若得到的新解支配当前解,则令np1=np1+1,而np2、np3和np4保持不变,否则,令npu=npu+0.5(u=1, 2, 3, 4)。为保证搜索多样性,在每次迭代执行完邻域搜索后进行判定,若某个邻域结构Nu的npu>200,则令npu=npu/2(u=1, 2, 3, 4)。
2.5.2 多目标模拟退火接受准则
完成每次的邻域搜索后,需要判断是否接受当前解,通常的接受准则为若新生成解更优,即新生成解支配当前解,则替换掉当前解。此操作虽简单易行,但在多样性的保持上效果并不突出。因此,使用基于多目标模拟退火的接受准则,如果新解无法支配当前解,仍然选择以一定概率接受当前解,并且随着迭代后期温度的降低,模拟退火对支配解的接受概率逐渐降低。基于多目标模拟退火的接受概率公式为
(20)
式中:RPg为第g次迭代的邻域搜索接受概率;tg为第g次迭代的温度值,tg=Temp·tg-1,Temp为冷却因子。
3 实验设计与分析
3.1 实验设计
为检验IMOMA算法在求解MOHFESP-CBC的性能,将其与传统NSGA-Ⅱ、结合局部搜索策略的改进混合蛙跳算法ISLFA[15]以及结合改进精英保留策略和自适应交叉概率参数的改进NSGA-Ⅱ算法INSGA-Ⅱ[14]进行对比。所有算法均采用MATLAB R2014a进行编程,在处理器为Intel Core i5-7300HQ CPU(2.50 GHz)、内存为8.00 GB的计算机上运行。为公平比较上述4种算法,以IMOMA算法运行最大迭代次数Gen=100且最大运行时间不超过600 s为所耗时间作为其他3种对比算法的停止条件。测试算例数据如下:
和分别满足[1, 10] 、[1, 5]、[1, 5]、[10, 30]和[1, 10]的均匀分布。随机生成不同规模的算例进行仿真实验,算例规模如下:N∈{20, 40, 60, 80, 100, 120},Ui∈{4, 5},S∈{3, 4},当S=3时,W={2},当S=4时,W={2, 3}。假设每个生产阶段的并行机数相同,N×S×Ui的不同组合共产生24种问题规模。
3.2 评价指标
多目标算法的优劣主要通过算法所求解集的非支配解数量、收敛性和多样性进行评估[16]。本文选取反向世代距离指标(IGD) 和间隔距离(SP)作为评价指标。由于测试算例的真实Pareto前沿未知,因此使用近似Pareto前沿代替最优Pareto前沿,对于每个算例,将所有算法得到的非支配解集去除支配解和重复解可以得到该算例的近似Pareto前沿。
(1)IGD。IGD是一种综合性指标,IGD值越小,表明解集越逼近近似Pareto前沿且分布更均匀,解集的收敛性和多样性更好,具体定义为
(21)
式中:dl为第l个非支配解到最优解之间的欧氏距离;|A|为所得到的最优Pareto前沿中非劣解的个数。
(2)SP。SP是一种多样性指标,用来反映非支配解集中解分布的均匀性,SP指标值越小,解集中解的分布性与多样性越好,具体定义为
(22)
式中:
为所有dl的均值。
3.3 不同规模问题对比实验
IMOMA算法参数包括元胞数组规模NP,冷却因子Temp。设定参数选取的大致范围:NP～[80, 150],Temp～[0.8, 0.99],在模拟退火初始温度固定10 000的情况下,在参数范围内进行大量算例测试,以IGD值作为评价指标,得到应用于IMOMA算法求解该问题的最优参数取值,即NP为100,模拟退火初始温度为10 000,Temp为0.95。对比算法同样参考原文献设计取一定的参数取值范围进行测试,从而设置NSGA-Ⅱ、ISLFA和INSGA-Ⅱ的NP均为100;NSGA-Ⅱ中PC=0.8,PM=0.3;ISLFA中扰动变异循环次数为5;INSGA-Ⅱ中进化后期阶段交叉率的调节系数为0.8。
针对每种问题规模的算例,每种算法独立运行10次,每次运行得到一组IGD和SP值,计算得到10次运行的平均IGD和平均SP值,测试结果见表1,其中运行时间为求解对应规模算例时4种算法的运行时间。由表1可得到如下结论。
表1 不同问题规模算例测试结果
Table 1 Test results for different sized problem instances
N×S×UiIGDSPIMOMANSGA-ⅡISLFAINSGA-ⅡIMOMANSGA-ⅡISLFAINSGA-Ⅱ运行时间/s20×3×401 525.201 362.101 335.00338.002 059.101 827.001 673.0067.5920×3×501 941.101 553.002 174.40109.002 050.001 709.003 267.0063.8620×4×484.513 010.90332.433 046.80255.203 496.30583.203 566.9074.0820×4×503 166.30524.612 720.60129.803 443.70653.623 170.8076.3340×3×4346.121 620.60629.721 306.501 857.204 731.001 693.203 698.80175.3440×3×502 798.703 060.102 695.10589.003 399.003 815.003 284.00179.5340×4×44.554 595.30412.634 889.10851.205 987.101 256.006 417.70167.4540×4×506 889.701 485.306 816.50376.008 059.901 861.207 435.30156.4160×3×4295.205 705.102 574.105 873.301 208.406 831.602 896.806 940.80197.9660×3×505 100.601 789.305 150.301 398.007 815.802 948.007 571.60178.0360×4×405 179.40440.393 749.401 722.407 401.002 122.405 590.30210.4260×4×508 026.901 725.107 949.50644.009 019.802 369.009 333.40219.6680×3×405 897.90792.286 974.10672.006 842.501 464.208 379.30248.6580×3×583.316 432.501 303.105 881.90343.217 806.801 649.006 497.40242.1980×4×4129.868 097.90489.297 308.601 305.409 784.901 504.008 897.70264.2380×4×546.676 887.1068.266 741.901 587.008 738.601 468.308 707.60272.95100×3×43.657 029.001 152.306 979.401 051.808 748.602 171.208 596.10294.78100×3×5151.438 767.701 762.407 282.601 070.0010 121.002 379.408 415.70291.75100×4×408 272.501 866.107 792.801 139.0010 042.002 990.209 589.40348.25100×4×509 717.101 952.109 717.101 075.3012 090.003 027.4011 410.00371.39120×3×44.087 495.201 443.708 383.00867.678 550.502 311.409 972.50400.36120×3×508 936.302 326.008 649.401 027.0010 799.003 353.0010 843.00374.50120×4×4012 075.001 688.3011 399.00419.0012 779.002 107.1013 171.00455.52120×4×5010 088.003 124.5010 733.00538.3311 131.003 662.8011 658.00458.98平均47.896 219.001 410.716 064.55857.257 572.012 159.277 420.30241.26
(1)在IGD指标方面,相同运行时间内IMOMA得到的平均IGD值在所有问题规模算例中均小于其他3种对比算法,说明IMOMA在求解该问题时能得到更好的Pareto解集,解的质量更优,算法的寻优能力较强,具有更好的收敛性和多样性。
(2)在SP指标方面,相同运行时间内IMOMA在求解40×3×4和80×4×5算例时获得的解集略差于ISLFA,但在其余算例上均优于其他3种对比算法,说明IMOMA求得解集中的元胞解具有较好的分布性和多样性。
为探索算法运行时间与求解性能的关系,取 N={40, 60, 80, 100},S=3,Ui=5的不同规模的一组算例,分别运行4种算法,设定停止条件为每种算法迭代100次,独立运行10次,得到10次的平均IGD、平均SP值以及运行时间,测试结果见表2。
表2 各算法迭代100次的测试结果
Table 2 Test results of algorithms for 100 iterations
N×S×UiIGDSP运行时间/sIMOMANSGA-ⅡISLFAINSGA-ⅡIMOMANSGA-ⅡISLFAINSGA-ⅡIMOMANSGA-ⅡISLFAINSGA-Ⅱ40×3×5106.1 3 401.5 82.03 556.2 250.0 3 642.4 165.33 885.4 136.6 92.5 171.8 104.0 60×3×505 417.1 222.0 5 156.1 63.0 5 705.8 285.0 5 279.5 173.0 138.0 229.2 137.9 80×3×518.57 154.2 1 074.6 6 990.2 868.38 877.1 1 942.7 8 296.8 209.6 160.9 251.3 162.8 100×3×536.99 604.7 2 088.5 9 284.7 721.310 803.2 3 009.8 10 604.0 280.0 193.9 343.9 203.5 平均40.46 394.4866.8 6 246.8475.77 257.1 1 350.7 7 016.4 199.8 146.3 249.1 152.0
由表2可知,对于4种规模问题,在平均运行时间199.8 s内,IMOMA得到的IGD和SP平均值均优于其他3种对比算法,虽然在求解40×3×5规模算例时IMOMA得到的IGD和SP值略差于ISLFA,但运行时间更短,且随着问题规模的增大,IMOMA得到的解集质量更高。IMOMA的运行时间平均值短于ISLFA,略长于NSGA-Ⅱ和INSGA-Ⅱ,但在IGD和SP指标上的表现远远好于NSGA-Ⅱ和INSGA-Ⅱ,说明IMOMA用略长的时间得到了更高质量的解集。
为判断算法之间是否存在统计学意义上的显著差别,根据表2的不同算例测试数据,使用SPSS Statistics 21进行Wilcoxon符号秩检验,结果如表3所示。由表3可知,在5%的显著性水平下,P值均<0.5,因此对于 IGD 和SP指标,IMOMA算法对比其余3种算法具有压倒性的显著优势。
表3 Wilcoxon符号秩检验结果
Table 3 Wilcoxon sign rank test results
算法比较P值IGDSPIMOMA和NSGA-Ⅱ0.000 0180.000 018IMOMA和ISLFA0.000 0180.000 027IMOMA和INSGA-Ⅱ0.000 0180.000 018
为更直观表现算法求解效果,以测试问题80×3×5为例,4种算法各随机运行1次获得的Pareto前沿如图6所示,其中,“APF”表示该问题的近似Pareto前沿。由图6可知,在APF的6个解中,有5个解由IMOMA得到,1个解由ISLFA得到,而NSGA-Ⅱ和INSGA-Ⅱ得到的Pareto解集质量相对较差。
图6 4种算法求解80×3×5算例的Pareto前沿
Figure 6 Pareto front of 4 algorithms for solving the 80×3×5 case
同时,相较于其他3种对比算法,IMOMA所得解集更接近于近似Pareto前沿,具有更好的收敛性。因此,IMOMA算法在求解MOHFESP-CBC方面具有更好的算法性能。
4 结论
本文研究了生产阶段间带有无限缓冲和阻塞两种不同中间缓冲约束的HFSP,以最小化最大完工时间和机器总能耗为目标建立了MOHFESP-CBC的整数规划模型。提出一种IMOMA算法求解该问题,应用基于Tent混沌映射的混合初始化策略生成初始元胞数组,全局优化算子引入NSGA-Ⅱ,采用基于参数的自适应遗传策略对交叉概率、变异概率进行调整,局部增强搜索算子采用融合自适应选择邻域搜索和多目标模拟退火的搜索策略,并结合问题特点设计4种邻域搜索结构用于提升局部搜索效率。
通过不同问题规模的仿真实验,与3种现有算法进行对比,验证了IMOMA在求解MOHFESP-CBC算法性能的有效性和优越性。
节能调度是现代工业发展的一大趋势,未来可继续深入探讨节能和经济指标的综合在车间调度领域的应用研究;还可考虑加入更多的实际生产约束以及其他组合中间缓冲约束的HFSP;另外探索更优的编解码方式以及设计解决该类问题的更高效的智能算法也将是下一步研究的重点。
[1] RIAHI V, KHORRAMIZADEH M, HAKIM NEWTON M A, et al. Scatter search for mixed blocking flowshop scheduling[J]. Expert Systems with Applications, 2017, 79: 20-32.
[2] 王君妍, 王薛苑, 轩华. 带批处理机的多阶段柔性流水车间调度优化[J]. 郑州大学学报(工学版), 2017, 38(5): 86-90.WANG J Y, WANG X Y, XUAN H. Multi-stage flexible flowshop scheduling with batching machines[J]. Journal of Zhengzhou University (Engineering Science), 2017, 38(5): 86-90.
[3] QIN H X, HAN Y Y, WANG Y T, et al. Intelligent optimization under blocking constraints: a novel iterated greedy algorithm for the hybrid flow shop group scheduling problem[J]. Knowledge-Based Systems, 2022, 258: 109962.
[4] MISSAOUI A, BOUJELBENE Y. An effective iterated greedy algorithm for blocking hybrid flow shop problem with due date window[J]. RAIRO-Operations Research, 2021, 55(3): 1603-1616.
[5] 胡蓉, 董钰明, 钱斌. 基于探路者算法的绿色有限缓冲区流水线调度[J]. 系统仿真学报, 2021, 33(6): 1384-1396.HU R, DONG Y M, QIAN B. Pathfinder algorithm for green pipeline scheduling with limited buffers[J]. Journal of System Simulation, 2021, 33(6): 1384-1396.
[6] LIN C C, LIU W Y, CHEN Y H. Considering stockers in reentrant hybrid flow shop scheduling with limited buffer capacity[J]. Computers &Industrial Engineering, 2020, 139: 106154.
[7] 裴小兵, 李依臻. 新型混合改进遗传算法求解零等待流水车间调度问题[J]. 计算机集成制造系统, 2021, 27(3): 815-827.PEI X B, LI Y Z. New hybrid improved genetic algorithm for solving no-wait flow shop scheduling problem[J]. Computer Integrated Manufacturing Systems, 2021, 27(3): 815-827.
[8] AZAIEZ M N, GHARBI A, KACEM I, et al. Two-stage no-wait hybrid flow shop with inter-stage flexibility for operating room scheduling[J]. Computers &Industrial Engineering, 2022, 168: 108040.
[9] WANG Y M, LI X P, RUIZ R, et al. An iterated greedy heuristic for mixed no-wait flowshop problems[J]. IEEE Transactions on Cybernetics, 2018, 48(5): 1553-1566.
[10] 钟祾充, 李文锋, 贺利军, 等. 集装箱码头混合零空闲柔性流水作业调度优化[J]. 计算机集成制造系统, 2022, 28(11): 3421-3432.ZHONG L C, LI W F, HE L J, et al. Optimization of mixed no-idle flexible flow scheduling in container terminal[J]. Computer Integrated Manufacturing Systems, 2022, 28(11): 3421-3432.
[11] 轩华, 付鑫博, 李冰. 基于混合离散人工蜂群算法的混合零等待柔性流水车间优化研究[J]. 工业工程与管理, 2023, 28(1): 170-180.XUAN H, FU X B, LI B. Research on optimization of mixed zero-wait flexible flowshop based on hybrid discrete artificial bee colony algorithm[J]. Industrial Engineering and Management, 2023, 28(1): 170-180.
[12] ZHUANG Z L, ZHANG Z L, TENG H, et al. Optimization for integrated scheduling of intelligent handling equipment with bidirectional flows and limited buffers at automated container terminals[J]. Computers and Operations Research, 2022, 145: 105863.
[13] 姜一啸, 吉卫喜, 何鑫, 等. 基于改进非支配排序遗传算法的多目标柔性作业车间低碳调度[J]. 中国机械工程, 2022, 33(21): 2564-2577.JIANG Y X, JI W X, HE X, et al. Low-carbon scheduling of multi-objective flexible job-shop based on improved NSGA-Ⅱ[J]. China Mechanical Engineering, 2022, 33(21): 2564-2577.
[14] 黄辉, 李梦想, 严永. 考虑序列设置时间的混合流水车间多目标调度研究[J]. 运筹与管理, 2020, 29(12): 215-221.HUANG H, LI M X, YAN Y. Research on multi-objective scheduling of hybrid flow production shop considering sequence setting time[J]. Operations Research and Management Science, 2020, 29(12): 215-221.
[15] 张洪亮, 徐公杰, 张金春. 带有学习效应的多阶段混合流水车间调度问题研究[J]. 重庆师范大学学报(自然科学版), 2021, 38(1): 87-95.ZHANG H L, XU G J, ZHANG J C. Research on multi-stage hybrid flow shop scheduling problem with learning effect[J]. Journal of Chongqing Normal University (Natural Science), 2021, 38(1): 87-95.
[16] 王丽萍, 任宇, 邱启仓, 等. 多目标进化算法性能评价指标研究综述[J]. 计算机学报, 2021, 44(8): 1590-1619.WANG L P, REN Y, QIU Q C, et al. Survey on performance indicators for multi-objective evolutionary algorithms[J]. Chinese Journal of Computers, 2021, 44(8): 1590-1619.