改进的多目标樽海鞘算法求解车间调度问题

doi:10.16180/j.cnki.issn1007-7820.2025.01.002

Abstract

Abstract:

In view of the flexible job shop scheduling problem, an improved multi-objective salp swarm algorithm combining decay factor and cross-variance operator is proposed. To facilitate the solution of the algorithm, a two-layer coding method of equal length is used and a conversion mechanism based on ascending order rules is introduced to achieve the conversion between individual position vectors and scheduling solutions. Chaotic mapping and a hybrid rule-based approach are used to generate a better initial population. A decay factor and a cross-variance operator are introduced in the position update of individuals to enhance the global search capability of the algorithm. The algorithm's solution performance is tested using standard and real-life examples of the scheduling problem and compared with other algorithms. The results show that the solution capability of the proposed improved multi-objective salp swarm algorithm is significantly improved over the original algorithm, verifying the effectiveness of the improved algorithm in solving the flexible job shop scheduling problem.

Key words: multi-objective salp swarm algorithm, bi-objective flexible job shop scheduling, two-layer coding, ascending order rules, discretized scheduling, chaotic mapping, decay factor, crossover operator, variational operator

CLC Number:

TP301.6

WEI Yu, WAN Weibing. Improved Multi-Objective Salp Swarm Algorithm for Solving Flexible Job Shop Scheduling Problem[J].Electronic Science and Technology, 2025, 38(1): 6-13.

Figures/Tables 11

Table 1.

Figure 1.

Figure 2.

Table 2.

Table 3.

Table 4.

Figure 3.

Figure 4.

Figure 5.

Figure 6.

References 24

[1]	Brucker P, Schlie R. Job-shop scheduling with multipurpose machines[J]. Computing, 1990, 45(10):369-375.
[2]	Ghasemi A, Ashoori A, Heavey C. Evolutionary learning based simulation optimization for stochastic job shop scheduling problems[J]. Applied Soft Computing, 2021, 106(2):107309-107315.
[3]	Ding H, Gu X. Improved particle swarm optimization algorithm based novel encoding and decoding schemes for flexible job shop scheduling problem[J]. Computers & Operations Research, 2020, 121(7):104951-104961.
[4]	Fan J, Shen W, Gao L, et al. A hybrid Jaya algorithm for solving flexible job shop scheduling problem considering multiple critical paths[J]. Journal of Manufacturing Systems, 2021, 60(11):298-311.
[5]	Li J Q, Liu Z M, Li C, et al. Improved artificial immune system algorithm for type-2 fuzzy flexible job shop scheduling problem[J]. IEEE Transactions on Fuzzy Systems, 2020, 29(11):3234-3248.
[6]	Zhang G, Hu Y, Sun J, et al. An improved genetic algorithm for the flexible job shop scheduling problem with multiple time constraints[J]. Swarm and Evolutionary Computation, 2020, 54(3):100664-100670.
[7]	Caldeira R H, Gnanavelbabu A, Vaidyanathan T. An effective backtracking search algorithm for multi-objective flexible job shop scheduling considering new job arrivals and energy consumption[J]. Computers & Industrial Engineering, 2020, 149(10):106863-106877.
[8]	陈强, 王宇嘉, 林炜星, 等. 改进粒子群算法求解分布式柔性车间调度问题[J]. 电子科技, 2021, 34(10):63-68.
	Chen Qiang, Wang Yujia, Lin Weixing, et al. An improved particle swarm optimization algorithm for distributed and flexible job-shop scheduling problem[J]. Electronic Science and Technology, 2021, 34(10):63-68.
[9]	邴孝锋, 陶翼飞, 董圆圆, 等. 求解改进布谷鸟算法的置换流水车间调度问题[J]. 电子科技, 2019, 32(10):60-64.
	Bing Xiaofeng, Tao Yifei, Dong Yuanyuan, et al. Solving theproblem of replacement flow shop scheduling based on improved cuckoo algorithm[J]. Electronic Science and Technology, 2019, 32(10):60-64.
[10]	Ding H, Gu X. Hybrid of human learning optimization algorithm and particle swarm optimization algorithm with scheduling strategies for the flexible job-shop scheduling problem[J]. Neurocomputing, 2020, 41(4):313-332.
[11]	Mirjalili S, Gandomi A H, Mirjalili S Z, et al. Salp swarm algorithm:A bio-inspired optimizer for engineering design problems[J]. Advances in Engineering Software, 2017, 114:163-191.
[12]	Faris H, Mafarja M M, Heidari A A, et al. An efficient binary salp swarm algorithm with crossover scheme for feature selection problems[J]. Knowledge-Based Systems, 2018, 154(8):43-67.
[13]	邢致恺, 贾鹤鸣, 宋文龙. 基于莱维飞行樽海鞘群优化算法的多阈值图像分割[J]. 自动化学报, 2021, 47(2):363-377.
	Xing Zhikai, Jia Heming, Song Wenlong. Levy flight trajectory-based salp swarm algorithm for multilevel thresholding image segmentation[J]. Acta Automatic Sinica, 2021, 47(2):363-377.
[14]	刘景森, 袁蒙蒙, 李煜. 基于改进樽海鞘群算法求解工程优化设计问题[J]. 系统仿真学报, 2021, 33(4):854-866. doi: 10.16182/j.issn1004731x.joss.19-0645
	Liu Jingsen, Yuan Mengmeng, Li Yu. Solvingeng ineering optimization design problems based on improved salp swarm algorithm[J]. Journal of System Simulation, 2021, 33(4):854-866. doi: 10.16182/j.issn1004731x.joss.19-0645
[15]	Sun Z X, Hu R, Qian B, et al. Salp swarm algorithm based on blocks on critical path for reentrant job shop scheduling problems[C]. Wuhan:Intelligent Computing Theories and Application: The Fourteenth International Conference, 2018:638-648.
[16]	Gu Y M, Chen M, Wang L. A self-learning discrete salp swarm algorithm based on deep reinforcement learning for dynamic job shop scheduling problem[J]. Applied Intelligence, 2023, 53(2):18925-18958.
[17]	Liu C, Yao Y, Zhu H. Hybrid salp swarm algorithm for solving the green scheduling problem in a double-flexible job shop[J]. Applied Sciences, 2021, 12(1):205-210.
[18]	赵文超, 郭鹏, 王海波, 等. 改进樽海鞘群算法求解柔性作业车间调度问题[J]. 智能系统学报, 2022, 17(2):376-386.
	Zhao Wenchao, Guo Peng, Wang Haibo, et al. Improved slap swarm algorithm for scheduling of flexible job shop[J]. CAAI Trasactions on Intelligent Systems, 2022, 17(2):376-386.
[19]	董君, 叶春明, 万孟然. 考虑可再生能源的可重入混合流水车间调度问题[J]. 计算机集成制造系统, 2022, 28(4):1112-1128.
	Dong Jun, Ye Chunming, Wan Mengran. Reentrant hybrid flow shop scheduling problem with renewable energy[J]. Computer Integrated Manufacturing Systems, 2022, 28(4):1112-1128.
[20]	Bingol H, Alatas B. Chaotic league championship algorithms[J]. Arabian Journal for Science and Engineering, 2016, 41(2):5123-5147.
[21]	Dos Santos Coelho L, Mariani V C. Use of chaotic sequences in a biologically inspired algorithm for engineering design optimization[J]. Expert Systems with Applications, 2008, 34(3):1905-1913.
[22]	卓然, 王未卿. 混沌映射与动态学习的自适应樽海鞘群算法[J]. 计算机工程与设计, 2021, 42(7):1963-1972.
	Zhuo Ran, Wang Weiqing. Self-adaptive salp swarm algorithm with chaotic mapping and dynamic learning[J]. Computer Engineering and Design, 2021, 42(7):1963-1972.
[23]	Mirjalili S, Saremi S, Mirjalili S M, et al. Multi-objective grey wolf optimizer:A novel algorithm for multi-criterion optimization[J]. Expert Systems with Applications, 2016, 47(10):106-119.
[24]	Mirjalili S. Dragonfly algorithm: A new meta-heuristic optimization technique for solving single-objective, discrete, and multi-objective problems[J]. Neural Computing and Applications, 2016, 27(10):1053-1073.

参数	说明
i	工件序号,i=1,2,…,n
J	工件集合,J={1,2,…,n}
M	加工设备集合,M={1,2,…,m}
O_ij	工件i的第j道工序
J_i	工件i的工序集合,J_i={1,…,n_i},n_i为其工序总数
M_ij	工件i的第j道工序的可选加工设备集合
S_i_,_j_,_k	工件i的第j道工序在设备k上的加工开始时间
F_i_,_j_,_k	工件i的第j道工序在设备k上的加工结束时间
C_i	工件i的完工时间

算例	规模	测度	GD
算例	规模	测度	MSSA	MOGWO	MODA	IMSSA₁	IMSSA₂	IMSSA
MK01	10×6	均值	6.997	7.154	10.843	6.999	7.824	9.763
MK01	10×6	标准差	0.528	0.936	0.572	0.473	0.581	0.471
MK02	10×6	均值	34.29	12.837	27.543	16.153	12.926	14.568
MK02	10×6	标准差	0.187	0.005	0.758	0.846	0.511	0.157
MK03	15×8	均值	67.891	76.824	58.479	60.265	59.315	54.372
MK03	15×8	标准差	0.456	0.428	0.414	0.576	0.419	0.014
MK04	15×8	均值	51.782	49.873	40.934	36.823	53.623	41.276
MK04	15×8	标准差	0.434	0.964	0.704	0.420	0.450	0.334
MK05	15×4	均值	33.492	48.531	32.682	28.462	23.463	20.438
MK05	15×4	标准差	0.545	0.475	0.452	0.532	0.273	0.007
MK06	10×15	均值	40.684	51.738	49.837	36.456	39.463	32.471
MK06	10×15	标准差	0.883	0.578	0.576	0.783	0.412	0.079
MK07	20×5	均值	68.435	48.671	39.981	43.165	53.165	39.752
MK07	20×5	标准差	0.655	0.451	0.257	0.465	0.541	0.434
MK08	20×10	均值	46.732	46.768	41.728	73.652	45.361	64.537
MK08	20×10	标准差	0.823	0.587	0.785	0.145	0.127	0.104
MK09	20×10	均值	48.975	47.827	34.614	43.265	33.168	54.873
MK09	20×10	标准差	0.436	0.453	0.414	0.511	0.149	0.142
MK10	20×15	均值	96.743	89.43	94.158	91.356	90.125	87.432
MK10	20×15	标准差	0.864	0.489	0.587	0.558	0.571	0.547

算例	规模	测度	GD
算例	规模	测度	MSSA	MOGWO	MODA	IMSSA₁	IMSSA₂	IMSSA
MK01	10×6	均值	5.716	4.765	4.724	4.632	3.913	3.913
MK01	10×6	标准差	0.125	0.146	0.546	0.254	0.542	0.053
MK02	10×6	均值	10.637	5.813	7.435	6.593	8.365	6.941
MK02	10×6	标准差	0.512	0.105	0.124	0.453	0.781	0.475
MK03	15×8	均值	48.972	37.684	32.461	36.482	35.253	34.552
MK03	15×8	标准差	0.854	0.462	0.247	0.472	0.547	0.452
MK04	15×8	均值	20.473	17.583	11.857	16.534	19.563	10.464
MK04	15×8	标准差	0.435	0.571	0.545	0.872	0.784	0.457
MK05	15×4	均值	42.581	39.854	32.413	39.463	40.953	34.152
MK05	15×4	标准差	0.575	0.786	0.876	0.587	0.171	0.572
MK06	10×15	均值	54.738	47.189	31.452	29.136	35.651	23.428
MK06	10×15	标准差	0.728	0.457	0.547	0.756	0.571	0.048
MK07	20×5	均值	25.961	21.473	27.543	23.863	25.943	25.687
MK07	20×5	标准差	0.544	0.704	0.256	0.571	0.425	0.147
MK08	20×10	均值	57.824	53.470	64.725	49.531	57.036	40.164
MK08	20×10	标准差	0.465	0.541	0.924	0.692	0.547	0.142
MK09	20×10	均值	34.873	43.257	31.401	35.463	33.729	31.401
MK09	20×10	标准差	0.654	0.871	0.847	0.695	0.887	0.812
MK10	20×15	均值	49.772	47.829	50.103	47.391	48.351	46.234
MK10	20×15	标准差	0.542	0.427	0.864	0.561	0.245	0.241

算例	规模	求解结果	IMSSA
MK01	10×6	完工时间	49
MK01	10×6	能耗	374
MK02	10×6	完工时间	63
MK02	10×6	能耗	357
MK03	15×8	完工时间	213
MK03	15×8	能耗	463
MK04	15×8	完工时间	61
MK04	15×8	能耗	371
MK05	15×4	完工时间	181
MK05	15×4	能耗	308
MK06	10×15	完工时间	63
MK06	10×15	能耗	349
MK07	20×5	完工时间	146
MK07	20×5	能耗	462
MK08	20×10	完工时间	536
MK08	20×10	能耗	365
MK09	20×10	完工时间	319
MK09	20×10	能耗	265
MK10	20×15	完工时间	207
MK10	20×15	能耗	189

Improved Multi-Objective Salp Swarm Algorithm for Solving Flexible Job Shop Scheduling Problem

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 11

References 24

Related Articles 15

Metrics

Comments

Recommended 0

[1]	LI Jiaying, YANG Zemin, SONG Zhedai, ZHU Jinrong. Research on Elastic Scaling Method of Kubernetes Container Cloud [J]. Electronic Science and Technology, 2025, 38(3): 32-39.
[2]	ZHANG Tangqian, HE Yu, JIANG Muning, QIN Tingxiang, ZHU Zhaoqiang, CHEN Zeshuang. Distributionally Robust Low-Carbon Economic Dispatch Considering New Energy Output [J]. Electronic Science and Technology, 2024, 37(10): 40-47.
[3]	YANG Zemin, XIA Changquan, LI Jiaying, ZHU Jinrong, HAN Yifan. Dynamic Weight Load Balancing Algorithm Based on Microservice for Smart Street Lamp Cloud Platform [J]. Electronic Science and Technology, 2024, 37(7): 89-94.
[4]	NIE Fangxin,WANG Yujia. Sparrow Search Algorithm Based on Adaptive t-Distribution and Random Walk [J]. Electronic Science and Technology, 2023, 36(7): 75-80.
[5]	SUN Xiuting,LI Yonggang,ZHANG Xing,XU Zhongyu,YU Yu. Importance Evaluation of Power Grid Nodes Based on Dynamic and Static Indexes [J]. Electronic Science and Technology, 2023, 36(4): 1-8.
[6]	WANG Ping,ZHAO Min. Improved Output Feedback Predictive Control for Perturbed LPV Systems [J]. Electronic Science and Technology, 2023, 36(1): 81-87.
[7]	LU Dongxiang. A Survey of Intelligent Transportation Path Planning Algorithms [J]. Electronic Science and Technology, 2022, 35(7): 22-27.
[8]	LIU Chenmin,WANG Yagang. Optimization of Firefly Algorithm Based on Continuous Space [J]. Electronic Science and Technology, 2022, 35(2): 40-45.
[9]	XIU Xiaobo,LI Boquan,ZHOU Feng. Optimization of Temperature Sensor Location Based on Genetic Algorithm [J]. Electronic Science and Technology, 2021, 34(9): 17-23.
[10]	XU Hangfan,LIU Cong,TANG Jiangang,PENG Dunlu. Accelerated Spectral Clustering Based on Improved Landmark Selection [J]. Electronic Science and Technology, 2021, 34(5): 47-53.
[11]	YAN Yuling,TANG Qingshan,BAI Chuang. Geomagnetic Matching Localization Algorithm Based on Affine Transformation [J]. Electronic Science and Technology, 2021, 34(4): 70-74.
[12]	FU Xinhe,YUAN Yongxu. Graphic Data Analysis Technology Based on Grey Prediction Algorithm [J]. Electronic Science and Technology, 2020, 33(7): 67-70.
[13]	XU Fengxiang. Implementation of a Collaborative Filtering Algorithm Based on Improved Similarity [J]. Electronic Science and Technology, 2020, 33(2): 54-59.
[14]	LI Cunjin,SUN Hong. The Study of Improved Self-adaptive Genetic Algorithm in Association Rules [J]. Electronic Science and Technology, 2019, 32(12): 58-63.
[15]	YU Hui,WANG Yujia,CHEN Qiang,XIAO Shanli. Multi-Objective Particle Swarm Optimization Based on Multi-population Dynamic Cooperation [J]. Electronic Science and Technology, 2019, 32(10): 28-33.

算法:IMSSA算法
1.根据Tent映射和基于规则的混合方式生成初始种群
2.while t < T_max
3. 计算每个樽海鞘个体的适应度值Fitness
4. 确定非支配解
5. 更新食物源存储库F
6. if存储库已满
7. 随机删除库中某个解,将新的非支配解加入存储库中
8. end
9. 从食物源存储库中选择一个作为食物源
10. 更新c₁
11. for每个个体
12. if(i==1)
13. 更新领导者位置
14. else
15. 更新衰减因子
16. 更新追随者位置
17. end
18. 交叉变异更新个体位置
19. end
20. 根据变量的上下界修正樽海鞘个体的位置
21.end
22.返回食物源存储库F