基于改进人工蜂群算法的多目标绿色柔性作业车间调度研究

李益兵1,2 黄炜星1 吴 锐1

1.武汉理工大学机电工程学院,武汉,4300702.数字制造湖北省重点实验室,武汉,430070

摘要针对多目标绿色柔性作业车间调度问题(MGFJSP)的特点,提出从碳排放量、噪声和废弃物这3个指标来综合评定环境污染程度,建立了以最小化最大完成时间和环境污染程度为优化目标的MGFJSP模型,并提出了一种改进的人工蜂群算法来求解该模型。算法的具体改进包括:设计了一种三维向量的编码和对应解码方案,在跟随蜂搜索阶段引入一种有效的动态邻域搜索操作来提高算法的局部搜索能力,在侦查蜂阶段提出产生新食物源的策略用于增加种群的多样性。最后进行了实验研究与算法对比,以验证所建模型和所提算法的有效性。

关键词绿色柔性作业车间调度;多目标优化;环境污染;人工蜂群算法

0 引言

减少环境污染,实现绿色制造,是现代制造业迫切需要解决的问题之一[1]。生产调度是制造系统的一个重要环节,高效的调度方法能有效地改善制造过程中的环境污染情况,达到节能减排的效果[2]

近年来,国内外针对绿色车间调度问题开展了大量的研究,如潘全科等[3]对模糊加工参数的绿色车间调度问题进行了分析,在模糊参数的基础上建立了绿色制造车间生产调度的决策模型,其目标是最大限度地缩短生产周期,同时减少对环境的负面影响;MANSOURI等[4]对绿色流水作业车间调度问题中能耗与最大完成时间之间的关系进行了权衡,并探索了制造业节能的潜力;蒋增强等[5]通过分析当前研究的现状和不足,建立了一种基于设备状态能耗曲线的低碳策略下的多目标柔性车间调度优化模型,该模型考虑了设备状态能耗曲线的能耗、最大生产期、加工成本等约束;刘清涛等[6]提出了一种面向绿色制造的多目标车间调度方法,该方法在保证生产效益的前提下能够使制造过程中资源消耗和环境的影响最小,有效地解决了绿色制造中的多目标调度优化问题;齐晓宁等[7]开展了基于遗传算法的面向绿色制造的车间调度优化问题,综合考虑了加工时间、电能消耗的可计算性以及质量、环境影响的复杂模糊性。

多目标柔性作业车间调度问题(multi-objective flexible job-shop scheduling problem, MFJSP)是复杂的NP-hard问题,相较于基础的车间调度问题更符合实际情况,求解难度也相对较高。MFJSP现有的研究主要集中在智能优化算法的求解上,XU等[8]提出了一种有效的蛙跳算法用于解决多目标柔性作业车间的调度优化问题,同时基于已知问题的数值模拟和比较验证了所提算法的有效性;CHIANG等[9]讨论了以最小化生产周期、总工作量和最大工作量为目标的MFJSP,并提出了一种多目标进化算法;LIU等[10]介绍了一种混合元启发式变邻域粒子群优化算法用于解决MFJSP;WANG等[11]为避免在解决MFJSP时出现的过早收敛和局部搜索能力较差等缺陷,提出了一种基于Pareto的分布估计算法。

本文提出从碳排放量、噪声和废弃物这3个指标来描述环境污染指标属性,并以最小化最大完成时间和环境污染程度为优化目标,开展了多目标绿色柔性作业车间调度问题(MGFJSP)研究。针对MGFJSP约束条件多、求解难度高等特点,设计了一种改进的人工蜂群(improved artificial bee colony,IABC)算法,以实现制造过程经济指标和绿色指标的协同优化。

1 问题描述及数学模型

本文提出的MGFJSP主要研究n个工件在m台机器上加工,每一台机器的加工速度可供选择,每个工件均有多道工序,同一工件的各道工序的先后关系不能发生改变。同时,还需要满足以下约束:①每道工序在同一时刻只能被一台机器加工;②每道工序均可在一组相容机器的任意一台机器上加工;③每台机器在加工工件时,加工速度一旦确定就不能进行随意变更;④每一道工序的加工过程一旦开始,便不可以被中断。

由于加工所需要的最大完成时间以及加工过程中造成的碳排放量、噪声和废弃物等都会因工序选择的加工机器和速度挡位的不同而发生改变,因此,本文所研究的调度问题的优化目标为:在满足加工约束条件的前提下,合理地安排各工序的加工机器以及该机器的速度挡位,以使所期望的指标达到最优。本文中所使用的符号定义如表1所示。

表1 符号含义

Tab.1 The meaning of symbols

索引号i,i'工件序号j,j'工序序号k机器序号v机器加工速度挡位序号n工件数量m机器数量ni,n'i工件i,i'的工序总数B一个无穷大的数参数变量Q(i)(j)kv机器k以速度挡位v加工工件i的第j道工序的能耗Psk机器k的待机功率Qsk机器k的待机能耗Oij工件i的第j道工序ε能耗和碳排放量之间的转换系数Lijk机器k加工工件i的第j道工序时的可选加工速度挡位集合nijkv机器k以速度挡位v加工工件i的第j道工序产生的噪声gijkv机器k以速度挡位v加工工件i的第j道工序产生的废弃物决策变量Cmax最大完成时间A总环境属性值ETC总碳排放量Sij工件i的第j道工序的起始加工时间Fij工件i的第j道工序的加工结束时间xijkv若工件i的第j道工序在机器k上以速度挡位v加工,则令xijkv=1,否则,令xijkv=0y(i')(j')ij若工件i的第j道工序是工件i'的第j'道工序的前置工序,则令y(i')(j')ij=1,否则,令y(i')(j')ij=0

将生产过程中产生的废弃物、噪声及总碳排放量的综合影响值定义为总环境属性值,并将总环境属性值的大小作为评价环境污染程度的依据。由此,目标函数可表示为

f=min(Cmax,A)

(1)

约束条件为

Cmax=max(Fini) i=1,2,…,n

(2)

式(2)表示最大完成时间是最大的工序加工结束时间。式(3)表示总能耗是各机器的总待机能耗与总加工能耗之和,而总碳排放量为碳排放量系数ε乘以总能耗,通常取ε=0.755 9[12]。式(4)中,总碳排放量、噪声和废弃物的量纲不同,因此采用加权平均值的方法对各参数进行归一化处理,其中wTCwnwg分别为总碳排放量、噪声和废弃物的权重,各权重值应该根据企业实际加工情况来定,本文权重取值分别为40%、20%和40%[13]。式(5)、式(6)是工序的约束,即同一工件的工序必须按顺序加工。式(7)是加工设备的约束,即同一台机器在同一时刻只能对一道工序进行加工。

2 算法设计

人工蜂群(ABC)算法是KARABOGA[14]提出的一种受生物行为启发的优化算法,该算法主要通过模拟蜜蜂的觅食来解决实际问题。由于ABC算法具有搜索速度快、精度高、鲁棒性强等优点,故已在车间调度领域得到了广泛的应用。但是,ABC算法只适用于求解连续型问题,而MGFJSP是离散型问题,ABC算法很难对其进行有效的求解,因此,本文提出了一种改进的人工蜂群(IABC)算法,其整体流程如下。

(1)进行种群初始化操作。通过计算种群中个体的拥挤距离和种群中非支配Pareto解的数量来更新档案集。假设N为当前迭代次数,G为最大迭代次数,令N=0。

(2)若N<G,则转至步骤(3);否则,转至步骤(7)。

(3)雇佣蜂操作。通过拥挤距离和种群中非支配Pareto解的数量来更新档案集。

(4)跟随蜂操作。通过拥挤距离和种群中非支配Pareto解的数量来更新档案集,NN+1。

(5)判断是否有需要放弃的蜜源,若有,则转至步骤(6);否则,转至步骤(2)。

(6)侦查蜂操作。判断当前迭代次数N是否超过最大迭代次数G, 若是,则转至步骤(7);否则,转至步骤(2)。

(7)输出档案集中的内容。

2.1 编码与解码

根据MGFJSP问题特性,本文设计了一种三维向量编码的方法,即每个可行解均由3个部分组成,分别是工序编码向量(OV)、机器编码向量(MV)和速度编码向量(SV),3个向量的长度均等于所有工件的工序数之和。

可行解的编码方式如图1所示。OV中用每个工件对应的索引号来表示该工件的工序,该索引号第几次出现就代表是该工件中的第几道工序;MV中对应的索引号表示对应工序所选择的机器序号;同理,SV中对应的索引号表示对应工序所选择的加工速度挡位。

图1 编码示意图

Fig.1 Coding diagram

为了得到具体的调度方案,还需要对可行解的编码进行解码操作,本文采用左移策略,即从左至右依次安排OV中的工序,在满足约束的前提下使工序尽可能早地被安排加工。

2.2 档案集的维护

本文在IABC算法中采用一个固定容量的档案集用于维护搜索过程中找到的非支配解的多样性[15],通过对非支配解进行拥挤距离大小的排序来确定档案集中的内容。个体拥挤距离的计算步骤如下[16]: ①按照每个目标函数值从大到小的顺序对种群进行排序;②选出目标函数值最小的个体和目标函数值最大的个体,将这两个个体的距离设置为无穷大;③将其他解的距离定义为其相邻两个解的函数值的归一化差值;④将每个个体在各个目标下的距离值的总和作为其拥挤距离;⑤按照拥挤距离从小到大的顺序对种群中的所有个体进行重新排序;⑥依次向档案集中添加重新排序后的个体,若个体数量大于档案集的容量,那么当档案集被填满时则不再向档案集中添加个体。

2.3 种群初始化

初始解的优劣会直接影响算法的求解速度和质量。目前,绝大部分算法均采用随机生成初始解的方法,这很难保证所产生的初始种群的质量。为克服传统方法中随机产生的初始解质量较低的缺陷,本文提出将随机生成与策略选择相结合的方式来生成可行解,即初始种群中40%的个体采用随机生成方式,剩余60%的个体采用策略选择方法,且在进行加工速度挡位选择时尽可能地选择挡位较大的速度,以缩短加工时间。

2.4 雇佣蜂操作

采用交叉与变异相结合的方法对雇佣蜂的搜索操作进行了改进。首先,从种群中选出一个父代X1,同时随机选出另外一个父代X2(X2要求不同于X1)用于与父代X1的OV向量进行交叉操作,本文选用已广泛使用的POX交叉方法[17],其具体操作过程如下:①将工件序号随机地分配到两个非空且互补的集合Q1Q2中;②从父代X1中选出包含在集合Q1中的工件序号,保持各工件序号的位置不变并复制到子代X′中;③从父代X2中选出包含在集合Q2中的工件序号,并将选出的工件序号按顺序依次插入到子代X′的空缺处;④按照步骤②和步骤③的操作,从父代X1中选出包含在集合Q2中的工件序号,保持各工件序号的位置不变并复制到子代X″中,从父代X2中选出包含在集合Q1中的工件序号,并将选出的工件序号按顺序插入到子代X″的空缺处;⑤从子代X′和X″中选出较优的个体作为交叉后的子代。

图2为利用POX交叉方式生成的一个子代X′的示意图。

图2 POX交叉操作示意图

Fig.2 Diagram of POX cross operation

若进行POX交叉操作后子代优于父代X1,则用该子代代替父代X1,若子代并不优于父代,则在该子代的基础上针对MV向量进行变异操作,即在MV向量中随机选择一个位置,并选择一个合理的机器序号进行替换,同时为该机器随机选择合理的加工速度挡位,进而得到新的子代个体。图3给出了MV向量的变异操作示意图。

注:“*”表示该序号是不合理序号。

图3 MV向量变异操作示意图

Fig.3 Diagram of the MV vector variation operation

将进行MV向量变异操作后产生的新子代与父代进行比较,若产生的新子代更优,则用该子代代替父代,否则在该子代的基础上针对SV向量进行变异操作,即在SV向量中随机选择一个位置并对其速度挡位进行合理的替换,若产生的子代更优,则用该子代代替父代。

2.5 跟随蜂操作

为了提高算法的局部搜索能力,本文引入动态邻域搜索(dynamic neighborhood search, DNS)机制来改进跟随蜂的搜索操作。共包含4种邻域结构:交换邻域结构、插入邻域结构、分配邻域结构和变异邻域结构。

交换邻域结构是将个体OV向量中任意指定的两个位置进行交换得到新的个体;插入邻域结构是指定个体OV向量中的某一元素插入到该OV向量的任意指定位置;分配邻域结构是给个体的指定工序随机分配合理的机器和速度挡位;变异邻域结构采用轮盘赌选择的方式,以一定的概率决定此时对指定工序进行仅机器序号的合理变异还是同时进行机器和速度挡位的合理变异。

基于DNS改进跟随蜂的搜索操作过程如下:在每一次邻域结构操作后都会进行新个体和原始个体的比较,若新个体优于原始个体,则新个体取代原始个体,且无需进行后续的邻域结构操作;若未得到优于原始个体的新个体,则需要进行后续的邻域结构操作,以得到更优的个体,如图4所示。

2.6 侦查蜂操作

侦查蜂阶段选用的是产生新食物源替换策略,而不是传统的随机挑选食物源,即挑选出一个更新次数超过规定限制次数最多的个体,并将该个体进行替换,替换的方法是从档案集中随机选择一个个体,并对该个体进行替换操作。

图4 跟随蜂搜索操作流程图

Fig.4 The search operation flow chart of follow bee

3 实验研究

3.1 测试算例

本文以Brandimarte算例[18]为标准算例,但由于本文模型考虑了噪声、废弃物指标,故需要进行数据的扩展。结合相关文献的理论支撑[12],在合理范围内随机生成了相应的数据,如表2所示,其中噪声和废弃物列为统一量纲后的数值。

表2 测试算例数据

Tab.2 Data of testing instances

算例工件总数机器总数可选工序数可选机器数加工时间(s)噪声废弃物MK01106[5,7]3[1,7][70,80][90,140]MK02106[5,7]6[1,7][72,83][109,135]MK03158105[1,20][71,79][99,126]MK04158[3,10]3[1,10][70,85][95,136]MK05154[5,10]2[5,10][75,84][108,143]MK06105155[1,10][72,84][95,127]MK0720555[1,20][70,80][121,142]MK082010[10,15]2[5,20][70,82][103,138]MK092010[10,15]5[5,20][67,84][98,129]MK102015[10,15]5[5,20][69,80][108,135]

算法的运行环境为:2.50 GHz,6 GB RAM,Windows 7,64位操作系统的个人计算机,编程语言为C#。

3.2 参数设置

影响IABC算法性能的参数主要有3个,分别为:种群规模PS,最大迭代次数G,档案集容量SA。为寻求IABC算法较优的运行参数组合,本文采用正交试验法对参数进行了优化配置,因素水平表见表3。

由于正交表中没有完全对应的三因素五水平的标准正交表,因此选用六因素五水平L25(56)的标准正交表来设计本文试验,如表 4 所示。需要说明的是,L25(56)标准正交表的纵列数比试验因素的个数多,则表4中的第1~3列对应试验的3个因素,并将第4~6列置空。同时为简化表4,故表4中只列出了本试验所对应的3个因素列。其中,分别表示当前因素在水平1~5下运行结果的平均值

表3 因素水平表

Tab.3 Factor level table

因数种群规模PS最大迭代次数G档案集容量SA水平1500305024002540330020304200152051001010

本文选用算例MK05作为正交试验的测试算例,算法均在每种参数组合下独立运行30次,可得到各参数组合下的非支配解集,同时将每种参数组合下得到的非支配解集聚集起来即可得到新的非支配解集,此处称为参考集,将各参数组合下得到的非支配解集占参考集中的数量作为实验结果,如表4所示。

为了更加直观地反映表4中因素与水平之间的内在规律,以每个因素的实际水平取值顺序绘制出相应的趋势图,分别见图5~图7。可以看出,当PS=500,G=10,SA=20时,算法的实验效果最佳。

3.3 结果讨论

为进一步验证算法的有效性,本文分别选择多目标粒子群优化(multi-objective particle swarm optimization, MOPSO)算法[19]、混合差分进化(hybrid differential evolution, HDE)算法[20]和改进的非支配排序遗传算法(non-dominated sorting genetic

表4 正交试验表

Tab.4 Orthogonal table

试验号种群规模PS最大迭代次数G档案集容量SA实验结果150030500.557 03250025400.508 67350020300.492 10450015200.516 34550010100.408 29640030400.490 13740025300.480 21840020200.514 87940015100.409 141040010500.449 871130030300.432 121230025200.417 201330020100.403 211430015500.450 691530010400.490 271620030200.408 171720025100.401 271820020500.386 951920015400.423 652020010300.425 712110030100.309 272210025500.370 682310020400.390 212410015300.416 792510010200.472 37Ⅰ-0.496 4860.439 3440.443 044Ⅱ-0.468 8440.435 6060.460 586Ⅲ-0.438 6980.437 4680.449 386Ⅳ-0.409 1500.443 3220.465 790Ⅴ-0.391 8640.449 3020.386 236极差0.104 6220.013 6960.079 554最优方案水平1水平5水平4

图5 种群规模因素水平趋势图

Fig.5 Factor level trend diagram of population size

图6 最大迭代次数因素水平趋势图

Fig.6 Factor level trend diagram of maximum number of iteration

图7 档案集容量因素水平趋势图

Fig.7 Factor level trend diagram of maximum number of iteration

algorithm-Ⅱ, NSGA-Ⅱ)[21]来开展对比实验研究,以反世代距离(IGD)和错误率(ER)为评价指标,IGD和ER的值越小,表明算法的性能越优。

将各自算法在每组测试数据下独立运行30次,工件数量越大,算法所需的运行时间越长,因此,设定各组测试数据算法运行时间(单位:s)的数值为工件数量的3倍,并取30次结果的平均值作为最终测试结果,如表5所示。

表5 算法对比测试结果

Tab.5 The experimental results of algorithm comparison

算例IABCMOPSOHDENSGA-ⅡIGD值ER值IGD值ER值IGD值ER值IGD值ER值MK010.002 80.006 613.130 90.975 022.022 71.000 018.067 70.924 3MK020.025 30.013 35.113 80.968 110.184 00.978 68.620 21.000 0MK030034.084 11.000 055.690 61.000 042.241 21.000 0MK040.001 20.000 811.217 91.000 019.847 00.996 316.586 40.896 4MK050.000 80.000 416.356 71.000 026.842 31.000 09.645 30.986 3MK060.001 30.000 716.347 41.000 025.588 31.000 021.626 90.965 4MK070046.591 11.000 079.610 71.000 066.168 61.000 0MK080.002 50.002 343.006 01.000 055.252 20.926 546.837 10.897 5MK090080.009 21.000 083.627 30.963 280.624 20.978 5MK100.001 80.001 945.061 91.000 059.444 41.000 051.159 20.762 3

4种算法的IGD和ER评价指标的对比结果分别见图8和图9。可以看出,IABC算法的IGD和ER评价指标均显著优于其他3种算法对应的评价指标,这说明在相同测试时间内,与其他3种算法相比,IABC算法得到的近似Pareto前沿更接近于真实的Pareto前沿,即得到的Pareto解的收敛性和多样性更优,从而更好地验证了IABC算法改进机理的合理性和有效性。

图8 4种算法的IGD对比结果

Fig.8 The comparison results of IGD for four algorithms

图9 4种算法的ER对比结果

Fig.9 The comparison results of ER for four algorithm

4 结论

(1)本文研究了考虑环境污染的多目标绿色柔性作业车间调度问题(MGFJSP),建立了以最小化最大完成时间和环境污染程度为优化目标的数学模型,统筹考虑了碳排放量、噪声和废弃物这3个指标。

(2)针对MGFJSP问题特点,提出了一种改进的人工蜂群算法,并通过编码和解码方案设计、混合初始化策略、多种交叉和变异方法、动态邻域搜索等操作来提高所提算法的寻优能力。

(3)基于标准算例进行了扩展,并将所提算法与常用算法进行了对比实验,有效地验证了所提算法改进机理的合理性和解决MGFJSP问题的有效性。

参考文献

[1] 刘飞, 曹华军, 何乃军. 绿色制造的研究现状与发展趋势[J]. 中国机械工程, 2000, 11(1):105-110.

LIU Fei, CAO Huajun, HE Naijun. On State-of-the-art of Green Manufacturing[J]. China Mechanical Engineering, 2000, 11(1):105-110.

[2] 王凌, 王晶晶, 吴楚格. 绿色车间调度优化研究进展[J]. 控制与决策, 2018, 33(3):385-391.

WANG Ling, WANG Jingjing, WU Chuge. Advances in Green Shop Scheduling and Optimization[J]. Control and Decision, 2018, 33(3):385-391.

[3] 潘全科, 王文宏, 朱剑英. 面向绿色制造的一类模糊调度模型及其算法[J]. 中国机械工程, 2006, 17(13):1371-1374.

PANG Quanke, WANG Wenhong, ZHU Jianying. Decision-making Model for Job Shop Scheduling with Fuzzy Processing Parameters in Green Manufacturing[J]. China Mechanical Engineering, 2006, 17(13):1371-1374.

[4] MANSOURI S A, AKTAS E, BESIKCI U. Green Scheduling of a Two-machine Flowshop:Trade-off between Makespan and Energy Consumption[J]. European Journal of Operational Research, 2016, 248(3):772-788.

[5] 蒋增强, 左乐.低碳策略下的多目标柔性作业车间调度[J]. 计算机集成制造系统, 2015, 21(4):1023-1031.

JIANG Zengqiang, ZUO Le. Multi-objective Flexible Job-shop Scheduling Based on Low-carbon Strategy[J].Computer Integrated Manufacturing Systems, 2015, 21(4):1023-1031.

[6] 刘清涛, 蔡宗琰, 刘晓婷,等. 一种面向绿色制造的多目标车间调度方法[J]. 长安大学学报(自然科学版), 2011, 31(2):106-110.

LIU Qingtao, CAI Zongyan, LIU Xiaoting, et al. Multi-objective Optimization for Job Shop Scheduling in Green Manufacturing[J]. Journal of Chang’an University(Natural Science), 2011, 31(2):106-110.

[7] 齐晓宁, 汪永超, 贾婧, 等. 基于遗传算法的面向绿色制造的车间调度优化[J]. 组合机床与自动化加工技术, 2012(10):16-18.

QI Xiaoning, WANG Yongchao, JIA Jing, et al. The Scheduling of Machine for Green Manufacturing Based on Genetic Algorithm[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2012(10):16-18.

[8] XU Y, WANG L, WANG S. An Effective Shuffled Frog-leaping Algorithm for the Flexible Job-shop Scheduling Problem[C]∥2013 IEEE Symposium on Computational Intelligence in Control and Automation (CICA). Singapore, 2013:128-134.

[9] CHIANG T C, LIN H J. A Simple and Effective Evolutionary Algorithm for Multi-objective Flexible Job Shop Scheduling[J]. International Journal of Production Economics, 2013, 141(1):87-98.

[10] LIU H, ABRAHAM A, GROSAN C. A Novel Variable Neighborhood Particle Swarm Optimization for Multi-objective Flexible Job-shop Scheduling Problems[C]∥2nd International Conference on Digital Information Management. Lyon: IEEE, 2007:138-145.

[11] WANG L, WANG S, LIU M. A Pareto-based Estimation of Distribution Algorithm for the Multi-objective Flexible Job-shop Scheduling Problem[J]. International Journal of Production Research, 2013, 51(12):3574-3592.

[12] 雷德明. 基于新型教学优化算法的低碳柔性作业车间调度[J]. 控制与决策, 2017, 32(9):1621-1627.

LEI Deming. Novel Teaching-learning-based Optimization Algorithm for Low Carbon Scheduling of Flexible Job Shop[J]. Control and Decision, 2017, 32(9):1621-1627.

[13] LU C, GAO L, LI X Y,et al. A Multi-objective Approach to Welding Shop Scheduling for Makespan, Noise Pollution and Energy Consumption[J]. Journal of Cleaner Production, 2018,196:773-787.

[14] KARABOGA D. An Idea Based on Honey Bee Swarm for Numerical Optimization[R]. Kayseri:Erciyes University, 2005.

[15] ZOU W, ZHU Y, CHEN H, et al. Solving Multi-objective Optimization Problems Using Artificial Bee Colony Algorithm[J]. Discrete dynamics in Nature and Society, 2011(11):1-37.

[16] XIANG Y, ZHOU Y, LIU H. An Elitism Based Multi-objective Artificial Bee Colony Algorithm[J]. European Journal of Operational Research, 2015, 245(1):168-193.

[17] 张国辉, 高亮, 李培根,等.改进遗传算法求解柔性作业车间调度问题[J]. 机械工程学报, 2009, 45(7):145-151.

ZHANG Guohui, GAO Liang, LI Peigen, et al. Improved Genetic Algorithm for the Flexible Job-shop Scheduling Problem[J].Journal of Mechanical Engineering, 2009, 45(7):145-151.

[18] BRANDIMARTE P. Routing and Scheduling in a Flexible Job Shop by Tabusearch[J]. Annals of Operations Research, 1993, 41(3):157-183.

[19] SINGH M R, SINGH M, MAHAPATRA S S, et al. Particle Swarm Optimization Algorithm Embedded with Maximum Deviation Theory for Solving Multi-objective Flexible Job Shop Scheduling Problem[J]. The International Journal of Advanced Manufacturing Technology, 2016, 85(9/12):2353-2366.

[20] ZHANG R, SONG S, WU C. A Hybrid Differential Evolution Algorithm for Job Shop Scheduling Problems with Expected Total Tardiness Criterion[J]. Applied Soft Computing, 2013, 13(3):1448-1458.

[21] 陈辅斌, 李忠学, 杨喜娟. 基于改进 NSGA2 算法的多目标柔性作业车间调度[J]. 工业工程, 2018, 21(2):55-61.

CHEN Fubin, LI Zhongxue, YANG Xijuan. Multi-objective Flexible Job Shop Scheduling Based on Improved NSGA2 Algorithm[J].Industrial Engineering Journal, 2018, 21(2):55-61.

Research on Multi-objective Green Flexible Job-shop Scheduling Based on Improved ABC Algorithm

LI Yibing1,2 HUANG Weixing1 WU Rui1

1.School of Mechanicaland Electronic Engineering,Wuhan University of Technology,Wuhan,430070 2.Hubei Key Laboratory of Digital Manufacturing,Wuhan University of Technology,Wuhan,430070

Abstract: Aiming at the characteristics of multi-objective green flexible job-shop scheduling problem (MGFJSP), three indicators of carbon emissions, noises and wastes were proposed to evaluate the degree of environmental pollution comprehensively. A MGFJSP model was established with the optimization goals of minimizing the makespan and the degree of environmental pollution. And the improved ABC algorithm was proposed to solve this model. The specific improvements of algorithm included: a three-dimensional vector coding schemne and the corresponding decoding scheme were designed, an effective dynamic neighborhood search operation was introduced to improve the local search ability of the algorithm in the follow bee search stage, and a strategy for generating new food sources was proposed to increase the diversity of the population in the bee detection stage. Finally, the experimental study and algorithm comparison were carried out to verify the validity of the established model and the proposed algorithm.

Key words: green flexible job-shop scheduling; multi-objective optimization; environmental pollution; artificial bee colony(ABC) algorithm

中图分类号TP18

DOI:10.3969/j.issn.1004-132X.2020.11.011

开放科学(资源服务)标识码(OSID):

收稿日期2019-02-20

基金项目国家自然科学基金资助项目(51705384,51875430)

(编辑 胡佳慧)

作者简介李益兵,男,1978年生,教授。研究方向为车间调度与优化算法、机械设备故障诊断。出版专著1部,发表论文20余篇。E-mail:ahlyb@whut.edu.cn。吴 锐(通信作者),男,1989年生,博士研究生。研究方向为车间调度及优化算法。发表论文5篇。E-mail:wurui@whut.edu.cn。