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

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

中图分类号:

TP301.6

魏郁, 万卫兵. 改进的多目标樽海鞘算法求解车间调度问题[J]. 电子科技, 2025, 38(1): 6-13.

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.

图/表 11

表1

图1

图2

表2

表3

表4

图3

图4

图5

图6

参考文献 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