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

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

Abstract

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

CLC Number:

TP391.9

Wang Ke, Guan Sijia, Xiyan Yin, Li Xixing, Tang Hongtao. 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.

Figures/Tables 25

Fig. 1

Fig. 2

Table 1

Parameters and meaning

参数	参数含义
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项工序的优先关系

Table 1

Fig. 3

Fig. 4

Table 2

Judgment matrix of objective function

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

Table 2

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Table 3

Table 4

Fig. 9

Table 5

Comparison results of different algorithms

案例	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

Table 5

Fig. 10

Fig. 11

Fig. 12

Table 6

Fig. 13

Fig. 14

Table 7

Comparison of indicators of different algorithms

实例测试	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

Table 7

Fig. 15

Fig. 16

Fig. 17

Table 8

References 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]	Li Feixing, Xing Lining, Zhou Yu. Adversarial Simulation Testing Algorithm for SVM Based on Multi-objective Evolutionary Optimization [J]. Journal of System Simulation, 2024, 36(9): 2016-2031.
[2]	Li Erchao, Zhang Shenghui. UAV Online Track Planning Based on DMOEA-APTC Algorithm [J]. Journal of System Simulation, 2024, 36(9): 2086-2099.
[3]	Zhang Wenqiang, Wang Xiaomeng, Zhang Xiaoxiao, Zhang Guohui. Hybrid Evolutionary Multi-objective Optimization Algorithm for Vehicle Routing Problem with Simultaneous Delivery and Pickup [J]. Journal of System Simulation, 2024, 36(8): 1914-1928.
[4]	Jiang Quan, Wei Jingxuan. Real-time Scheduling Method for Dynamic Flexible Job Shop Scheduling [J]. Journal of System Simulation, 2024, 36(7): 1609-1620.
[5]	Tao Yifei, Ding Xiaopeng, Luo Junbin, Fu Xiao, Wu Jiaxing, Li Yirong. Simulation Optimization of Airport Baggage Import System Based on Multi-objective Wolf Pack Algorithm [J]. Journal of System Simulation, 2024, 36(7): 1655-1669.
[6]	Deng Mingjun, Hu Xinxia, Li Xiang, Xu Liping. Arterial Coordination Optimization Method Based on Vehicle Speed Guidance and Inductive Control [J]. Journal of System Simulation, 2024, 36(6): 1309-1321.
[7]	Wen Tingxin, Guan Tingyu. Hybrid Flow Shop Scheduling with Limited Buffers Considering Energy Consumption and Transportation [J]. Journal of System Simulation, 2024, 36(6): 1344-1358.
[8]	Zhao Jia, Lai Zhizhen, Wu Runxiu, Cui Zhihua, Wang Hui. Hierarchical Guided Enhanced Multi-objective Firefly Algorithm [J]. Journal of System Simulation, 2024, 36(5): 1152-1164.
[9]	Wang Yubo, Hu Chengyu, Gong Wenyin. Handling Constrained Multi-objective Optimization Problems Based on Relationship Between Pareto Fronts [J]. Journal of System Simulation, 2024, 36(4): 901-914.
[10]	Zeng Shaoda, Liu Hailin. Planning Modeling and Optimization Algorithm for 5G Indoor Distribution System [J]. Journal of System Simulation, 2024, 36(3): 659-672.
[11]	An Jing, Si Guangya, Zeng Miaoting. Construction of Surrogate Model Driven by Model and Data [J]. Journal of System Simulation, 2024, 36(3): 756-769.
[12]	Wang Hui, Peng Le. Improved Multi-objective Swarm Algorithm to Optimize Wash-out Motion and its Simulation Experiment [J]. Journal of System Simulation, 2024, 36(2): 436-448.
[13]	Zhang Yankai, Wang Xuesong, Jin Yubin, Zhang Dongsheng. Research on Multi-objective Gait Planning of Biped Robot Based on Virtual Prototype [J]. Journal of System Simulation, 2024, 36(12): 2984-2992.
[14]	Wei Xiang, Liu Xingxuan, Fu Dianzheng, Yang Tianji, Yang Jiaxuan. Platform Path Optimization Method Based on Cumulative Detection Probability of Sonar Search [J]. Journal of System Simulation, 2024, 36(11): 2674-2683.
[15]	Xu Yigang, Chen Yong, Wang Chen, Peng Yunxian. Improving NSGA-III Algorithm for Solving High-dimensional Many-objective Green Flexible Job Shop Scheduling Problem [J]. Journal of System Simulation, 2024, 36(10): 2314-2329.