基于NEM的置换流水车间调度算法

2019-06-11 03:39:57 计算技术与自动化2019年1期

摘要:对类电磁机制算法进行优化设计,提出基于NEM求解置换流水车间调度问题的算法。该算法将通过引入随机键的编码方式?#25237;?#36739;差粒子进行变异的操作方式,以提高算法求解的精度和收敛的速度。最后将通过仿真实验验证该算法的?#34892;?#24615;。

关键词:类电磁机制算法;NEM;调度;变异

中图分类号:TP3

文献标识码A

置换流水车间调度问题(Permutation Flow ShopScheduling Problem,PFSP)广泛存在于生产系统和服务系统中,是典型的组合优化问题,也是典型的NP难问题[1]。PFSP的求解方法很多:构造型启发式算法,能够快速地构造解,但解的质量和算法通用性通常较差;基于物理或仿生学原理的改进型调度算法,能以较大概?#35797;誑尚?#26102;间范围内求得该问题的近似最优解,但其复杂度一般较大,并且算法的结构和参数都需要进行?#40092;?#30340;设定才能达到预期的效果[2]。针对?#40092;?#24773;况,提出基于NEM求解置换流水车间调度问题的算法。该算法在求解PFSP时,将提出对较差粒子进行变异操作这一思想,以提高算法的求解精度并加快算法的收敛速度。最后将通过实验仿真验证基于NEM求解PFSP算法的?#34892;?#24615;。

1 NEM算法简介[3]

通过对EM算法的初始化、局部搜索、合力计算和粒子移动?#27597;?#27493;骤分别进行改进,并在此基础上提出一种实用的类电磁机制算法——归?#25442;?#31867;电磁机制算法( Normalization Electromagnetism-likeMechanism,NEM)。对EM算法“复杂度较大?#38381;?#19968;缺陷,采用归?#25442;?#26041;法,使得目标函数值都在某个小范围内,这样就可以减少运算量。针对EM算法局部搜索和计算合力中的缺陷,采用去掉易产生溢出错误的分母部分‖xj-xi2,添加一个合力计算修

2 NEM算法的改进——变异操作

为了扩大?#34892;?#25628;索范围,增强算法的全局搜索能力,根据优胜劣汰原则,在不增?#26377;?#31890;子的情况下,将最差的几个粒子进行变异操作后,选择变异后的较优粒子替换原来的最差粒子,以便得到更优的解。当粒子数不小于30时,选择变异当前粒子群中最差的5个粒子,当粒子数小于30时,略过此步。这么做是由于当粒子数过少时,变异步骤会扰乱类电磁机制算法的收敛趋势,并?#19968;?#38477;低算法的收敛速度。

实现这一步骤比较简单,首先按目标函数值的大小将粒子进?#20449;?#24207;,目标函数值较大的排在后面,然后选择最后的5个粒子进行变异操作。变异操作方式分为?#25442;?#21464;异、插入变异和反转变异,三种变异方式如图1所示。

对选出的5个最差粒子分别使用这三种方式进行变异操作,共产生15个新粒子。从中选取5个最优的粒子替换原粒子队列中最后的5个粒子,最后再计算目标函数值并进行重新排序,更新当前最优值。

3 随机键的引入

在一些离散型的优化问题中,为了方便对解直接进行数学操作,广泛采用了随机键的编码方式[4]。本文在基于NEM算法解决PFSP问题时,也借用随机键的编码方式模拟工件的排序。

随机键的编码方式就是将解转换表示为一串(0,1)之间的随机数,并将这串随机数用作解码时的分类键。例如一个9工件问题的调度方案:[0.82, 0.23, 0.45, 0.74, 0.87, 0.11,0.56, 0.69, 0.78],其中,编码中的位置代表工件,处在位置的随机数代表工件的排列顺序。将这些随机数按照升序(工件的加工顺序)进?#20449;?#21015;,可得?#26053;?#30340;排序:8-2-3-6-9-1-4-5—7。这种编码方式可以消除NEM算法在求解过程中产生的不?#23578;?#35299;。

随机键与工件排序的转换方式如图2所示。首先将搜索到的粒子进行随机键转换,然后计算其适应值,接着再进行粒子的合力计算和移动操作,最后将移动后得到的粒子再进行随机键转换,进入下一轮的循环。

4 算法设计与实现

通过随机键编码方式的引入,将离散型工件排序编码转变成NEM算法可直接使用的连续型编码。将总的完工时间看作目标函数,其值越小,则解的适应度值就越高。使用随机方式初始化种群粒子,当算法迭代次数到达预先设定的某个值时自动停止。算法的局部搜索采用最简单的方式一仅对最优粒子采取局部搜索。在规定的最大迭代次数内,对当前最优粒子的每一维随机均匀地按照一定步长进行局部搜索。在?#26031;?#31243;中,如果?#19994;?#26356;优的解,则用其替换当前最优粒子。基于NEM的PFSP算法的流程如图3所示。

5 实验结果与分析

实验选取29个应用广泛的Benchmark问题进行性能测试,并与传统GA和NEH作比较。这29个Benchmark问题指Carlier( 1978)提出的8个算例Carl,Car2,…,Car8和Tailland( 1993)提出的21个算例Rec01,Rec03,…,Rec41。NEM和GA分别对每个算例独立运行20次,最大迭代次数均设为300,粒子数均设为30。实验仿真结果如表1所示。表中,m和n分别表示机器数和工件数,c*表示问题的最优解,RE表示与最优解c*的相对误差(c heu max- c*)xl00%,BRE为最优相对误差,ARE为平均相对误差。

从表1可以看出,加入变异操作改进后的NEM算法具有很好的优化质量。尤其对Carlier系列问题,均能得到已知最优解,ARE也都小于GA。对Tailland系列问题也能够得到良好的近似最优解,且质量明?#26434;?#20110;方法GA和NEH,甚至NEM的最差结果都?#23545;?#20248;于NEH方法。由此可见,经过改进的NEM算法在优化质量方面相对于方法NEH和GA具有很大的优越性。

6 实例

某SMT生产线由高速贴装机HS60?#25237;?#21151;能贴装机80F5组成,产品设计为单面贴装。待贴装元器件共有42种,根据封装?#38382;?#21644;组装精度分别将这些元器件分配给HS60和80F5。分配给HS60的元器件为1~16,17~23必须分配到80F5?#29486;?#35013;,而24~42则两者皆可。?#20013;?#23545;24~42?#24067;?9种元器件进行EM算法优化分配,要求总的贴装时间最小,并且两种贴装机的贴装时间差不大于0.35s。42种元器件的贴装机分配、貼装时间以及数?#32771;?#34920;2-表4。

通过NEM算法的优化,所求得最优解为:(1,1,0,1,0,0,1,0,1,0,1,1,0,1,1,1,1,1,1)和(1,1,0,1,0,1,1,0,0,1,1,1,0,0,1,1,0,1,1),求解过程中获得了两个最优解。两个最优解的总贴装时间都是30.22s,THS60=15.26s,T80ES=15.26s,?#23548;?#36148;装时间差为ξ= 0.30s,符合生产线平衡的要求。

7 结束语

针对EM算法不能直接被?#32654;?#35299;决流水车间调度这类离散型优化问题的情况,通过引入随机键的编码方式将工序编码方式进行了转换,然后在NEM算法的基础上增添了变异操作从而对算法进行了改进,最后将改进后的NEM算法应用于解决离散型的流水车间调度问题。实验仿真结果表明,改进后的NEM算法成功地解决了流水车间调度问题。

参考文献

[1]刘敏,张超勇,张国军,等,基于混合粒子群优化算法的置换流水车间调度问题研究[J].中国机械工程,2011,22(17): 2048-2053.

[2] CEN M,CHENG R.Cenetic algorithm and engineering design[M]. Beijing: Science Press, 2000.

[3]姜建国,王双记,刘永青,等,一种实用的类电磁机制算法[J].西安电子科技大学学报,2013(02):48-53.

[4]KOLISCH R,HARTMANN S. Heuristic algorithms for solving theresource -constrained project scheduling problem: classificationand computational analysis [M]. WECIARZ J (editor): ProjectScheduling-Recent Models, Algorithms and Applications, KluwerAcademic Publishers. Boston. 1999:147.

?
湮灭者祖拉玛特打法
新时时彩走势图乐彩 排列七近1000走势图 王者荣耀攻略-鲁班七号攻略(出装,铭文等) 寻仙手游怎么出师 魂斗罗归来辅助外挂 新疆福彩3d走势图中彩网 二十二世纪古墓奇兵性物 法国南特商学院在哪个城市 哈德斯菲尔德大学学费 排球之窗微信公众号 快速时时彩计算方法如下 热血传奇最新版本 守望先锋多少分算高 竞彩足球推荐 20选5走势图开奖 星际争霸虫族兵种图鉴