<-上一篇/Previous Article 下一篇/Next Article->

[1]郭丽萍,李向涛,谷文祥,等.改进的萤火虫算法求解阻塞流水线调度问题[J].智能系统学报,2013,8(1):33-38.[doi:10.3969/j.issn.1673-4785.201205012]
　GUO Liping,LI Xiangtao,GU Wenxiang,et al.An improved firefly algorithm for the blocking flow shop scheduling problem[J].CAAI Transactions on Intelligent Systems,2013,8(1):33-38.[doi:10.3969/j.issn.1673-4785.201205012]

点击复制

改进的萤火虫算法求解阻塞流水线调度问题

PDF下载 HTML

《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷: 8 期数: 2013年第1期页码: 33-38 栏目: 学术论文—智能系统出版日期: 2013-03-25

Title:: An improved firefly algorithm for the blocking flow shop scheduling problem

文章编号:: 1673-4785(2013)01-0033-06

作者:: 郭丽萍¹，李向涛¹，谷文祥^1,2，殷明浩¹; 1.东北师范大学计算机科学与信息技术学院，吉林长春 130117；
2.长春建筑学院基础教学部，吉林长春 130607

Author(s):: GUO Liping¹, LI Xiangtao¹, GU Wenxiang ^1,2 , YIN Minghao¹; 1. Department of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China;
2. Department of Basic Subjects Teaching, Changchun Architecture & Civil Engineering College, Changchun 130607, China

关键词:: 阻塞流水线调度问题; 萤火虫算法; 离散机制; NEH启发式; 局部搜索

Keywords:: blocking flow shop scheduling problem; firefly algorithm; discrete mechanism; NEH heuristic method; local search

分类号:: TP301.6

DOI:: 10.3969/j.issn.1673-4785.201205012

文献标志码:: A

摘要:: 为了提高阻塞流水线调度问题的求解性能，提出了一种改进的萤火虫算法来求解阻塞流水线调度问题.首先，提出一种离散机制把个体的实数编码形式转换成离散的作业序列，从而使算法能够应用于离散问题求解；其次，设计一种双重初始化方法，并将NEH启发式方法应用到初始化中来，使算法有一个较优的初始化环境，提高初始种群的解的质量；此外，重新设计了算法中个体的移动方式来增大搜索域；最后，以一定概率对种群中的个体进行局部搜索，加强算法的局部搜索性能.通过对Taillard数据集中部分实例进行求解，实验结果验证了新算法的有效性.

Abstract:: In order to improve the solving performance of the blocking flow shop scheduling problem, the researcher proposes to examine an improved firefly algorithm. Firstly, a discrete mechanism was proposed to convert the real coded form of individuals to discrete job sequences, so that the algorithm could be used to deal with discrete problems. Secondly, a doubleinitialization method was designed and the NEH (Nawaz Enscore Ham) heuristic method was applied to the initialization, which provided a superior initial environment and improved the quality of the solution of the initial population. In addition, the research paper focused on redesigning the movement pattern of individuals to enhance the search space. Finally, a local search algorithm was applied to individuals with a certain probability, for the purpose of enhancing the ability to search locally. The improved firefly algorithm was then tested utilizing the Taillard datasets, and the results verified the effectiveness of the new algorithm.

参考文献/References:: ［1］ALLAHYERDI A, NG C T, CHENG T C E, et al. A survey of scheduling problems with setup times or costs［J］. European Journal of Operational Research, 2008, 187(3): 985-1032.
［2］MCCORMICK S T, PINEDO M L, SHENKER S, et al. Sequencing in an assembly line with blocking to minimize cycle time［J］. Operations Research, 1989, 37(6): 925-935.
［3］RONCONI D P. A note on constructive heuristics for the flowshop problem with blocking［J］. International Journal of Production Economics, 2004, 87(1): 39-48.
［4］CARAFFA V, IANES S, BAGCHI T P, et al. Minimizing makespan in a blocking flowshop using genetic algorithms［J］. International Journal of Production Economics, 2001, 70(2): 101-115.
［5］RONCONI D P. A branch and bound algorithm to minimize the makespan in a flowshop with blocking［J］. Annals of Operations Research, 2005, 138(1): 53-65.
［6］GRABOWSKI J, PEMPERA J. The permutation flow shop problem with blocking. A tabu search approach［J］. Omega, 2007, 35(3): 302-311.
［7］WANG Ling, PAN Quanke, SUGANTHAN P N, et al. A novel hybrid discrete differential evolution algorithm for blocking flow shop scheduling problems［J］. Computers & Operations Research, 2010, 37(3): 509-520.
［8］YANG Xinshe. Nature inspired metaheuristic algorithms［M］. Frome, UK: Luniver Press, 2008: 81-96.
［9］YANG Xinshe. Firefly algorithms for multimodal optimization［C］//Proceedings of the 5th International Conference on Stochastic Algorithms: Foundations and Applications. Berlin/Heidelberg, Germany: Springer Verlag, 2009: 169-178.
［10］NAWAZ M, ENSCORE E E J, HAM I. A heuristic algorithm for the m machine, n job flow shop sequencing problem［J］. Omega, 1983, 11(1): 91-95.
［11］BROWN C T, LIEBOVITCH L S, GLENDON R. Lévy flights in Dobe Ju/’ hoansi foraging patterns［J］. Human Ecology, 2007, 35(1): 129-138.
［12］PAVLYUKEVICH I. Lévy flights, nonlocal search and simulated annealing［J］. Journal of Computational Physics, 2007, 226(2): 1830-1844.
［13］YANG Xinshe. Firefly algorithm, Lévy flights and global optimization［C］//Research and Development in Intelligent Systems XXVI. London, UK: Springer, 2010: 209-218.
［14］YANG Xinshe. Firefly algorithm, stochastic test functions and design optimization［J］. International Journal of Bio Inspired Computation, 2010, 2(2): 78-84.

相似文献/References:: [1]莫愿斌,马彦追,郑巧燕,等.单纯形法的改进萤火虫算法及其在非线性方程组求解中的应用[J].智能系统学报,2014,9(6):747.[doi:10.3969/j.issn.1673-4785.201309075]
　MO Yuanbin,MA Yanzhui,ZHENG Qiaoyan,et al.Improved firefly algorithm based on simplex method and its application in solving non-linear equation groups[J].CAAI Transactions on Intelligent Systems,2014,9():747.[doi:10.3969/j.issn.1673-4785.201309075]
[2]朱书伟,周治平,张道文.融合并行混沌萤火虫算法的K-调和均值聚类[J].智能系统学报,2015,10(6):872.[doi:10.11992/tis.201505043]
　ZHU Shuwei,ZHOU Zhiping,ZHANG Daowen.K-harmonic means clustering merged with parallel chaotic firefly algorithm[J].CAAI Transactions on Intelligent Systems,2015,10():872.[doi:10.11992/tis.201505043]
[3]魏伟一,文雅宏.一种精英反向学习的萤火虫优化算法[J].智能系统学报,2017,12(5):710.[doi:10.11992/tis.201706014]
　WEI Weiyi,WEN Yahong.Firefly optimization algorithm utilizing elite opposition-based learning[J].CAAI Transactions on Intelligent Systems,2017,12():710.[doi:10.11992/tis.201706014]
[4]贾鹤鸣,彭晓旭,邢致恺,等.改进萤火虫优化算法的Renyi熵污油图像分割[J].智能系统学报,2020,15(2):367.[doi:10.11992/tis.201809002]
　JIA Heming,PENG Xiaoxu,XING Zhikai,et al.Renyi entropy based on improved firefly optimization algorithm for image segmentation of waste oil[J].CAAI Transactions on Intelligent Systems,2020,15():367.[doi:10.11992/tis.201809002]
[5]赵嘉,陈丹丹,肖人彬,等.一种基于最大最小策略和非均匀变异的萤火虫算法[J].智能系统学报,2022,17(1):116.[doi:10.11992/tis.202106018]
　ZHAO Jia,CHEN Dandan,XIAO Renbin,et al.A heterogeneous variation firefly algorithm with maximin strategy[J].CAAI Transactions on Intelligent Systems,2022,17():116.[doi:10.11992/tis.202106018]

备注/Memo

收稿日期：2012-05-07.
网络出版日期：2013-01-25.
基金项目：国家自然科学基金资助项目（60803102, 61070084）. 
通信作者：郭丽萍.
E-mail: guolp281@nenu.edu.cn.
作者简介：
郭丽萍，女，1989年生，硕士研究生，主要研究方向为智能规划、智能信息处理. 李
向涛，男，1987年生，博士研究生，主要研究方向为智能规划、智能信息处理，发表学术论文多篇.
谷文祥，男，1947年生，教授，博士生导师，主要研究方向为智能规划与规划识别、形式语言与自动机理论、模糊数学及其应用.主持国家自然科学基金项目3项，发表学术论文100余篇.

更新日期/Last Update: 2013-04-12

改进的萤火虫算法求解阻塞流水线调度问题 PDF下载HTML

备注/Memo

改进的萤火虫算法求解阻塞流水线调度问题

PDF下载 HTML