一种动态双种群果蝇优化算法求解FJSP

计算机工程与科学

一种动态双种群果蝇优化算法求解FJSP

程子安,童鹰,申丽娟,于帅帅,李明

（西南林业大学机械与交通学院，云南昆明650000）

收稿日期:2015-06-11 修回日期:2015-09-16 出版日期:2016-09-25 发布日期:2016-09-25
基金资助:
国家自然科学基金(31100424)；西南林业大学科技创新基金（1460）

A dynamic double population fruit fly optimization algorithm for FJSP solution

CHENG Zi-an,TONG Ying,SHEN Li-juan,YU Shuai-shuai,LI Ming

（College of Machinery and Transportation,Southwest Forestry University,Kunming 650000,China）

Received:2015-06-11 Revised:2015-09-16 Online:2016-09-25 Published:2016-09-25

摘要/Abstract

摘要：

为了有效解决柔性作业车间调度问题（FJSP）,提出了一种具有较强进化机制的动态双种群果蝇优化算法（DDFOA），该算法采用自适应移动步长，并动态地将种群划分为先进子种群和后进子种群，其中先进子种群侧重局部搜索，后进子种群负责全局搜索。同时针对柔性作业车间调度问题，设计了合适的编码转化方案。最后，对算法的收敛性进行了证明，并选用经典算例对其进行仿真实验，仿真结果验证了DDFOA求解FJSP的有效性。

关键词: 柔性作业车间调度, 双种群, 果蝇优化算法, 邻域搜索

Abstract:

We propose an improved fruit fly optimization algorithm named dynamic double population fruit fly optimization algorithm (DDFOA) to solve the flexible job shop scheduling problem (FJSP). The DDFOA adopts a self-adaptive moving step length and divides the population into two parts, in which the backward sub population focuses on global search, and the advanced sub population is responsible for local search. Then, we design an appropriate code conversion program for the FJSP. The convergence of the proposed algorithm is proved. Simulation results on several benchmarks show that the DDFOA is an effective approach for solving the FJSP.

Key words: flexible job shop scheduling, double population, fruit fly optimization algorithm, neighborhood search

程子安,童鹰,申丽娟,于帅帅,李明. 一种动态双种群果蝇优化算法求解FJSP[J]. 计算机工程与科学.

CHENG Zi-an,TONG Ying,SHEN Li-juan,YU Shuai-shuai,LI Ming. A dynamic double population fruit fly optimization algorithm for FJSP solution [J]. Computer Engineering & Science.

参考文献

［1］Li Jun-qing,Pan Quan-ke,Suganthan P N.A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem［J］.International Journal of Advanced Manufacturing Technology,2011,52(5-8):683-697.
［2］Dai Min,Tang Dun-bing,Zheng Kun,et al.An improved genetic-simulated annealing algorithm based on a hormone modulation mechanism for a flexible flow-shop scheduling problem［J］.Advances in Mechanical Engineering,2013,13(2):260-280.
［3］Luan Fei,Wang Wen,Fu Wei-ping,et al.FJSP solving by improve GA based on PST hierarchy structure［J］.Computer Integrated Manufacturing Systems,2014,20(10):2494-2501.(in Chinese)
［4］Xing Li-ning,Chen Ying-wu,Wang Peng,et al.A knowledge-based ant colony optimization for flexible job shop scheduling problems［J］.Applied Soft Computing,2010,10(3):888-896.
［5］Moslehi G,Mahnam M.A pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search［J］.General Information,2011,129(1):14-22.
［6］Zhang Jing,Wang Wan-liang,Xu Xin-li,et al.Improve particle swarm algorithm for batch splitting flexible job shop scheduling［J］.Control and Decision,2012,27(4):513-518.(in Chinese)
［7］Pan Wen-chao.A new fruit fly optimization algorithm:Taking the financial distress model as an example［J］.Journal of Knowledge-Based Systems,2012,26(2):69-74.
［8］Pan Wen-chao. A new evolutionary computation approach:Fruit fly optimization algorithm［C］∥Proc of 2011 Conference on Digital Technology and Innovation Management,2012:1.
［9］Pan Wen-chao.Using fruit fly optimization algorithm optimized general regression neural network to construct the operating performance of enterprises model ［J］.Journal of Taiyuan University of Technology(Social Sciences Edition),2011,29(4):1-5.(in Chinese)
［10］Liu Cheng-zhong,Han Jun-ying.Adaptive fruit fly optimization algorithm based on bacterial migration ［J］.Computer Engineering & Science,2014,36(4):690-696.(in Chinese)
［11］Ning Jian-ping,Wang Bing,Li Hong-ru,et al.Research on and application of diminishing step fruit fly optimization algorithm ［J］.Journal of Shenzhen University Science and Engineering,2014,31(4):367-373.(in Chinese)
［12］Passino K M.Biomimicry of bacterial foraging for distributed optimization and control［J］.IEEE Control Systems Magazine,2002,22(3):52-67.
［13］Hansen P, Mladenovic N. Variable neighborhood search:Principles and applications［J］.European Journal of Operational Research,2001,130(3):449-467.
［14］Paolo B.Routing and scheduling in flexible job shop by tabu search［J］.Annals of Operations Research,1993,22(2):157-183.
［15］Pezzella F,Morganti G,Ciaschetti G.A genetic algorithm for the flexible job-shop scheduling problem［J］.Computers & Operation Research,2008,35(10):3202-3212.
［16］Jia H,Nee A,Fuh J,et al.A modified genetic algorithm for distributed scheduling problems［J］.International Journal of Intelligent Manufacturing,2003,14(3-4):351-362.
附中文参考文献:
［3］栾飞，王雯，傅卫平,等.基于PST层次结构的改进GA求解柔性车间调度问题［J］.计算机集成制造系统,2014,20(10):2494-2501.
［6］张静，王万良，徐新黎,等.基于改进粒子群算法求解柔性作业车间批量调度问题［J］.控制与决策,2012,27(4):513-518.
［9］潘文超.应用果蝇优化算法优化广义回归神经网络进行企业经营绩效评估［J］.太原理工大学学报（社会科学版）,2011,29(4):1-5.
［10］刘成忠，韩俊英.基于细菌迁徙的自适应果蝇优化算法［J］.计算机工程与科学,2014,36(4):690-696.
［11］宁剑平，王冰，李洪儒,等.递减步长果蝇优化算法及应用［J］.深圳大学学报（理工版）,2014,31(4):367-373.

[1]	张铸, 饶盛华, 张仕杰. 一种新型的混沌步长果蝇优化算法[J]. 计算机工程与科学, 2020, 42(04): 755-760.
[2]	陈明扬，王林，余晓晓. 改进果蝇算法优化回声状态网络的旅游需求预测研究[J]. 计算机工程与科学, 2020, 42(02): 307-316.
[3]	段兴锋1,2,任鸿翔1,神和龙1. 基于CUDA的弱可压SPH流体建模与仿真[J]. 计算机工程与科学, 2018, 40(08): 1375-1382.
[4]	王英博1，王艺星2. 基于SQP局部搜索的多子群果蝇优化算法[J]. 计算机工程与科学, 2018, 40(05): 906-915.
[5]	范朝冬1,任柯1,易灵芝1,肖乐意2，朱彪明1,李杰1. 双种群分子动理论优化算法[J]. 计算机工程与科学, 2018, 40(04): 723-730.
[6]	张磊1,刘成忠2. 一种面向多模函数改进的果蝇优化算法[J]. 计算机工程与科学, 2017, 39(01): 206-214.
[7]	高雷阜，赵世杰，于冬梅，徒君. 果蝇耦合均匀设计算法及其优化SVM参数[J]. J4, 2016, 38(05): 954-959.
[8]	胡廉民1,2,张九华1,常永耘3,黄翰3. 求解护士排班问题的可变邻域搜索遗传算法[J]. J4, 2013, 35(5): 149-153.
[9]	宋亚男1，徐荣华1，叶家玮2. 混合算法的邻域结构变更研究及在排样问题上的应用[J]. J4, 2011, 33(2): 173-178.