Please wait a minute...
浙江大学学报(工学版)
Journal of ZheJiang University (Engineering Science)  2023, Vol. 57 Issue (7): 1267-1277    DOI: 10.3785/j.issn.1008-973X.2023.07.001
    
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
Download: HTML     PDF(1024KB) HTML
Export: BibTeX | EndNote (RIS)      

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     
Received: 26 July 2022      Published: 17 July 2023
CLC:  TP 278  
Corresponding Authors: Wei-min WU     E-mail: hyniu@zju.edu.cn;wmwu@iipc.zju.edu.cn
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Hao-yi NIU
Wei-min WU
Ting-qi ZHANG
Wei SHEN
Tao ZHANG
Cite this article:

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.

URL:

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


自适应樽海鞘群算法求解考虑运输时间的柔性作业车间调度

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


关键词： 柔性作业车间调度,  运输时间,  樽海鞘群算法,  智能优化算法,  边际效应 
Fig.1 Coding scheme
Fig.2 Generation method of operation code
Fig.3 Neighborhood search operator of operation code
Fig.4 Flow chart of neighborhood search
Fig.5 Flow chart of adaptive salp swarm algorithm
案例 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
Tab.1 Comparison results of makespan with different improved strategies
Fig.6 Convergence curves of solving EX104 with different improved strategies
案例 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
Tab.2 Comparison results of different optimization algorithms ( ${{\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
Tab.3 Comparison results of different optimization algorithms ( ${{\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
Tab.4 Comparison results of ASSA algorithm and GUROBI solver
案例 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
Tab.5 Comparison results of using different number of AGV
Fig.7 AGV marginal utility curve of each case
[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] PEI Zhi, ZHANG Xue-fang, LU Hai-min, DU Rui, LU Jian-sha. Multi-stage no-wait pharmaceutical flexible job shop scheduling[J]. Journal of ZheJiang University (Engineering Science), 2018, 52(12): 2253-2261.
[2] ZHAO Shi-kui, FANG Shui-liang, GU Xin-jian. Genetic algorithm with new initialization mechanism for flexible job shop scheduling[J]. Journal of ZheJiang University (Engineering Science), 2013, 47(6): 1022-1030.
[3] FANG Shui-liang, YAO Yan-fei, ZHAO Shi-kui. Improved genetic algorithm for flexible job shop scheduling[J]. Journal of ZheJiang University (Engineering Science), 2012, 46(4): 629-635.
[4] HU Xu-Feng, HUANG Min-Xiang, WANG Ting-Ting, CHEN Xin-Lei. Optimization of shortterm complex distribution network maintenance scheduling[J]. Journal of ZheJiang University (Engineering Science), 2010, 44(3): 510-515.