基于协同奔袭自适应狼群算法的双车间优化调度

梁 迪, 薛 健, 赵伊诺

(沈阳大学 机械工程学院, 辽宁 沈阳 110044)

目前车间调度研究大多以单一车间为对象,而实际生产工件加工的开始时间往往与前一车间息息相关,因此研究多车间的协同调度有助于使车间整体调度更优.已有众多学者将智能启发式算法应用到协同调度问题上,冯霞等[1]用遗传算法对机场的加油车和摆渡车协同调度问题进行了分析改进,提高了机场的运行效率.于大洋等[2]提出了电动汽车充电与风电协同调度碳减排效益的测算模型,证明了协同调度是实现风电和电动汽车规模化协调利用的一种有效手段,但目前针对生产车间协同调度方面的研究较少.狼群算法被国内外众多学者提出并改进,将其应用于调度及路径规划等问题上.冯晓莉等[3]将狼群算法结合模拟退火算法,提高了算法的全局收敛性与计算鲁棒性,并将其应用于求解复杂的并联泵站群优化运行模型上;周璟[4]提出了混沌狼群围捕算法,在狼群围捕算法基础上,使用Tent混沌映射改进了狼群初始化方法,使狼群初始分布更加均匀,提高了车间内机器人导航规划的实时性,减少了导航路径长度;Seifi等[5]提出了灰狼和鲨鱼气味算法(GWO+SSO)的组合,并将其应用于多个边界约束下目标函数优化,实验结果证明该方法在全局极小值上具有较高的收敛性.以上学者在算法上的改进皆是提高算法的有效性及准确性,但在算法运行速度与收敛速度上收效不明显.

本文在已有学者提出的的三级领导式狼群算法[6]基础上进行改进:为了加快算法搜索效率,结合粒子群算法和细菌觅食算法,在“狼群围攻”阶段融入粒子群算法特点,加入自适应步长;为了提高算法后期收敛速度,在“强者生存”环节融入细菌算法特点,淘汰适应度最差的一半狼,并将剩余的一半狼复制.文中对案例企业车间调度问题进行分析建模,并用MATLAB进行求解.

1 协同奔袭策略的狼群优化算法(CAWPA)

初始狼群算法(wolf pack algorithm,WPA)是学者模拟自然界狼群的围捕猎物行为提出的,其中抽象出搜索行为、围攻行为和更新行为[7].2013年吴虎胜等[8]提出了一种全新的狼群算法,更加细致地将狼群分成头狼、探狼、猛狼3大类.

为了使算法搜索最优值的范围更加全面广泛,将领导狼设置为3匹,让它们分别带领狼群搜索最佳解,这样不仅避免了原始狼群算法易陷入最优的问题,而且加快了全局的搜索速度和精确度.CAWPA算法的流程如图1所示.

图1 CAWPA算法流程图Fig.1 Flow chart of CAWPA algorithm

1.1 初始化狼群

在搜索区域内,随机将狼群的位置初始化,即

(1)

式中,1≤l≤L.

然后根据式(1)初始化第i匹狼在最初始迭代时的位置为

(2)

式中:xi为狼群的位置分布;xmax为狼群可活动的最大范围;xmin为狼群可活动的最小范围;e为一个随机数值,取值在[0,1]之间.

1.2 “3匹头狼”领导式奔袭行为

首先选取适应度最大的狼作为头狼,记为α狼,然后依次选取适应度第2和第3的狼作为第2领导狼和第3领导狼,记为β狼和δ狼,其余狼群记为ω狼[9].

α狼、β狼和δ狼的适应度分别记为fα、fβ、fδ,并记3匹狼的适应度之和为f,即

f=fα+fβ+fδ.

(3)

2匹狼之间的距离采用欧式距离描述,Xi狼与α狼之间的距离公式为

(4)

(5)

Xi狼与δ狼之间的距离公式为

(6)

记3个距离之和为l,

l=lα+lβ+lδ.

(7)

因此,“3匹头狼”领导的奔袭方式为

1.3 围攻行为

算法后期,将头狼位置示为猎物位置,围攻过程公式为

(9)

1.4 “适者生存”策略

原算法中[10],在淘汰阶段会淘汰适应度比较差的R匹狼,重新随机生成R匹狼,R为在范围[N/ (2χ),N/χ]中的一个随机正整数,其中χ表示淘汰狼数的比例因子,这样做增大了算法的计算时间[11].本文参考细菌觅食算法,把细菌觅食算法特点融入狼群算法,将适应度较低的一半狼淘汰,然后直接将剩余的一半较强的狼复制[12].这样不仅可以使算法在设置参数的过程中更简单,而且也会保留多次迭代之后适应度较高的狼.

2 实验仿真

金属结构件的制造属于多品种、小批量的生产方式,生产过程中产生的中间零部件规格繁多[13].现有车间调度问题的研究主要是优化单一车间的生产效率最优,缺少统一的协同调度[14],使上下游车间无法达到整体最优.因此,有必要进行科学合理的协同生产调度,从而减少在制品库存,缩短产品总完工时间,提高生产效率.

本文主要考虑切割车间与机械加工车间协同调度问题,切割车间是典型的并行机调度问题(parallel machine scheduling problem,PMSP),而机械加工车间的生产安排为流水线调度问题(flow scheduling problem,FSP).但是在同时考虑2个车间的生产时并不能简单地将PMSP作为流水调度车间的一道工序,因为在机械加工车间加工的零件在并行机部分是合并加工的,多个零件合并在一张板材上加工.因此切割车间与机械加工车间需要协同调度.

结构件切割车间板材的切割过程分为准备、加工与收件3个阶段.准备时间为切割之前将板材放到固定架上的时间;加工时间与设备切割的速度相关,而切割速度则与板材材质有关;收件时间为完成切割之后,需要对切割得到的零件进行收集整理的时间[15].每种板材的准备时间和收件时间均与板材大小有关,而且是固定值,所以加工时间由板材和切割设备共同决定.

经过切割后得到的零件直接送往机械加工车间进行加工,每个零件按相同顺序经过每个机械加工机器,每台机器上各零件加工顺序一致,工艺程序如图2所示.

图2 双车间工艺程序Fig.2 Process of dual workshop

2.1 建立数学模型

2.1.1 切割阶段

约束各板材完工时间为

(10)

式中:n为切割阶段板材的数量;m为切割阶段机器的数量;Cip代表板材i在机器p上的完工时间;Cgp代表板材g在机器p上的完工时间;g是板材i在机器p上的前序板材;STi为板材i在切割阶段的准备时间;Li为板材i的切割长度;vip为板材i在机器p上的切割速度;PTi为板材i在切割阶段的收件时间.

2.1.2 加工阶段

计算零件完工时间和最大完工时间.

(11)

式中:Cjq为零件j在机器q上的完工时间;n′为机械加工阶段零件的数量;m′为机械加工阶段机器的数量;j为机械加工阶段零件的序号;q为机械加工阶段机器的序号;Tjq为机械加工阶段零件j在机器q上的加工时间.

最大完工时间Cmax≥Cjq.

2.2 实验设计与参数设置

板材的切割速度通过矩阵V随机生成,

例如,同一种板材可以在第1列(切割机器1)上以速度1切割,也可以以速度2在第2列(切割机器2)上切割,但不能在第3列(切割机器3)上切割.板材的数量n设置为5、10、15,需加工的板材材质设为3种,切割车间机器数量m设置为3,切割长度服从U[100,200]分布,准备时间ST服从U[1,25]分布,收件时间PT服从U[1,25]分布.机械加工阶段零件数量n′设置为20、40、60、80.机械加工流水车间机器数量设置为4,其中加工的准备时间包含在加工时间内,加工时间服从U[1,40]分布的整数,所有零件的加工时间一致.

基础种群大小为100,迭代次数设置为10(n+n′),GA算法交叉概率为1,变异概率为0.1,CAWPA算法游走概率为1,奔袭概率为0.1.

2.3 实验结果及对比

为评价本文提出的CAWPA算法的表现, 本文引入GA算法和GWO算法求解该问题. 3种算法独立运行20次, 选取运算结果的平均值、最小值、相对百分比偏差和标准差4个指标来评价算法的能力. 具体如表1～表4所示.

实验的运行环境是Window 10系统,Intel(R) Core(TM)i7-8750HCPU@ 2.20 GHz 2.21 GHz,运行内存16.0 GB.最优结果用星号标出.

表1 5、10、15个板材在不同零件数下算法运行结果的平均值对比Table 1 Comparison of the average value of algorithm running results of 5, 10, and 15 plates with different parts numbers min

表2 5、10、15个板材在不同零件数下算法运行结果的最小值对比Table 2 Comparison of the minimum value of algorithm running results of 5, 10, and 15 plates with different parts numbers min

表3 5、10、15个板材在不同零件数下算法运行结果的相对百分比偏差对比Table 3 Comparison of relative percentage deviations of algorithm running results of 5, 10, and 15 plates with different parts numbers %

表4 5、10、15个板材在不同零件数下算法运行结果的标准差对比Table 4 Comparison of the standard deviation of the algorithm running results of 5, 10, and 15 plates with different parts numbers

通过对表1～表4的数据对比分析可知,改进后的CAWPA算法相较于GA算法与GWO算法更优秀.在切割阶段板材数量为5时,GWO算法也能取得与CAWPA算法相似的最优解,但是随着板材数量的增加,GWO算法也慢慢体现出后继无力的感觉,这说明GWO算法对于求解协同调度问题十分有效,但随着数据的增加,未作改进的GWO算法在处理速度上明显不尽人意.在平均解上CAWPA较其他2种算法更加稳定,数据也更加准确.

本文选取切割阶段板材数量5、机械加工阶段零件数量20为具体案例.迭代次数为10×(5+20)=250,得到双车间协同调度甘特图,如图3所示,其中M-Q-1～M-Q-3表示切割车间的第1、2、3台机器,M-G-1～M-G-4表示机械加工车间的第1、2、3、4台机器;S1代表切割阶段板材1,J1代表机械加工阶段零件1,以此类推.图中M-G-4为最后一个零件J16的完工时间,即为总加工时间,运行结果得出总加工时间为737 min.

图3 双车间协同调度甘特图Fig.3 Gantt chart for cooperative scheduling of dual workshop

图4 各算法迭代进化对比Fig.4 Comparison of iterative evolution of each algorithm

图4为3个算法的迭代进化对比图,从图中可以看出:在前20次迭代中,协同奔袭狼群算法在处理速度方面有明显优势,求解速度更快,搜索到较优解的时间更短,也更准确;GA算法虽然前期较GWO算法进化速度快,但容易陷入局部最优解;随着迭代次数的增加,通过将细菌觅食算法融入CAWPA算法的后期,使CAWPA算法能够在短时间内找到最优解,且不易陷入局部最优,而GWO算法虽然搜索最优解的能力较GA算法更强,但相比CAWPA算法进化速度比较慢.

3 结 论

本文提出了一种协同奔袭策略的狼群优化算法(CAWPA),以改进传统狼群算法对数据处理不准确且易陷入局部最优的问题.在前期搜索阶段,加入3匹头狼协同领导策略:α,β和δ3匹领导狼,使算法具有更全面的搜索范围,在游走行为加入交互策略以提高狼群沟通交互能力;在“猛狼围攻”环节,融入自适应步长机制,使得算法具有更快的收敛速度;在后期“强者生存”环节中模仿细菌觅食算法,去除适应度最差的2/N匹狼,复制剩余的2/N匹狼.将改进后的狼群算法应用在切割车间与机械加工车间协同调度问题上,选取了GA算法和GWO算法进行比较,共进行了4组实验,比较了平均值、最小值、相对百分比偏差和标准差,并选取1组具体案例,对比3种算法的迭代速度和得到最优解时间.实验结果证明CAWPA算法相比较于其他2种算法具有更准确的计算结果和更稳定的表现.