求解置换流水线调度问题的改进萤火虫优化算法

doi:10.11896/j.issn.1002-137X.2016.08.048

摘要/Abstract

摘要： 针对最小化最大完成时间的置换流水线调度问题,提出了一种改进的离散萤火虫优化算法。在传统萤火虫优化算法的基础上,采用基于升序排序的随机键编码方式对萤火虫种群进行离散化处理,使用NEH算法对萤火虫种群进行初始化处理,结合遗传算法的交叉变异思想改进位置更新策略,采用个体变异方式解决孤立个体问题,提高算法的寻优能力。最后通过典型算例对改进算法进行仿真测试,实验结果表明该算法求解置换流水线调度问题时具备很强的寻优能力和鲁棒性,明显优于传统萤火虫优化算法和遗传算法,是解决置换流水线调度问题的一种有效算法。

关键词: 置换流水线调度,萤火虫优化算法,NEH算法,位置更新策略

Abstract: An improved discrete glowworm swarm optimization (DGSO) was proposed for solving the permutation flow shop scheduling problem (PFSP) with the objective of minimizing makespan.On the basis of the traditional glowworm swarm optimization algorithm,this paper used a random key coding method based on the ascending order to discretize the glowworm swarm populations.Then it used the NEH algorithm to initialize the glowworm swarm populations,the idea of crossover and mutation thought in genetic algorithm was used to improve the location updating strategy,and individual mutation was used to resolve individual problems in isolation,improving the capability of algorithm optimization.Finally,the simulation test of the improved algorithm was carried out through typical examples.Simulation results show its efficiency and superiority for solving the PFSP.It is obviously better than the traditional glowworm swarm optimization and genetic algorithm,and it is an effective algorithm for solving flow shop scheduling problem.

Key words: Permutation flow shop scheduling problem,Glowworm swarm optimization algorithm,NEH algorithm,Location updating strategy

张丽红,余世明. 求解置换流水线调度问题的改进萤火虫优化算法[J]. 计算机科学, 2016, 43(8): 240-243. https://doi.org/10.11896/j.issn.1002-137X.2016.08.048

ZHANG Li-hong and YU Shi-ming. Improved GSO Algorithm for Solving PFSP[J]. Computer Science, 2016, 43(8): 240-243. https://doi.org/10.11896/j.issn.1002-137X.2016.08.048

参考文献

[1] Wang Ling,Wu Hao,Tang Fang.A Hybrid Quantum-Inspired Genetic Algorithm for Flow Shop Scheduling[J].Lecture Notes in Computer Science,2005,3654:636-644
[2] Wang L,Zhong D Z.An effective hybrid heuristic for flow shop scheduling[J].International Journal of Advanced Manufactu-ring Technology,2003,21:38-44
[3] Johnson S.Optimal two-and-three stage production scheduleswith setup time include[J].Naval Research Logistics Quarterly,1954,1:61-68
[4] Gupta J N.Two-stage hybrid Flow shop scheduling problem[J].Operational Research Society,1988,39(4):359-364
[5] Dannenbring D G.An evaluation of flow shop sequencing heuristics[J].Management Science,1977,23(11):1174-1182
[6] Nawaz M,Enscore J E,Ham I.A heuristic algorithm for the m-machine,n-job flow-shop sequencing problem[J].Omega,1983,11(1):91-95
[7] Gupta J N D,Chen C L,Yap L Y,et al.Designing a tabu search algorithm to minimize total flow time in a flow shop[J].Arabian Journal for Science and Engineering,2000,25(1C):79-94
[8] Rajendran C,Zieglerb H.Amt colony algorithms for permutation flow-shop scheduling problem to minimize makespan/total flowtime of jobs[J].European Journal of Operational Research,2004,155(2):426-438
[9] Krishnanand K N,Ghose D.Detection of multiple source locations using a glowworm metaphor with applications to collective robotics[C]∥Proc of IEEE Swarm Intelligence Symposium.Piscataway:IEEE Press,2005:84-91
[10] Huang Zheng-xin,Zhou Yong-quan.Self-adaptive step glowwormswarm optimization algorithm for optimizing multimodal functions[J].Computer Science,2011,32(10):220-224(in Chinese) 黄正新,周永权.自适应步长萤火虫群多模态函数优化算法[J].计算机科学,2011,38(7):220-224
[11] Liu Jia-kun,Zhou Yong-quan.Glowworm swarm optimizationalgorithm based on max-min luciferin[J].Application Research of Computers,2011,28(10):3662-3664(in Chinese) 刘佳昆,周永权.一种最大最小萤光素值人工萤火虫算法[J].计算机应用研究,2011,28(10):3662-3664
[12] Wu Wei-min,Kang Shao-jiang,Lin Zhi-yi,et al.Multimodalfunction optimisation based on improved glowworm swarm optimisation[J].Computer Applications and Software,2014(1):283-285,2(in Chinese) 吴伟民,亢少将,林志毅,等.基于改进萤火虫算法的多模函数优化[J].计算机应用与软件,2014,(1):283-285,302
[13] Davis L.Job shop scheduling with genetic algorithms[C]∥International Conference on Genetic Algorithms and Their Applications.Mahwah,NJ,Lawrence Eribaum Associate,1985:136-140
[14] Ge Hong-wei.The research of some optimization problemsbased on computational intelligence[D].Jilin:Jilin University,2006(in Chinese) 葛宏伟.基于计算智能的若干优化问题研究[D].吉林:吉林大学,2006
[15] Carlier J.Scheduling with disjunctive constraints[J].Operations Research,1978,12(4):333-350
[16] Taillard E.Scheduling instances.(2015-06-03).http://mistic.heg-vd.ch/taillard/problems.dir/ordonnancement.dr/ ordonnancement.html
[17] Wang Shu-ting.Studies on permutation flow shop scheduling using genetic algorithm variable neighborhood search[D].Changsha:Huazhong University of Science and Technology,2013(in Chinese) 王书婷.基于遗传变邻域算法的置换流水车间调度问题研究[D].长沙:华中科技大学,2013

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed