Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2023, Vol. 57 Issue (7): 1267-1277    DOI: 10.3785/j.issn.1008-973X.2023.07.001
自动化技术     
自适应樽海鞘群算法求解考虑运输时间的柔性作业车间调度
牛昊一(),吴维敏(),章庭棋,沈微,张涛
1. 浙江大学 工业控制技术国家重点实验室，浙江 杭州 310027
2. 浙江大学 智能系统与控制研究所，浙江 杭州 310027
Adaptive salp swarm algorithm for solving flexible job shop scheduling problem with transportation time
Hao-yi NIU(),Wei-min WU(),Ting-qi ZHANG,Wei SHEN,Tao ZHANG
1. State Key Laboratory of Industrial Control Technology, Zhejiang University, Hangzhou 310027, China
2. Institute of Cyber-Systems and Control, Zhejiang University, Hangzhou 310027, China
 全文: PDF(1024 KB)   HTML
摘要：

针对考虑运输时间的柔性作业车间调度问题，以最小化最大完工时间为优化目标，提出自适应樽海鞘群算法. 设计基于随机密钥方法的3层编码方案，将编码的离散解空间连续化. 引入惯性权重评价跟随者之间的相互影响程度，增强算法的全局探索与局部搜索能力. 提出自适应更新领导者-跟随者种群数量策略，根据种群迭代状态对领导者和跟随者的数量进行自适应调整. 在邻域搜索中引入禁忌搜索策略，防止算法陷入局部最优. 通过基准算例测试，验证了算法的有效性和优越性，发现AGV数量对完工时间的影响符合边际效应递减的规律.
关键词： 柔性作业车间调度;  运输时间;  樽海鞘群算法;  智能优化算法;  边际效应    
Abstract:

An adaptive salp swarm algorithm was proposed by minimizing the makespan in order to solve the flexible job shop scheduling problem with transportation time. A three-layer coding scheme was designed based on random key in order to make the discrete solution space continuous. The inertia weight was introduced to evaluate the influence among followers in order to enhance the global exploration and local search performance of the algorithm. An adaptive leader-follower population update strategy was proposed, and the number of leaders and followers was adjusted by the population status. The tabu search strategy was combined with the neighborhood search in order to prevent the algorithm from falling into local optimum. The benchmark instances verified the effectiveness and superiority of the proposed algorithm. The influence of the number of AGVs on the makespan conforms to the law of diminishing marginal effect.
Key words: flexible job shop scheduling    transportation time    salp swarm algorithm    intelligent optimization algorithm    marginal utility
收稿日期: 2022-07-26 出版日期: 2023-07-17
CLC:  TP 278  
通讯作者: 吴维敏     E-mail: hyniu@zju.edu.cn;wmwu@iipc.zju.edu.cn
作者简介: 牛昊一（1995—），男，博士生，从事智能优化算法的研究. orcid.org/0000-0001-7116-1440. E-mail： hyniu@zju.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　
牛昊一
吴维敏
章庭棋
沈微
张涛

引用本文:

牛昊一,吴维敏,章庭棋,沈微,张涛. 自适应樽海鞘群算法求解考虑运输时间的柔性作业车间调度[J]. 浙江大学学报(工学版), 2023, 57(7): 1267-1277.

Hao-yi NIU,Wei-min WU,Ting-qi ZHANG,Wei SHEN,Tao ZHANG. Adaptive salp swarm algorithm for solving flexible job shop scheduling problem with transportation time. Journal of ZheJiang University (Engineering Science), 2023, 57(7): 1267-1277.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2023.07.001    或    https://www.zjujournals.com/eng/CN/Y2023/V57/I7/1267

图 1  编码方案
图 2  工序排列编码的生成方式
图 3  工序排列编码的邻域搜索操作
图 4  邻域搜索的流程图
图 5  自适应樽海鞘群算法的流程图
案例 SSA WSSA LSSA TSSA ASSA
$C_{\max } $ $C_{\rm{{max}}}^{\rm{{avg}}} $ $\delta/ {\text{%}} $ $C_{\max } $ ${C_{\rm{{max}}}^{\rm{{avg}}} } $ $\delta / {\text{%}} $ ${C_{\max }} $ ${C_{\rm{{max}}}^{\rm{{avg}}} } $ $\delta / {\text{%}} $ ${C_{\max }} $ ${C_{\rm{{max}}}^{\rm{{avg}}} } $ $\delta / {\text{%}} $ ${C_{\max }} $ ${C_{\rm{{max}}}^{\rm{{avg}}} } $ $\delta / {\text{%}}$
EX11 96 98 0 96 97.4 0 96 97.8 0 96 96.8 0 96 96 0
EX21 106 108.8 3.92 105 108.3 2.94 106 108.9 3.92 104 106.9 1.96 102 103.4 0
EX31 107 111.7 8.08 108 111.8 9.09 110 113.7 11.11 113 108.5 14.14 99 103.7 0
EX41 122 125.4 8.93 119 125.4 6.25 121 124.1 8.04 120 122.5 7.14 112 114.8 0
EX51 88 89.2 1.15 88 89.6 1.49 88 90.2 1.15 88 88.5 1.15 87 87.1 0
EX64 136 140 13.33 134 138.9 11.67 128 137.9 6.67 130 137.2 8.33 120 126 0
EX74 142 145 10.94 136 142.8 6.25 142 145.3 10.94 136 142.8 6.25 128 133 0
EX84 165 171.1 1.23 165 171.3 1.23 165 170.6 1.23 166 170.4 1.84 163 163 0
EX94 128 133.5 6.67 131 133.8 9.17 128 131.3 6.67 123 128.7 2.50 120 122.6 0
EX104 175 182.8 10.06 179 183.2 12.58 174 180.5 9.43 171 179.1 7.55 159 166.5 0
平均值 — — 6.43 — — 6.07 — — 5.92 — — 5.09 — — 0.0
表 1  不同改进策略的加工完成时间对比结果
图 6  采用不同改进策略求解EX104的收敛曲线
案例 AGA IDSSA AAADE MOGWO ASSA
$t_{\rm{op }}/ {\rm{s}} $ ${C_{\max }} $ $\delta / {\text{%}} $ $t_{\rm{op }}/ {\rm{s}}$ ${C_{\max }} $ $\delta / {\text{%}} $ $t_{\rm{op }}/ {\rm{s}}$ ${C_{\max }} $ $\delta / {\text{%}} $ $t_{\rm{op }}/ {\rm{s}}$ ${C_{\max }} $ $\delta / {\text{%}} $ $t_{\rm{op }}/ {\rm{s}}$ ${C_{\max }} $ $\delta / {\text{%}} $
EX11 6.37 96 0 7.78 97 1.04 5.46 96 0 8.83 96 0 5.04 96 0
EX21 19.97 102 0 15.21 104 1.96 13.63 102 0 21.00 103 0.98 13.27 102 0
EX32 6.91 85 0 7.25 85 0 5.15 86 1.77 4.78 86 1.77 4.71 85 0
EX42 28.85 88 0 31.78 88 0 26.55 88 0 35.19 88 0 26.03 88 0
EX53 8.71 74 0 11.61 74 0 6.02 76 2.70 8.00 76 2.70 5.68 74 0
EX63 17.16 104 0.97 23.01 107 3.89 15.63 103 0 23.67 104 0.97 15.11 103 0
EX74 23.90 127 0 26.29 130 2.36 18.68 128 0.79 18.42 130 2.36 18.18 128 0.79
EX84 18.75 163 0 23.15 165 1.23 15.79 163 0 17.46 170 4.29 15.23 163 0
EX94 6.81 122 1.67 8.76 125 4.17 6.33 120 0 7.58 122 1.67 5.87 120 0
EX104 14.74 159 0 18.13 165 3.77 12.04 159 0 19.79 160 0.63 11.50 159 0
平均值 15.22 — 0.26 17.30 — 1.84 12.53 — 0.53 16.47 — 1.54 12.06 — 0.08
表 2  不同优化算法的实验测试结果（ ${{\overline t } / {\overline p }} > {\text{0}}{\text{.25}}$）
案例 AGA IDSSA AAADE MOGWO ASSA
$t_{\rm{op }}/ {\rm{s}}$ $C_{{\rm{max}}} $ $\delta / {\text{%}} $ $t_{\rm{op }}/ {\rm{s}}$ $C_{{\rm{max}}} $ $\delta / {\text{%}} $ $t_{\rm{op }}/ {\rm{s}}$ $C_{{\rm{max}}} $ $\delta / {\text{%}}$ $t_{\rm{op }}/ {\rm{s}}$ $C_{{\rm{max}}} $ $\delta / {\text{%}} $ $t_{\rm{op }}/ {\rm{s}}$ $C_{{\rm{max}}} $ $\delta / {\text{%}} $
EX110 1.33 126 0 1.76 126 0 0.70 126 0 0.91 126 0 0.36 126 0
EX210 1.68 148 0 1.90 148 0 0.82 148 0 1.06 148 0 0.44 148 0
EX320 1.38 145 0 1.78 148 2.07 0.84 145 0 1.57 145 0 0.46 145 0
EX420 9.50 114 0 10.31 114 0 6.85 114 0 7.79 114 0 6.40 114 0
EX530 1.32 99 0 1.12 99 0 0.53 99 0 1.09 99 0 0.19 99 0
EX630 5.82 182 0 7.22 182 0 5.12 182 0 8.34 182 0 4.65 182 0
EX740 4.99 137 0 5.24 137 0 3.12 137 0 3.85 137 0 2.65 137 0
EX840 1.49 293 0 2.29 294 0.34 0.78 293 0 1.06 293 0 0.28 293 0
EX940 8.27 175 0 11.50 175 0 6.51 175 0 12.24 175 0 6.12 175 0
EX1040 33.25 240 0 37.28 240 0 24.98 240 0 43.53 240 0 24.49 240 0
平均值 6.9 — 0.0 8.04 — 0.24 5.03 — 0.0 8.14 — 0.0 4.6 — 0.0
表 3  不同优化算法的实验测试结果（ ${{\overline t } / {\overline p }}{\text{ < 0}}{\text{.25}}$）
案例 ASSA GUROBI 案例 ASSA GUROBI
$t_{\rm{op} }/{\rm{s}}$ ${C_{{\rm{\max}} } }$ $\delta / {\text{%}} $ $t_{\rm{op} }/{\rm{s} }$ ${C_{{\rm{\max}} } }$ $\delta / {\text{%}} $ $t_{\rm{op} }/{\rm{s}}$ ${C_{{\rm{\max}} } }$ $\delta / {\text{%}} $ $t_{\rm{op} }/{\rm{s}}$ ${C_{{\rm{\max}} } }$ $\delta / {\text{%}} $
EX11 5.04 96 0 59.29 96 0 EX110 0.36 126 0 15.61 126 0
EX21 13.27 102 0 146.46 102 0 EX210 0.44 148 0 14.56 148 0
EX32 4.71 85 0 60.41 85 0 EX320 0.46 145 0 16.22 145 0
EX42 26.03 88 0 323.05 88 0 EX420 6.40 114 0 53.12 114 0
EX53 5.68 74 0 83.67 74 0 EX530 0.19 99 0 13.64 99 0
EX63 15.11 103 0 196.18 103 0 EX630 4.65 182 0 41.32 182 0
EX74 18.18 128 0 231.56 128 0 EX640 5.41 184 0 45.48 184 0
EX84 15.23 163 0 171.99 163 0 EX740 2.65 137 0 32.03 137 0
EX94 5.87 120 0 71.66 120 0 EX741 1.78 203 0 19.70 203 0
EX104 11.50 159 0 134.67 159 0 EX840 0.28 293 0 12.07 293 0
平均值 12.06 — 0.0 147.89 — 0.0 平均值 2.26 — 0.0 26.38 — 0.0
表 4  ASSA算法与GUROBI求解器的实验测试结果
案例 Cmax
S = 2 S = 3 S = 4 S = 5 S = 6
EX11 96 86 76 76 76
EX21 102 86 86 86 86
EX31 99 88 88 88 88
EX41 112 89 83 78 78
EX51 87 70 65 65 65
EX61 118 108 108 108 108
EX71 113 89 78 77 77
EX81 161 161 161 161 161
EX91 116 107 105 105 105
EX101 147 136 133 133 133
表 5  不同数量AGV的实验测试结果
图 7  各案例的AGV边际效应曲线
1 姜天华 混合灰狼优化算法求解柔性作业车间调度问题[J]. 控制与决策, 2018, 33 (3): 503- 508
JIANG Tian-hua Flexible job shop scheduling problem with hybrid grey wolf optimization algorithm[J]. Control and Decision, 2018, 33 (3): 503- 508
doi: 10.13195/j.kzyjc.2017.0124
2 SINGH N, SARNGADHARAN P V, PAL P K AGV scheduling for automated material distribution: a case study[J]. Journal of Intelligent Manufacturing, 2011, 22 (2): 219- 228
doi: 10.1007/s10845-009-0283-9
3 ZENG C, TANG J, YAN C Scheduling of no Buffer job shop cells with blocking constraints and automated guided vehicles[J]. Applied Soft Computing, 2014, 28 (8): 1033- 1046
4 ZHENG Y, XIAO Y, SEO Y A Tabu search algorithm for simultaneous machine/AGV scheduling problem[J]. International Journal of Production Research, 2014, 52 (19): 5748- 5763
doi: 10.1080/00207543.2014.910628
5 MOUSAVI M, YAP H J, MUSA S N, et al Multi-objective AGV scheduling in an FMS using a hybrid of genetic algorithm and particle swarm optimization[J]. PLoS One, 2017, 12 (3): 1- 24
6 GNANAVEL B A, JERALD J, NOORUL H A, et al Scheduling of machines and automated guided vehicles in FMS using differential evolution[J]. International Journal of Production Research, 2010, 48 (16): 4683- 4699
doi: 10.1080/00207540903049407
7 EROL R, SAHIN C, BAYKASOGLU A, et al A multi-agent based approach to dynamic scheduling of machines and automated guided vehicles in manufacturing systems[J]. Applied Soft Computing, 2012, 12 (6): 1720- 1732
doi: 10.1016/j.asoc.2012.02.001
8 徐云琴, 叶春明, 曹磊 含有AGV的柔性车间调度优化研究[J]. 计算机应用研究, 2018, 35 (11): 3271- 3275
XU Yun-qin, YE Chun-ming, CAO Lei Research on flexible job-shop scheduling problem with AGV constraints[J]. Application Research of Computers, 2018, 35 (11): 3271- 3275
doi: 10.3969/j.issn.1001-3695.2018.11.017
9 ABDELMAGUID T F, NASSEF A O, KAMAL B A, et al A hybrid GA/heuristic approach to the simultaneous scheduling of machines and automated guided vehicles[J]. International Journal of Production Research, 2004, 42 (2): 267- 281
doi: 10.1080/0020754032000123579
10 NOURI H E, DRISS O B, GHEDIRA K Simultaneous scheduling of machines and transport robots in flexible job shop environment using hybrid metaheuristics based on clustered holonic multiagent model[J]. Computers and Industrial Engineering, 2016, 24 (2): 488- 501
11 MIRJALILI S, GANDOMI A H, MIRJALILI S Z Salp swarm algorithm: a bio-inspired optimizer for engineering design problems[J]. Advances in Engineering Software, 2017, 114 (6): 163- 191
12 KHISHE M, MOHAMMADI H Passive sonar target classification using multi-layer perceptron trained by salp swarm algorithm[J]. Ocean Engineering, 2019, 181: 98- 108
doi: 10.1016/j.oceaneng.2019.04.013
13 陈涛, 王梦馨, 黄湘松 基于樽海鞘群算法的无源时差定位[J]. 电子与信息学报, 2018, 40 (7): 1591- 1597
CHEN Tao, WANG Meng-xin, HUANG Xiang-song Time difference of arrival passive location based on salp swarm algorithm[J]. Journal of Electronics and Information Technology, 2018, 40 (7): 1591- 1597
doi: 10.11999/JEIT170979
14 赵文超, 郭鹏, 王海波, 等. 改进樽海鞘群算法求解柔性作业车间调度问题 [J]. 智能系统学报, 2022, 17(2): 376-386.
ZHAO Wen-chao, GUO Peng, WANG Hai-bo, et al. Improved salp swarm algorithm for scheduling of flexible job shop [J]. CAAI Transactions on Intelligent Systems, 2022, 17(2): 376-386.
15 SAYED G I, KHORIBA G, HAGGAG M H A novel chaotic salp swarm algorithm for global optimization and feature selection[J]. Applied Intelligence, 2018, 48 (10): 3462- 3481
doi: 10.1007/s10489-018-1158-6
16 WU J, NAN R J, CHEN L Improved salp swarm algorithm based on weight factor and adaptive mutation[J]. Journal of Experimental and Theoretical Artificial Intelligence, 2019, 31 (3): 493- 515
doi: 10.1080/0952813X.2019.1572659
17 YANG B, ZHONG L E, SHU H C, et al Novel bio-inspired memetic salp swarm algorithm and application to MPPT for PV systems considering partial shading condition[J]. Journal of Cleaner Production, 2019, 215: 1203- 1222
doi: 10.1016/j.jclepro.2019.01.150
18 BILGE U, ULUSOY G A time window approach to simultaneous scheduling of machines and material handling system in FMS[J]. Operations Research, 1995, 43 (6): 1058- 1070
doi: 10.1287/opre.43.6.1058
19 LUO S, ZHANG L, FAN Y Energy-efficient scheduling for multi-objective flexible job shops with variable processing speeds by grey wolf optimization[J]. Journal of Cleaner Production, 2019, 234: 1365- 1384
doi: 10.1016/j.jclepro.2019.06.151
20 IBRAHIM A M, TAWHID M A An improved artificial algae algorithm integrated with differential evolution for job-shop scheduling problem[J]. Journal of Intelligent Manufacturing, 2023, 34: 1763- 1778
doi: 10.1007/s10845-021-01888-8
21 黄利梅 企业知识型员工激励边际递减效用的优化策略探究[J]. 技术经济与管理研究, 2018, 258 (1): 20- 23
HUANG Li-mei Study on optimization strategy of enterprise knowledge workers’ incentive marginal utility[J]. Technical Economics and Management Research, 2018, 258 (1): 20- 23
doi: 10.3969/j.issn.1004-292X.2018.01.004
[1] 赵诗奎, 方水良, 顾新建. 柔性车间调度的新型初始机制遗传算法[J]. J4, 2013, 47(6): 1022-1030.
[2] 杨玉婷, 史玉回, 夏顺仁. 基于讨论机制的头脑风暴优化算法[J]. J4, 2013, 47(10): 1705-1711.
[3] 王云, 冯毅雄, 谭建荣, 高一聪. 柔性作业车间分批调度多目标优化方法[J]. J4, 2011, 45(4): 719-726.