混流双边拆卸线平衡问题的精英差分进化算法

doi:10.13229/j.cnki.jdxbgxb.20210857

摘要/Abstract

摘要：

针对双边拆卸过程中产品单一且存在的负载不均衡和环境污染等现象，以最小化工作站数、负载均衡指标、需求指标和危害指标为优化目标，建立多目标、多产品双边拆卸线数学模型。首先，结合混流拆卸问题特征，设计了一种精英差分进化算法对所提模型进行求解，该算法设计了一种新的编码-解码方式贴合实际拆卸过程；其次，结合精英策略改进自身随机过程与进化过程；最后，采用Pareto比较和NSGA-II机制筛选非劣解。通过与双边拆卸现有实例对比，验证了算法的可行性和良好的求解性能。并将所建模型与本文算法运用于混流电视机拆卸案例，求解得到多组较优方案供决策者选择。

关键词: 计算机应用, 混流, 双边拆卸线, 多目标求解, 差分进化

Abstract:

Aiming at the phenomenon of single product， existing load imbalance and environmental pollution during the two-side disassembly process， a mathematical model of multi-objective mixed-model two-sided disassembly line was established to minimize the number of workstations， load balancing index， demand indexl， and hazard index. An elite differential evolution algorithm was designed to solve the proposed model. And the algorithm designed a new encoding and decoding method to fit the actual disassembly process. The elite strategy was combined to improve the algorithm's random process and evolution process. Pareto comparison and NSGA-II mechanism were used to screen non-inferior solutions. The feasibility and well performance of the algorithm are verified by comparing it with the actual two-side disassembly examples. Finally， the model and the algorithm were applied to a mixed-model TV disassembly case， then giving several better schemes for decision-makers to choose.

Key words: computer applications, mixed-model, two-side disassembly line, multi-objective solution, differential evolution algorithm

中图分类号:

TP29

张则强,梁巍,谢梦柯,郑红斌. 混流双边拆卸线平衡问题的精英差分进化算法[J]. 吉林大学学报(工学版), 2023, 53(5): 1297-1304.

Ze-qiang ZHANG,Wei LIANG,Meng-ke XIE,Hong-bin ZHENG. Elite differential evolution algorithm for mixed⁃model two⁃side disassembly line balancing problem[J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(5): 1297-1304.

图/表 8

图1

图2

表1

表2

表3

图3

表4

图4

参考文献 27

1	Zhang Y, Zhang Z Q, Guan C, et al. Improved whale optimisation algorithm for two-sided disassembly line balancing problems considering part characteristic indexes[J]. International Journal of Production Research, 2022, 60(8): 2553-2571.
2	Gungor A, Gupta S M. A solution approach to the disassembly line balancing problem in the presence of task failures[J]. International Journal of Production Research, 2001, 39(7): 1427-1467.
3	Özceylan E, Kalayci C B, Güngör A, et al. Disassembly line balancing problem: a review of the state of the art and future directions[J]. International Journal of Production Research, 2018(1): 1-23.
4	张则强, 蔡宁, 曾艳清, 等.面向再制造的拆卸线平衡问题建模理论及求解方法综述[J].中国机械工程, 2018, 29(21): 2636-2645.
	Zhang Ze-qiang, Cai Ning, Zeng Yan-qing, et al. Review of modeling theory and solution method for disassembly line balancing problems for remanufacturing[J]. China Mechanical Engineering, 2018, 29(21): 2636-2645.
5	Delice Y, Aydogan E K, Ozcan U, et al. A modified particle swarm optimization algorithm to mixed-model two-sided assembly line balancing[J]. Journal of Intelligent Manufacturing, 2017, 28(1): 23-36.
6	He J K, Chu F, Zheng F F, et al. A green-oriented bi-objective disassembly line balancing problem with stochastic task processing times[J]. Annals of Operations Research, 2021, 296(1/2): 71-93.
7	Liu J Y, Zhou Z D, Pham D T, et al. Collaborative optimization of robotic disassembly sequence planning and robotic disassembly line balancing problem using improved discrete Bees algorithm in remanufacturing[J]. Robotics and Computer-Integrated Manufacturing, 2020, 61: 1-18.
8	周炳海, 彭涛. 混流装配线准时化物料配送调度优化[J].吉林大学学报: 工学版, 2017, 47(4): 1253-1261.
	Zhou Bing-hai, Peng Tao. Optimal schedule of just-in-time part distribution for mixed-model assembly lines[J]. Journal of Jilin University(Engineering and Technology Edition), 2017, 47(4): 1253-1261.
9	Ali M, Siarry P, Pant M. An efficient differential evolution based algorithm for solving multi-objective optimization problems[J]. European Journal of Operational Research, 2012, 217(2): 404-416.
10	董宁, 王宇平.求解约束优化问题的引导多目标差分进化算法[J].吉林大学学报: 工学版, 2015, 45(2): 569-575.
	Dong Ning, Wang Yu-ping. Guiding multi-objective differential evolution algorithm for constrained optimization[J]. Journal of Jilin University(Engineering and Technology Edition), 2015, 45(2): 569-575.
11	刘洲洲, 张倩昀, 马新华, 等.基于优化离散差分进化算法的压缩感知信号重构[J].吉林大学学报: 工学版, 2021, 51(6): 2246-2252.
	Liu Zhou-zhou, Zhang Qian-yun, Ma Xin-hua,et al. Compressed sensing signal reconstruction based on optimized discret differential evolution algorithm[J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(6): 2246-2252.
12	毕超超, 范勤勤, 王维莉.基于策略自适应的多目标差分进化算法及其应用[J].计算机应用研究, 2020, 37(7): 2016-2021.
	Bi Chao-chao, Fan Qing-qing, Wang Wei-li. Multi-objective differential evolution algorithm based on self-adaptive strategy and its application[J]. ApplicationResearch of Computers, 2020, 37(7): 2016-2021.
13	曾宇容, 张金隆, 彭璐, 等.基于模拟退火的混合差分进化算法及其在联合补货⁃配送集成优化中的应用[J]. 计算机应用研究, 2018, 35(4): 1037-1041.
	Zeng Yu-rong, Zhang Jing-long, Peng Lu, et al. Hybrid differential evolution supported by simulated annealing and its application in integrated joint replenishment-delivery problems[J]. Application Research of Computers, 2018, 35(4): 1037-1041.
14	周炳海, 吴琼.考虑工具和空间约束的机器人装配线平衡优化[J].吉林大学学报: 工学版, 2019, 49(6): 2069-2075.
	Zhou Bing-hai, Wu Qiong. Balancing and optimization of robotic assemble lines with tool and space constraint[J]. Journal of Jilin University(Engineering and Technology Edition), 2019, 49(6): 2069-2075.
15	Zhu L X, Zhang Z Q, Wang Y, et al. On the end-of-life state oriented multi-objective disassembly line balancing problem[J]. Journal of Intelligent Manufacturing, 2020, 31(6): 1403-1428.
16	Bader J, Zitzler E. Hype: an algorithm for fast hypervolume-based many-objective optimization[J]. Evolutionary Computation, 2011, 19(1): 45-76.
17	Yin T, Zhang Z Q, Jiang J. A Pareto-discrete hummingbird algorithm for partial sequence-dependent disassembly line balancing problem considering tool requirements[J]. Journal of Manufacturing Systems, 2021, 60: 406-428.
18	Macaskill J L. Application series, Part 1 Production-line balances for mixed-model lines[J]. Management Science, 1972, 19(4): 423-434.
19	Boysen N, Fliedner M, Scholl A. Assembly line balancing: joint precedence graphs under high product variety[J]. IIE Transactions, 2009, 41(3): 183-193.
20	Tuncel E, Zeid A, Kamarthi S. Solving large scale disassembly line balancing problem with uncertainty using reinforcement learning[J]. Journal of Intelligent Manufacturing, 2014, 25(4): 647-659.
21	Kalayci C B, Polat O, Gupta S M. A variable neighbourhood search algorithm for disassembly lines[J]. Journal of Manufacturing Technology Management, 2015, 26(2): 182-194.
22	Kalayci C B, Gupta S M. Simulated annealing algorithm for solving sequence-dependent disassembly line balancing problem[J]. IFAC Proceedings Volumes, 2013, 46(9): 93-98.
23	汪开普, 张则强, 朱立夏, 等.多目标拆卸线平衡问题的Pareto遗传模拟退火算法[J].计算机集成制造系统, 2017, 23(6): 1277-1285.
	Wang Kai-pu, Zhang Ze-qiang, Zhu Li-xia, et al. Pareto genetic simulated annealing algorithm for multi-objective disassembly line balancing problem[J]. Computer Integrated Manufacturing Systems, 2017, 23(6): 1277-1285.
24	汪开普, 张则强, 毛丽丽, 等.多目标拆卸线平衡问题的Pareto人工鱼群算法[J].中国机械工程, 2017, 28(2): 183-190.
	Wang Kai-pu, Zhang Ze-qiang, Mao Li-li, et al. Pareto artificial fish swarm algorithm for multiobjective disassembly line balance problem[J]. China Mechanical Engineering, 2017, 28(2): 183-190.
25	Zhang Z Q, Wang K P, Zhu L X, et al. A pareto improved artificial fish swarm algorithm for solving a multi-objective fuzzy disassembly line balancing problem[J]. Expert Systems with Applications, 2017, 86: 165-176.
26	邹宾森, 张则强, 李六柯, 等.双边拆卸线平衡问题建模与优化[J].中国机械工程, 2018, 29(9): 1090-1097+1107.
	Zhou Bing-seng, Zhang Ze-qiang, Li Liu-ke, et al. Modeling and optimization of bilateral disassembly line balance problem[J]. China Mechanical Engineering, 2018, 29(9): 1090-1097+1107.
27	张三强.整车混流装配线平衡和优化排序的研究与应用[D].武汉: 华中科技大学机械科学与工程学院, 2015.
	Zhang San-qiang. Research and application of vehicle mixed-model assembly line balancing and optimize sequencing[D]. Wuhan: School of Mechanical Science and Engineering, Huazhong University of Technology, 2015.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

算法	S₁	S₂	S₃	S₄	算法	S₁	S₂	S₃	S₄
VNS	9	9	825	76	GASA	9	9	825	76
GA	9	9	868	82		9	11	821	75
SA	9	9	853	81		9	15	815	75
EDE	9	9	823	77		10	141	814	73
	9	9	825	76		10	195	818	74
	9	11	821	75	AFSA	9	9	825	76
	9	15	815	75		9	9	823	77
	10	111	900	73		9	11	821	75
	10	155	879	72		9	15	817	74
	11	395	870	70		10	195	813	73
	11	395	868	71		10	141	812	74
	12	523	802	73		11	295	809	73
	12	559	804	71		11	287	817	72

BA				EDE
F₁	F₂	F₃	F₄	F₁	F₂	F₃	F₄
6	5 907	461	42	5	813	530	35
6	6 359	445	36	5	1 047	520	35
6	8 757	517	25	6	7 327	502	34
7	19 657	481	26	7	18 873	479	24
7	16 859	454	34	8	33 695	469	21
8	28 533	485	24	8	34 959	400	32
9	51 679	435	30	9	47 657	459	23
9	48 711	433	34	9	46 321	423	25

方案	GA				SA				EDE
方案	F₁	F₂	F₃	F₄	F₁	F₂	F₃	F₄	F₁	F₂	F₃	F₄
1	6	3 368	388	48	6	3 408	393	48	6	4 186	368	42
2	6	5 093	323	71	6	3 364	387	57	6	3 362	357	54
3	6	5 017	336	63	6	4 158	369	42	6	3 398	321	60
4	7	7 474	376	42	6	3 504	321	64	6	3 364	379	48
5	7	10 905	309	63	6	3 452	322	60	6	4 178	320	54
6	7	6 473	324	57	7	18 197	331	48	7	7 658	360	42
7	7	12 979	313	52	7	17 979	345	45	7	10 188	308	51
8	8	23 864	323	45	8	10 976	309	51	7	12 840	305	55
9	8	10 383	353	48	8	14 629	306	59	8	19 019	330	48
10	9	17 279	349	49	8	8 239	317	51	8	5 346	331	48

方案	f₁	f₂	f₃	f₄
1	6	5 175.11	3 436	180
2	6	6 667.83	3 671	132
3	6	7 582.83	3 561	144
4	7	8 844.83	3 297	102
5	7	18 606.23	3 262	108
6	7	18 217.35	3 259	120
7	8	23 703.01	3 037	174
8	8	24 058.83	3 074	162

[1]	姜宇,潘家铮,陈何淮,符凌智,齐红. 基于分割方法的繁体中文报纸文本检测[J]. 吉林大学学报(工学版), 2023, 53(4): 1146-1154.
[2]	于鹏,朴燕. 基于多尺度特征的行人重识别属性提取新方法[J]. 吉林大学学报(工学版), 2023, 53(4): 1155-1162.
[3]	潘弘洋,刘昭,杨波,孙庚,刘衍珩. 基于新一代通信技术的无人机系统群体智能方法综述[J]. 吉林大学学报(工学版), 2023, 53(3): 629-642.
[4]	何颖,樊俊松,王巍,孙庚,刘衍珩. 无人机空地安全通信与航迹规划的多目标联合优化方法[J]. 吉林大学学报(工学版), 2023, 53(3): 913-922.
[5]	吴振宇,刘小飞,王义普. 基于DKRRT^*-APF算法的无人系统轨迹规划[J]. 吉林大学学报(工学版), 2023, 53(3): 781-791.
[6]	陶博,颜伏伍,尹智帅,武冬梅. 基于高精度地图增强的三维目标检测算法[J]. 吉林大学学报(工学版), 2023, 53(3): 802-809.
[7]	薛珊,张亚亮,吕琼莹,曹国华. 复杂背景下的反无人机系统目标检测算法[J]. 吉林大学学报(工学版), 2023, 53(3): 891-901.
[8]	祁贤雨,王巍,王琳,赵玉飞,董彦鹏. 基于物体语义栅格地图的语义拓扑地图构建方法[J]. 吉林大学学报(工学版), 2023, 53(2): 569-575.
[9]	时小虎,吴佳琦,吴春国,程石,翁小辉,常志勇. 基于残差网络的弯道增强车道线检测方法[J]. 吉林大学学报(工学版), 2023, 53(2): 584-592.
[10]	郭鹏,赵文超,雷坤. 基于改进Jaya算法的双资源约束柔性作业车间调度[J]. 吉林大学学报(工学版), 2023, 53(2): 480-487.
[11]	刘近贞,高国辉,熊慧. 用于脑组织分割的多尺度注意网络[J]. 吉林大学学报(工学版), 2023, 53(2): 576-583.
[12]	赵宏伟,张健荣,朱隽平,李海. 基于对比自监督学习的图像分类框架[J]. 吉林大学学报(工学版), 2022, 52(8): 1850-1856.
[13]	秦贵和,黄俊锋,孙铭会. 基于双手键盘的虚拟现实文本输入[J]. 吉林大学学报(工学版), 2022, 52(8): 1881-1888.
[14]	胡丹,孟新. 基于时变网格的对地观测卫星搜索海上船舶方法[J]. 吉林大学学报(工学版), 2022, 52(8): 1896-1903.
[15]	曲福恒,丁天雨,陆洋,杨勇,胡雅婷. 基于邻域相似性的图像码字快速搜索算法[J]. 吉林大学学报(工学版), 2022, 52(8): 1865-1871.