基于混合遗传禁忌搜索算法的混流装配线平衡优化研究

doi:10.16182/j.issn1004731x.joss.23-1045

系统仿真学报 ›› 2025, Vol. 37 ›› Issue (1): 167-182.doi: 10.16182/j.issn1004731x.joss.23-1045

• 论文 • 上一篇

基于混合遗传禁忌搜索算法的混流装配线平衡优化研究

王科¹, 官思佳²^,³, 殷希彦¹, 李西兴¹, 唐红涛⁴

^1.湖北工业大学机械工程学院，湖北武汉 430068
^2.武汉理工大学信息工程学院，湖北武汉 430070
^3.航天科工空间工程发展有限公司，北京 100854
^4.武汉理工大学机电工程学院，湖北武汉 430070

收稿日期:2023-08-23 修回日期:2023-09-25 出版日期:2025-01-20 发布日期:2025-01-23
通讯作者: 殷希彦
第一作者简介:王科(1997-)，男，硕士生，研究方向为车间调度与智能算法优化。
基金资助:
国家自然科学基金面上项目(52075401);湖北省科技重大专项(2021AAA007);湖北省重点研发计划(2021BAA203);湖北工业大学绿色工业引领计划(XJ2021005001);湖北工业大学科研启动金(BSQD2020009)

Research on Mixed-model Assembly Line Balancing Optimization Based on Hybrid Genetic Tabu Search Algorithm

Wang Ke¹, Guan Sijia²^,³, Xiyan Yin¹, Li Xixing¹, Tang Hongtao⁴

^1.College of Mechanical Engineering, Hubei University of Technology, Wuhan 430068, China
^2.School of Information Engineering, Wuhan University of Technology, Wuhan 430070, China
^3.CASIC Space Engineering Development Co. , Ltd. , Beijing 100854, China
^4.School of Mechanical and Electrical Engineering, Wuhan University of Technology, Wuhan 430070, China

Received:2023-08-23 Revised:2023-09-25 Online:2025-01-20 Published:2025-01-23
Contact: Xiyan Yin

摘要/Abstract

摘要：

针对混流液压泵装配线存在工位闲置或堵塞导致作业负荷不均衡的问题，提出了一种混合遗传禁忌搜索算法求解和计算机仿真验证的方法。以最小化混流装配线的生产节拍、不同工作站间分配的作业负荷和同一工作站内不同产品的作业负荷平滑指数为优化目标，设计了一种具有较强局部搜索能力的混合遗传禁忌搜索算法，算法通过Hamming距离的判断对可行解进行多片段交叉、片段变异操作；采用正交实验法确定了算法最佳参数组合，并在经典案例集和液压泵装配线上验证了混合遗传禁忌搜索算法的有效性和优越性；在Plant Simulation软件中考虑液压泵装配线设备情况，根据实际生产对优化方案进行仿真分析，研究结果表明了该优化方法能有效降低混流液压泵装配线的生产节拍，均衡各工作站间的工序分配和同一工作站内不同型号产品的作业负荷，实现了混流装配线的平衡再优化。

关键词: 混流装配线, 多目标优化, 混合遗传禁忌搜索, 投产排序, 仿真优化

Abstract:

Aiming at the problem of unbalanced running load caused by idle or blocked workstations in the assembly line of mixed-flow hydraulic pump, a hybrid genetic tabu search algorithm solution and computer simulation verification method are proposed. A hybrid genetic tabu search algorithm with strong local search capability is designed with the optimization objectives of minimizing the production beats of the mixed-flow assembly line, the operational loads distributed among different workstations and the operational load smoothing indices of different products within the same workstation. The algorithm incorporates multi-fragment crossover and fragmentation of feasible solutions through Hamming distance mutation operations. The optimal combination of parameters for the algorithm is determined using the orthogonal experiment method. The effectiveness and superiority of the hybrid genetic forbidden search algorithm are verified using both the classical case set and the hydraulic pump assembly line. The start-up sequencing scheme is simulated using Plant Simulation software to analyze the equipment situation of the hydraulic pump assembly line based on actual production. The research findings demonstrate that the optimization method effectively had reduced production beat and smoothing index of the mixed-flow assembly line. It also balances the workload of different products between workstations and within the same workstation, thus achieving a balanced re-optimization of the mixed-flow assembly line.

Key words: mixed-model assembly line, multi-objective optimization, hybrid genetic tabu search, production sequencing, simulation optimization

中图分类号:

TP391.9

王科,官思佳,殷希彦等 . 基于混合遗传禁忌搜索算法的混流装配线平衡优化研究[J]. 系统仿真学报, 2025, 37(1): 167-182.

Wang Ke,Guan Sijia,Xiyan Yin,et al . Research on Mixed-model Assembly Line Balancing Optimization Based on Hybrid Genetic Tabu Search Algorithm[J]. Journal of System Simulation, 2025, 37(1): 167-182.

图/表 25

图1

图2

表1

参数及含义

参数	参数含义
S	工作站总数
s	第s个工作站
$C T$	生产节拍
$Q (s)$	第s个工作站的作业元素集合
m	第m个作业元素
M	作业元素的总和
A	全部工序构成的集合
P	产品种类总数
p	第p种产品
$d p$	第p种产品的需求量
D	所有产品的总需求量
$r p$	第p种产品需求量 $d p$ 占所有产品需求量D的百分比
$t p m$	第p种产品的第 $m$ 道工序的装配时间
$t m$	联合作业优先关系图中各个作业元素的时间
$T p s$	第p种产品在第s个工作站的总装配时间
$T s$	工作站s的总装配时间
$T s u m$	所有作业的装配时间总和
$x m s$	第m项工序是否被分配到第s个工作站中
$y m n$	第m项工序和第n项工序的优先关系

表1

图3

图4

表2

目标函数的判断矩阵

目标	$φ$	SI	CI
$φ$	1	2	5
SI	1/2	1	4
CI	1/5	1/4	1

表2

图5

图6

图7

图8

表3

表4

图9

表5

不同算法求解的对比结果

案例	S	$C T t h e o r y$	IGA		VaNSAS		HGTSA
案例	S	$C T t h e o r y$	CT/s	$η$ /%	CT/s	$η$ /%	CT/s	$η$ /%	SI
Jackon	3	16	16	95.83	16	95.83	16	95.83	1.29
Jackon	4	12	12	95.83	12	95.83	12	95.83	1.22
Mitchell	5	21	21	100	21	100	21	100	0
	6	18	18	97.22	18	97.22	18	97.22	1.22
	7	15	16	93.75	16	93.75	16	93.75	1.76
	8	14	15	87.50	14	93.75	14	93.75	1.60
Heskia	5	205	208	98.46	206	99.42	205	99.90	1.12
	6	171	177	96.42	173	98.65	171	99.80	1.29
	7	147	159	92.00	149	98.18	147	99.51	1.70
	8	128	144	88.89	129	99.22	129	99.22	1.87
Killridge	4	138	140	98.57	138	100	138	100	0
	5	111	114	96.84	113	97.70	111	99.46	1.14
	6	92	96	95.83	94	97.87	93	98.92	1.63
	7	79	85	92.77	80	98.57	80	98.57	1.72
	8	69	75	92.00	69	100	70	98.57	1.41
	9	62	70	87.62	65	94.36	63	97.35	2.50
	10	56	63	87.62	58	95.17	57	96.84	2.68
Tonge	5	702	724	96.96	708	99.15	705	99.57	3.78
	6	585	600	97.50	592	98.82	589	99.32	5.51
	7	502	521	96.24	511	98.13	509	98.51	10.04
	8	439	457	96.00	451	97.28	450	97.50	8.86
	9	390	419	93.08	399	97.74	396	98.48	8.27
	10	351	382	91.88	363	96.69	361	97.23	9.42

表5

图10

图11

图12

表6

图13

图14

表7

不同算法的指标对比

实例测试	CT/s	$η$ /%	SI	CI	f	f_avg
原优化方案	499.6	83.67	192.50	78.63
IGA	488.2	85.62	70.08	87.34	31.94	34.38
VaNSAS	464.2	90.05	57.87	55.45	24.80	26.43
HGTSA	453.2	92.23	40.40	67.98	20.17	21.26

表7

图15

图16

图17

表8

参考文献 27

1	Zhang Beikun, Xu Liyun, Zhang Jian. Balancing and Sequencing Problem of Mixed-model U-shaped Robotic Assembly Line: Mathematical Model and Dragonfly Algorithm Based Approach[J]. Applied Soft Computing, 2021, 98: 106739.
2	Bock Stefan, Boysen Nils. Integrated Real-time Control of Mixed-model Assembly Lines and Their Part Feeding Processes[J]. Computers & Operations Research, 2021, 132: 105344.
3	孙宝凤, 申琇秀, 龙书玲, 等. 混流装配线的双目标投产排序决策模型[J]. 计算机集成制造系统, 2017, 23(7): 1481-1491.
	Sun Baofeng, Shen Xiuxiu, Long Shuling, et al. Bi-objective Sequencing Decision Model for Mixed-model Assembly Line[J]. Computer Integrated Manufacturing Systems, 2017, 23(7): 1481-1491.
4	Zhang Hanye. An Immune Genetic Algorithm for Simple Assembly Line Balancing Problem of Type1[J]. Assembly Automation, 2019, 39(1): 113-123.
5	李珍萍, 施莹, 吴凌云. 多约束混流线平衡与排序优化问题研究[J]. 系统仿真学报, 2023, 35(1): 27-40.
	Li Zhenping, Shi Ying, Wu Lingyun. Research on Mixed Flow Line Balancing and Scheduling Optimization with Multiple Constraints[J]. Journal of System Simulation, 2023, 35(1): 27-40.
6	Jiao Yuling, Cao Nan, Li Jin, et al. Balancing a U-shaped Assembly Line with a Heuristic Algorithm Based on a Comprehensive Rank Value[J]. Sustainability, 2022, 14(2): 775.
7	戴隆州, 吴永明, 李少波, 等. 多目标粒子群算法在混装线再平衡中的应用[J]. 计算机应用研究, 2018, 35(1): 145-149.
	Dai Longzhou, Wu Yongming, Li Shaobo, et al. Multi-objective Particle Swarm Algorithm in Mixed-model Assembly Line Rebalancing[J]. Application Research of Computers, 2018, 35(1): 145-149.
8	杜利珍, 王运发, 王震, 等. 基于果蝇算法的第二类装配线平衡问题[J]. 中国机械工程, 2018, 29(22): 2711-2715.
	Du Lizhen, Wang Yunfa, Wang Zhen, et al. Assembly Line Balancing Problem of Type Ⅱ Based on Fruit Fly Algorithm[J]. China Mechanical Engineering, 2018, 29(22): 2711-2715.
9	Liu Xuemei, Yang Xiaolang, Lei Mingliang. Optimisation of Mixed-model Assembly Line Balancing Problem Under Uncertain Demand[J]. Journal of Manufacturing Systems, 2021, 59: 214-227.
10	Zhang Honghao, Zhang Chaoyong, Peng Yong, et al. Balancing Problem of Stochastic Large-scale U-type Assembly Lines Using a Modified Evolutionary Algorithm[J]. IEEE Access, 2018, 6: 78414-78424.
11	蒙凯, 唐秋华, 张子凯, 等. 基于改进多目标灰狼算法的装配线平衡与预防维护集成优化[J]. 计算机集成制造系统, 2020, 26(12): 3302-3312.
	Meng Kai, Tang Qiuhua, Zhang Zikai, et al. Integrated Optimization of Assembly Line Balance and Preventive Maintenance Based on Improved Multi-objective Grey Wolf Algorithm[J]. Computer Integrated Manufacturing Systems, 2020, 26(12): 3302-3312.
12	Álvarez-Miranda Eduardo, Chace Sebastián, Pereira Jordi. Assembly Line Balancing with Parallel Workstations[J]. International Journal of Production Research, 2021, 59(21): 6486-6506.
13	杨武成, 程文明. 多人共站第一类混流装配线平衡问题的优化[J]. 西南交通大学学报, 2021, 56(5): 981-988.
	Yang Wucheng, Cheng Wenming. Optimization Research on Mixed-model Multi-manned Assembly Line Balancing Problem of TypeI[J]. Journal of Southwest Jiaotong University, 2021, 56(5): 981-988.
14	赵小松, 陈肯, 刘娜, 等. 考虑心理压力和体力消耗的混流装配线平衡问题[J]. 计算机集成制造系统, 2022, 28(5): 1401-1411.
	Zhao Xiaosong, Chen Ken, Liu Na, et al. Mixed-model Assembly Line Balancing Problem Considering Psychological Pressure and Physical Exhaustion[J]. Computer Integrated Manufacturing Systems, 2022, 28(5): 1401-1411.
15	黄学文, 陈绍芬, 周阗玉, 等. 求解柔性作业车间调度的遗传算法综述[J]. 计算机集成制造系统, 2022, 28(2): 536-551.
	Huang Xuewen, Chen Shaofen, Zhou Tianyu, et al. Survey on Genetic Algorithms for Solving Flexible Job-shop Scheduling Problem[J]. Computer Integrated Manufacturing Systems, 2022, 28(2): 536-551.
16	陈昭明, 徐泽宇, 赵迎. DPCA与GA-SVM融合的智能台车液压系统故障诊断[J]. 控制工程, 2020, 27(11): 1980-1986.
	Chen Zhaoming, Xu Zeyu, Zhao Ying. Hydraulic System Fault Diagnosis of Intelligent Trolley Based on Dynamic PCA and Genetic Algorithm Improved SVM[J]. Control Engineering of China, 2020, 27(11): 1980-1986.
17	冯豪博, 胡桥, 赵振轶. 基于精英族系遗传算法的AUV集群路径规划[J]. 系统工程与电子技术, 2022, 44(7): 2251-2262.
	Feng Haobo, Hu Qiao, Zhao Zhenyi. AUV Swarm Path Planning Based on Elite Family Genetic Algorithm[J]. Systems Engineering and Electronics, 2022, 44(7): 2251-2262.
18	黄珍珍, 莫碧贤, 温李红. 基于遗传算法及仿真技术的服装生产流水线平衡[J]. 纺织学报, 2020, 41(7): 154-159.
	Huang Zhenzhen, Mo Bixian, Wen Lihong. Garment Production Line Balance Based on Genetic Algorithm and Simulation[J]. Journal of Textile Research, 2020, 41(7): 154-159.
19	郑谐, 王婷, 徐云天. 基于遗传算法的飞机脉动式装配线平衡[J]. 计算机集成制造系统, 2018, 24(6): 1367-1373.
	Zheng Xie, Wang Ting, Xu Yuntian. Balance of Aircraft Pulse Assembly Line Based on Genetic Algorithm[J]. Computer Integrated Manufacturing Systems, 2018, 24(6): 1367-1373.
20	郑逸凡, 钱斌, 胡蓉, 等. CE-GA协同进化算法求解人机共同作业的U形装配线平衡问题[J]. 机械工程学报, 2020, 56(9): 199-214.
	Zheng Yifan, Qian Bin, Hu Rong, et al. CE-GA Co-evolutionary Algorithm for Solving U-shaped Assembly Line Balancing Problem with Man-robot Cooperation[J]. Journal of Mechanical Engineering, 2020, 56(9): 199-214.
21	Zhang Zikai, Tang Qiuhua, Han Dayong, et al. An Enhanced Multi-objective JAYA Algorithm for U-shaped Assembly Line Balancing Considering Preventive Maintenance Scenarios[J]. International Journal of Production Research, 2021, 59(20): 6146-6165.
22	Wang Chun, Tian Na, Ji Zhicheng, et al. Multi-objective Fuzzy Flexible Job Shop Scheduling Using Memetic Algorithm[J]. Journal of Statistical Computation and Simulation, 2017, 87(14): 2828-2846.
23	Hou Liang, Wu Yongming, Lai Rongshen, et al. Product Family Assembly Line Balancing Based on an Improved Genetic Algorithm[J]. The International Journal of Advanced Manufacturing Technology, 2014, 70(9): 1775-1786.
24	Jirasirilerd Ganokgarn, Pitakaso Rapeepan, Sethanan Kanchana, et al. Simple Assembly Line Balancing Problem Type 2 By Variable Neighborhood Strategy Adaptive Search: A Case Study Garment Industry[J]. Journal of Open Innovation: Technology, Market, and Complexity, 2020, 6(1): 21.
25	Li Xixing, Guo Xing, Tang Hongtao, et al. An Improved Cuckoo Search Algorithm for the Hybrid Flow-shop Scheduling Problem in Sand Casting Enterprises Considering Batch Processing[J]. Computers & Industrial Engineering, 2023, 176: 108921.
26	刘鑫. R公司液压泵混流装配线平衡优化研究[D]. 天津: 河北工业大学, 2021.
	Liu Xin. Research on Balance and Optimization of Hydraulic Pump Mixed-model Assembly Line for Company R[D]. Tianjin: Hebei University of Technology, 2021.
27	Meng Kai, Tang Qiuhua, Cheng Lixin, et al. Mixed-model Assembly Line Balancing Problem Considering Preventive Maintenance Scenarios: MILP Model and Cooperative Co-evolutionary Algorithm[J]. Applied Soft Computing, 2022, 127: 109341.

实验编号	参数水平				f_avg
实验编号	Pop	L	l	G	f_avg
1	30	0.4R	20	10	0.38
2	30	0.5R	40	20	0.28
3	30	0.6R	60	30	0.29
4	60	0.4R	40	30	0.25
5	60	0.5R	60	10	0.21
6	60	0.6R	20	20	0.26
7	90	0.4R	60	20	0.29
8	90	0.5R	20	30	0.22
9	90	0.6R	40	10	0.23
均值1	0.32	0.31	0.29	0.27
均值2	0.24	0.24	0.25	0.28
均值3	0.25	0.26	0.26	0.25
极差	0.08	0.07	0.04	0.03

评价指标	原优化方案	改进后
装配线平均作业率	78.26	88.51
工位平均阻塞率	10.89	2.05
装配线平衡率	83.67	92.23

[1]	李飞行, 邢立宁, 周宇. 基于多目标演化优化的SVM对抗仿真测试算法[J]. 系统仿真学报, 2024, 36(9): 2016-2031.
[2]	李二超, 张生辉. 基于DMOEA-APTC算法的无人机在线航迹规划[J]. 系统仿真学报, 2024, 36(9): 2086-2099.
[3]	张闻强, 王晓萌, 张晓晓, 张国辉. 集配一体化车辆路径规划的混合进化多目标优化[J]. 系统仿真学报, 2024, 36(8): 1914-1928.
[4]	蒋权, 魏静萱. 用于动态柔性作业车间调度的实时调度方法[J]. 系统仿真学报, 2024, 36(7): 1609-1620.
[5]	陶翼飞, 丁小鹏, 罗俊斌, 付潇, 吴佳兴, 李宜榕. 基于多目标狼群算法的机场行李导入系统仿真优化研究[J]. 系统仿真学报, 2024, 36(7): 1655-1669.
[6]	邓明君, 胡辛瑕, 李响, 徐丽萍. 基于车速引导和感应控制的干线协调优化方法[J]. 系统仿真学报, 2024, 36(6): 1309-1321.
[7]	温廷新, 关婷誉. 考虑能耗和运输的有限缓冲区混合流水车间调度[J]. 系统仿真学报, 2024, 36(6): 1344-1358.
[8]	赵嘉, 赖智臻, 吴润秀, 崔志华, 王晖. 层级引导的增强型多目标萤火虫算法[J]. 系统仿真学报, 2024, 36(5): 1152-1164.
[9]	王昱博, 胡成玉, 龚文引. 基于帕累托前沿关系求解约束多目标优化问题[J]. 系统仿真学报, 2024, 36(4): 901-914.
[10]	曾少达, 刘海林. 5G室内分布系统规划建模及优化算法[J]. 系统仿真学报, 2024, 36(3): 659-672.
[11]	安靖, 司光亚, 曾妙婷. 模型与数据混合驱动的代理模型构建方法研究[J]. 系统仿真学报, 2024, 36(3): 756-769.
[12]	王辉, 彭乐. 改进多目标蜂群算法优化洗出运动及仿真实验[J]. 系统仿真学报, 2024, 36(2): 436-448.
[13]	张彦凯, 王雪松, 金雨斌, 张东升. 基于虚拟样机的双足机器人多目标步态规划研究[J]. 系统仿真学报, 2024, 36(12): 2984-2992.
[14]	卫翔, 刘星璇, 付殿峥, 杨天吉, 杨家轩. 基于声纳搜索累积探测概率的平台路径优化方法[J]. 系统仿真学报, 2024, 36(11): 2674-2683.
[15]	徐宜刚, 陈勇, 王宸, 彭运贤. 改进NSGA-III求解高维多目标绿色柔性作业车间调度问题[J]. 系统仿真学报, 2024, 36(10): 2314-2329.

基于混合遗传禁忌搜索算法的混流装配线平衡优化研究

Research on Mixed-model Assembly Line Balancing Optimization Based on Hybrid Genetic Tabu Search Algorithm

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 25

参考文献 27

相关文章 15

编辑推荐

Metrics

本文评价

工序	综合作业时间/s	工序	综合作业时间/s	工序	综合作业时间/s	工序	综合作业时间/s
1	149.2	18	36.6	35	47.3	52	23.9
2	197.6	19	47.6	36	18.7	53	21.8
3	57.7	20	16.4	37	39.1	54	5.1
4	54.0	21	40.9	38	40.2	55	1.3
5	61.3	22	9.4	39	12.1	56	3.2
6	96.3	23	36.9	40	37.3	57	3.8
7	49.3	24	36.3	41	38.9	58	31.2
8	52.9	25	129.6	42	13.9	59	148.8
9	70.0	26	71.1	43	34.7	60	71.4
10	58.1	27	63.0	44	48.0	61	126.5
11	52.9	28	97.6	45	36.7	62	139.3
12	70.0	29	45.1	46	103.0	63	263.1
13	58.3	30	15.0	47	162.6	64	35.5
14	27.1	31	43.7	48	42.7	65	26.3
15	23.5	32	294.9	49	272.3
16	54.6	33	274.8	50	115.1
17	63.6	34	158.8	51	20.1