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
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.
Fig.3Neighborhood search operator of operation code
Fig.4Flow chart of neighborhood search
Fig.5Flow 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.1Comparison results of makespan with different improved strategies
Fig.6Convergence 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.2Comparison 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.3Comparison 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.4Comparison 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.5Comparison results of using different number of AGV
Fig.7AGV 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