求解改进布谷鸟算法的置换流水车间调度问题

doi:10.16180/j.cnki.issn1007-7820.2019.10.012

摘要/Abstract

摘要：

针对实际工况下置换流水车间调度问题,文中以最小化完工时间为目标对标准布谷鸟算法进行了改进。为提高优化解的稳定性和算法的计算精度,该算法将淘汰概率引入动态自适应机制,将局部搜索引入差分进化机制,并在初始种群的生成中引入NEH算法。文中将改进的布谷鸟算法运用于解决实际工况下的置换流水车间调度问题,通过与标准布谷鸟算法仿真优化结果进行对比,证明了改进布谷鸟算法具有更好的解的稳定性和更高的寻优精度。

关键词: 关置换流水车间调度, 布谷鸟搜索算法, 淘汰概率, 局部搜索, 差分进化机制, 最小化完工时间

Abstract:

Aiming at the problem of displacement flow shop scheduling under actual working conditions, the standard cuckoo algorithm was improved with the goal of minimizing the completion time. In order to improve the stability of the optimized solution and the computational accuracy of the algorithm, the proposed algorithm introduced the elimination probability into the dynamic adaptive mechanism. Besides, the proposed algorithm also introduced the local search into the differential evolution mechanism, and applied the NEH algorithm in the initial population generation. The improved cuckoo search was applied to solve the permutation flow shop scheduling problem under actual working conditions. The results showed that compared with the simulation optimization results of the standard cuckoo search, the improved cuckoo search had better stability and higher precision.

Key words: PFSP, cuckoo search, elimination probability, local search, differential evolution mechanism, makespan.

中图分类号:

TP301

邴孝锋,陶翼飞,董圆圆,孙思汉. 求解改进布谷鸟算法的置换流水车间调度问题[J]. 电子科技, 2019, 32(10): 60-64.

BING Xiaofeng,TAO Yifei,DONG Yuanyuan,SUN Sihan. Solving the Problem of Replacement Flow Shop Scheduling Based on Improved Cuckoo Algorithm[J]. Electronic Science and Technology, 2019, 32(10): 60-64.

图/表 8

图1

图2

图3

表1

表2

表3

图5

图6

参考文献 18

[1]	惠晓龙, 郜振鑫 . 一种基于Petri网的多目标无死锁蚁群调度算法[J]. 电子科技, 2014,27(5):179-181.
	Hui Xiaolong, Gao Zhenxin . A multi-objectivedeadlock-free ant colony scheduling algorithm based on petri nets[J]. Electronic Science and Technology, 2014,27(5):179-181.
[2]	王春, 田娜, 纪志成 , 等. 求解模糊柔性作业车间调度的多目标进化算法[J]. 电子学报, 2017,45(12):2909-2916.
	Wang Chun, Tian Na, Ji Zhicheng , et al. Multi-objective evolutionary algorithm for solving fuzzy flexible job shop scheduling[J]. Acta Electronica Sinica, 2017,45(12):2909-2916.
[3]	马祎航, 陶文华, 刘阳 . 基于双模式PSO算法求解置换流水车间调度问题[J]. 电子设计工程, 2016,24(15):1-4.
	Ma Weihang, Tao Wenhua, Liu Yang . Study on the problem of permutation flow shop scheduling based on dual-mode PSO algorithm[J]. Electronic Design Engineering, 2016,24(15):1-4.
[4]	谢展鹏, 张超勇, 邵新宇 , 等. 基于Memetic算法的有限缓冲区流水车间调度问题[J]. 计算机集成制造系统, 2015,21(5):1253-1261.
	Xie Zhanpeng, Zhang Chaoyong, Shao Xinyu , et al. The finite buffer flow shop scheduling problem basedon Memetic algorithm[J]. Computer Integrated Manufacturing Systems, 2015,21(5):1253-1261.
[5]	吴斌, 陈佳华, 李玉 , 等. 物流领域的“JIT”——越库调度[J]. 油气储运, 2018,37(2):143-149.
	Wu Bin, Chen Jiahua, Li Yu , et al. “JIT” in the field of logistics - cross-docking scheduling[J]. Oil and Gas Storage and Transportation, 2018,37(2):143-149.
[6]	曹夏夏, 唐加福, 刘黎黎 . 基于集划分的精确算法求解机场接送车辆调度问题[J]. 系统工程理论与实践, 2013,33(7):1682-1689.
	Cao Xiaxia, Tang Jiafu, Liu Lili . Accurate algorithm based on set partition for solving airport shuttle vehicle scheduling problem[J]. Systems Engineering Theory & Practice, 2013,33(7):1682-1689.
[7]	刘志英, 代乙君, 隋毅 . 具有复杂缓冲的分段多流水车间调度问题[J]. 哈尔滨工程大学学报, 2014(7):875-882.
	Liu Zhiying, Dai Yijun, Sui Yi . Segmented multi-flow shop scheduling problem with complex buffer[J]. Journal of Harbin Engineering University, 2014(7):875-882.
[8]	唐海波, 叶春明, 张新功 . 应用模拟植物生长算法求解置换流水车间调度问题[J]. 计算机应用研究, 2010,27(10):3670-3672.
	Tang Haibo, Ye Chunming, Zhang Xingong . Application of simulated plant growth algorithm to solve displacement flow shop scheduling problem[J]. Journal of Co-mputer Applications, 2010,27(10):3670-3672.
[9]	王宇嘉, 聂善坤, 肖闪丽 . 基于动态多种群的粒子群优化算法[J]. 电子科技, 2017,30(7):9-12.
	Wang Yujia, Nie Shankun, Xiao Shanli . Particle swarm optimization algorithm based on dynamic multi-group[J]. Electronic Science and Technology, 2017,30(7):9-12.
[10]	Rahman H F, Sarker R, Essam D . A Genetic algorithm for permutation flow shop scheduling under make to stock production system[J]. Computers & Industrial Engineering, 2015,90(C):12-24.
[11]	Zabihzadeh S S, Rezaeian J . Two meta-heuristic algorithms for flexible flow shop scheduling problem with robotic transportation and release time[J]. Applied Soft Computing, 2016,40(7):319-330.
[12]	徐杨丽, 叶春明 . 布谷鸟算法求解置换流水车间调度问题[J]. 数学理论与应用, 2015(3):89-96.
	Xu Yangli, Ye Chunming . Cuckoo algorithm for solving permutation flow shop scheduling problem[J]. Journal of Matuhematical Theory and Application, 2015(3):89-96.
[13]	段鹏飞, 余杰, 聂慧 , 等. 求解广义优先关系下多技能人员项目调度问题的改进布谷鸟搜索算法[J]. 计算机应用研究, 2018,35(5):1315-1319.
	Duan Pengfei, Yu Jie, Nie Hui , et al. Improvedcuckoo search algorithm for multi-skilled project schduling problem under generalized priority relationship[J]. Application Research of Computers, 2018,35(5):1315-1319.
[14]	胡欣欣 . 求解函数优化问题的改进布谷鸟搜索算法[J] 计算机工程与设计, 2013,34(10):3639-3642.
	Hu Xinxin . Improved cuckoo search algorithm for solving function optimization problems[J]. Computer Engineering and Design, 2013,34(10):3639-3642.
[15]	吴炅, 周健勇 . 整数规划的布谷鸟算法[J]. 数学理论与应用, 2013(3):99-106.
	Wu jiong Zhou Jianyong, . The cuckoo algorithm for integer programming[J]. Mathematical Theory andApplication, 2013(3):99-106.
[16]	Fuqing Zhao, Yang Liu, Yi Zhang , et al. A hybrid harmony search algorithm with efficient job sequence scheme and variable neighborhood search for the permutation flow shop schedulingproblems[J]. Engineering Applications of Artificial Intelligence, 2017,65(3):9-22.
[17]	陈乐, 龙文 . 求解工程结构优化问题的改进布谷鸟搜索算法[J]. 计算机应用研究, 2014,31(3):679-683.
	Chen Le, Long Wen . Improved cuckoo search algorithm for solving engineering structure optimization problems[J]. Journal of Computer Applications, 2014,31(3):679-683
[18]	赵平, 吴昊 . 差分进化混合粒子群算法求解装配式住宅项目进度优化问题[J]. 计算机工程与科学, 2016,38(7):1495-1501.
	Zhao Ping, Wu Hao . Differential evolution hybrid particle swarm optimization algorithm for solving the progress of assembly projects[J]. Computer Engineering and Science, 2016,38(7):1495-1501.

Job	M₁	M₂	M₃	M₄	M₅	M₆
1	1,0.5²	2,0.5²	1,0.3²	1,0.5²	8,0.2²	7,0.5²
2	1,0.2²	1,0.2²	1,0.5²	3,0.5²	10,0.5²	8,0.2²
3	2,0.5²	2,0.5²	2,0.3²	2,0.2²	5,0.2²	6,0.5²
4	3,0.5²	3,0.3²	1,0.2²	1,0.5²	7,0.5²	6,0.3²
5	5,0.8²	2,0.2²	1,0.3²	2,0.5²	5,0.2²	7,0.5²
6	3,0.5²	1,0.5²	2,0.5²	4,0.3²	3,0.5²	8,0.5²
7	1,0.3²	2,0.5²	2,0.3²	2,0.5²	5,0.2²	9,0.3²
8	1,0.5²	1,0.3²	1,0.5²	5,0.3²	10,0.5²	7,0.5²
9	1,0.3²	4,0.5²	1,0.3²	5,0.5²	5,0.2²	7,0.5²
10	3,0.5²	1,0.5²	2,0.5²	4,0.5²	7,0.5²	9,0.3²

性能指标	布谷鸟算法	改进后的布谷鸟算法
Min	23 798	22 600
Avg	24 159.6	23 469.2
Avg-FI	28.15	21.5
SD	317.69	304.80
Cousume	599.05	579.75