当前位置:文档之家 > 改进细菌觅食算法解决零空闲流水线调度问题

改进细菌觅食算法解决零空闲流水线调度问题

2015,51(17)零空闲流水线调度(NIFS ),即生产过程中不允许设备停止运转,是一类典型的生产调度问题。在集成电路、纺织和陶瓷等许多产品的生产过程中,存在一些特殊的设备,如价值昂贵、使用过程能量耗费大以及开启和停止都需较长的时间,基于生产成本考虑,是要求机器连续运转的,因此,零空闲流水线调度问题不仅具有重要的理论价值,还具备很强的实际意义[1]。研究表明[2],3台机器以上的NIFS 问题为NP-Hard 难题,关于其有效算法的研究已成为学术界和工程界的热点课题。目前,解决该类问题的方法主要分3种:经典优化算法、启发式方法和智能优化算法。经典优化算发如分支定界算法[3]在解决小规模问题的求解时取得了良好的效果,但随着问题规模的增大,算法耗时大,很难快速取得最优解;启发式方法(NEH 、SGM 、KK 、IGA_BA 、IGA_BA )相较于经典方法能较快地获取问题的解,但往往解的质量不高;随着计算智能技术的发展,智能优化算法已经成为解决该类问题的主要方法,包括离散差分进化算法[4]、离散粒子群算法[5-6]、和声搜索算法[7]、和

声搜索和模拟退火相结合的和声退火算法[8]、迭代贪心算法[9]以及蛙跳算法[10],另外还有禁忌搜索算法[11]和蚁群算法[12]。上述算法通常采用NEH 法产生质量较高的初始解,以提高算法的搜索速度,对初始解的质量有一改进细菌觅食算法解决零空闲流水线调度问题

李丽娟,吴晓,王志龙

LI Lijuan,WU Xiao,WANG Zhilong

西南交通大学机械工程学院,成都610031

School of Mechanical Engineering,Southwest Jiaotong University,Chengdu 610031,China

LI Lijuan,WU Xiao,WANG Zhilong.Research of no-idle flow shop scheduling based on improved bacteria foraging optimization http://www.doczj.com/doc/77ea3b10571252d380eb6294dd88d0d233d43c2f.html puter Engineering and Applications,2015,51(17):255-258.

Abstract :For No-Idle Flow shop Scheduling problem (NIFS )with the target of maximum makespan,a new solution named Improved Bacteria Foraging Optimization algorithm (IBFO )is proposed in this http://www.doczj.com/doc/77ea3b10571252d380eb6294dd88d0d233d43c2f.html pared to BFO,3modi-fications are added in IBFO.In the chemotaxis process,it introduces a crossover operator.During the process of reproduc-tion,it applies a hybrid strategy based on both health degree and target value of the bacterium.And for elimination pro-cess,it puts forward a self-adaption probability instead of a constant data.It tests IBFO through 6different size Taillard problems by MATLAB,the results indicate that IBFO is feasible and effective.Further,in order to test the algorithm ’s robustness to initial value,two methods are applied to get the initial bacterium population :random and NEH method.

Key words :No-Idle Flow shop Scheduling (NIFS );Bacteria Foraging Optimization algorithm (BFO );NEH heuristic algorithm;self-adaption migration probability;robustness

摘要:针对零空闲流水线调度问题,建立以最大完成时间为目标的数学模型,并提出了解决问题的改进细菌觅食优化算法。在标准细菌觅食优化算法的基础上,引入了交叉优化算子、混合复制策略以及一种基于健康度和适应度共同控制的自适应迁徙概率,以加速算法的收敛过程,并有效抑制精英个体的逃逸,防止解发生退化。采用路径编码方式,通过MATLAB 算例试验,表明了改进细菌觅食优化算法在求解零空闲流水线调度问题上的可行性和有效性;同时,运用两种方式产生初始解:随机方式和NEH 方法,进一步验证算法的鲁棒性。

关键词:零空闲流水线调度;细菌觅食优化算法;NEH 启发式算法;自适应迁徙概率;鲁棒性

文献标志码
:A 中图分类号:TP301.6doi :10.3778/j.issn.1002-8331.1309-0345

文献标志码:A 中图分类号:TP301.6doi :10.3778/j.issn.1002-8331.1309-0345

作者简介:李丽娟(1989—),女,硕士研究生,主要研究方向为生产调度;吴晓(1970—),男,博士,副教授,主要研究方向为工业工

程、机械结构强度和疲劳可靠性。E-mail :814975361@http://www.doczj.com/doc/77ea3b10571252d380eb6294dd88d0d233d43c2f.html

收稿日期:2013-09-24修回日期:2013-10-28文章编号:1002-8331(2015)17-0255-04

CNKI 网络优先出版:2014-02-24,http://www.doczj.com/doc/77ea3b10571252d380eb6294dd88d0d233d43c2f.html /kcms/doi/10.3778/j.issn.1002-8331.1309-0345.html Computer Engineering and Applications 计算机工程与应用

改进细菌觅食算法解决零空闲流水线调度问题

改进细菌觅食算法解决零空闲流水线调度问题

改进细菌觅食算法解决零空闲流水线调度问题

改进细菌觅食算法解决零空闲流水线调度问题

改进细菌觅食算法解决零空闲流水线调度问题

改进细菌觅食算法解决零空闲流水线调度问题

改进细菌觅食算法解决零空闲流水线调度问题

改进细菌觅食算法解决零空闲流水线调度问题

255