求解U型装配线平衡的改进启发式算法

doi:10.13229/j.cnki.jdxbgxb20200606

吉林大学学报(工学版) ›› 2021, Vol. 51 ›› Issue (6): 2061-2067.doi: 10.13229/j.cnki.jdxbgxb20200606

• 交通运输工程·土木工程 • 上一篇

求解U型装配线平衡的改进启发式算法

焦玉玲¹(),李琳¹,李津¹(),徐彬杰²,曹楠¹

^1.吉林大学交通学院，长春 130022
^2.中南大学交通运输工程学院，长沙 410018

收稿日期:2020-08-10 出版日期:2021-11-01 发布日期:2021-11-15
通讯作者: 李津 E-mail:jyling777@163.com;li_jin@jlu.edu.cn
作者简介:焦玉玲（1968-），女，副教授，博士. 研究方向：生产物流系统优化与智能算法. E-mail：jyling777@163.com
基金资助:
国家自然科学基金面上项目(61873109)

Improved heuristic algorithm for U⁃shaped assembly line balancing

Yu-ling JIAO¹(),Lin LI¹,Jin LI¹(),Bin-jie XU²,Nan CAO¹

^1.College of Transportation，Jilin University，Changchun 130022，China
^2.College of Transportation Engineering，Central South University，Changsha 410018，China

Received:2020-08-10 Online:2021-11-01 Published:2021-11-15
Contact: Jin LI E-mail:jyling777@163.com;li_jin@jlu.edu.cn

摘要/Abstract

摘要：

在假设条件下建立单U型装配线第一类平衡规划模型，根据表达产品作业优先关系的邻接矩阵特征，确定入口和出口候选作业集合，依据综合阶位值大小依次选择分配作业，求解单U型装配线平衡问题。结合小算例，详细说明了改进启发式算法的求解过程并编程计算，运用改进启发式算法程序计算了32个经典算例，将计算结果和评价指标分别与启发式算法和遗传算法进行对比，验证了该改进启发式算法有效，且计算速度快、计算结果稳定。

关键词: 工业工程, U型装配线平衡, 改进启发式算法, 邻接矩阵

Abstract:

The type-1 balance model for the single U-shaped assembly line under the assumptions is established. First, according to the characteristics of the adjacency matrix that expresses the priority relationship of the operations, the set of candidate tasks for the entry and exit are determined. Then the assignment tasks are selected in turn according to the comprehensive rank value. Finally, the single U-shaped assembly line balancing problem is solved. Combined with one example, the solution process of the improved heuristic algorithm is explained and programmed. 32 classic examples are calculated using the improved heuristic algorithm program. The calculation results and evaluation indicators are compared with the heuristic algorithm and genetic algorithm respectively. It is verified that the improved heuristic algorithm is effective, fast and stable.

Key words: industrial engineering, U-shaped assembly ling balancing, improved heuristic algorithm, adjacency matrix

中图分类号:

TB491

焦玉玲,李琳,李津,徐彬杰,曹楠. 求解U型装配线平衡的改进启发式算法[J]. 吉林大学学报(工学版), 2021, 51(6): 2061-2067.

Yu-ling JIAO,Lin LI,Jin LI,Bin-jie XU,Nan CAO. Improved heuristic algorithm for U⁃shaped assembly line balancing[J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(6): 2061-2067.

图/表 9

图1

图2

表1

Jackson-11作业综合阶位值"

	作业
	1	2	3	4	5	6	7	8	9	10	11
$N i$	10	4	3	3	3	3	2	2	1	1	0
$W N i$	6	5	4	4	4	4	3	3	2	2	1
$T i$	46	19	17	19	13	17	12	15	9	9	4
$W T i$	8	7	6	7	4	6	3	5	2	2	1
$W i$	48	35	24	28	16	24	9	15	4	4	1

表1

图3

表2

图4

表3

平衡结果及指标对比"

序号	算例名称	$C$	$m L B$	PUH^［12］				GA				IHA
序号	算例名称	$C$	$m L B$	$m$	CPU/s	$E$ /%	$V$	$m$	CPU/s	$E$ /%	$V$	$m$	CPU/s	$E$ /%	$V$
1	Mertens 7	6	5	6	2.12	80.56	0.18	6	1.08	80.56	0.12	6	1.85	80.56	0.15
2		7	5	5	2.26	82.86	0.14	5	1.06	82.86	0.11	6	1.88	69.05	0.15
3		8	4	5	2.13	72.50	0.18	5	1.10	72.50	0.11	5	1.85	72.50	0.15
4		15	2	2	2.14	96.67	0.03	2	1.18	96.67	0.03	2	1.82	96.67	0.03
5	Jaeschke 9	6	7	8	2.08	77.08	0.14	8	1.26	77.08	0.12	8	1.84	77.08	0.14
6		7	6	7	2.13	75.51	0.17	7	1.23	75.51	0.13	7	1.89	75.51	0.17
7		8	5	6	2.00	77.08	0.20	6	1.25	77.08	0.13	6	1.85	77.08	0.19
8		18	3	3	2.03	68.52	0.45	3	1.26	68.52	0.17	3	1.89	68.52	0.35
9	Jackson 11	9	6	6	2.04	85.19	0.18	6	1.49	85.19	0.08	6	1.88	85.19	0.18
10		10	5	6	1.97	76.67	0.18	5	1.43	92.00	0.04	5	1.84	92.00	0.12
11		14	4	4	2.06	82.14	0.19	4	1.41	82.14	0.04	4	1.86	82.14	0.23
12		21	3	3	2.07	73.02	0.35	3	1.42	73.02	0.03	3	1.93	73.02	0.33
13	Mitchell 21	14	8	8	2.12	93.75	0.06	8	2.29	93.75	0.04	9	1.86	83.33	0.18
14		15	7	8	2.23	87.50	0.17	8	2.42	87.50	0.04	8	1.92	87.50	0.12
15		21	5	6	2.14	83.33	0.31	5	1.40	100.00	0.00	6	1.92	83.33	0.27
16	Heskiaoff 28	138	8	8	2.18	92.75	0.10	8	2.93	92.75	0.02	8	1.95	92.75	0.07
17		205	5	6	2.19	83.25	0.36	6	2.88	83.25	0.03	6	2.02	83.25	0.25
18		216	5	5	2.13	94.81	0.10	5	2.86	94.81	0.01	5	2.03	94.81	0.06
19		324	4	4	2.12	79.01	0.36	4	2.91	79.01	0.01	4	2.20	79.01	0.34
20	Kilbridge 45	57	10	10	1.85	96.84	0.03	10	4.44	96.84	0.02	11	2.23	88.04	0.23
21		79	7	8	2.07	87.34	0.30	8	4.39	87.34	0.03	8	2.19	87.34	0.22
22		92	6	7	1.93	85.71	0.31	7	4.42	85.71	0.04	7	2.08	85.71	0.25
23		110	6	6	1.99	83.64	0.33	6	4.41	83.64	0.03	6	2.10	83.64	0.33
24	Tonge 70	364	10	10	2.00	96.43	0.09	10	6.79	96.43	0.02	10	2.11	96.43	0.06
25		410	9	9	2.02	95.12	0.11	9	6.83	95.12	0.01	9	2.16	95.12	0.11
26		468	8	8	2.06	93.75	0.14	8	6.79	93.75	0.02	8	2.14	93.75	0.15
27		527	7	7	1.96	95.15	0.11	7	6.70	95.15	0.01	7	2.15	95.15	0.10
28	Arcus 83	5048	15	16	1.98	93.73	0.11	16	8.16	93.73	0.03	16	1.93	93.73	0.08
29		6842	12	12	2.08	92.21	0.16	12	8.16	92.21	0.03	12	2.21	92.21	0.19
30		7571	10	11	2.07	90.91	0.17	11	8.05	90.91	0.03	11	1.99	90.91	0.17
31		8412	9	10	2.07	90.00	0.24	10	8.44	90.00	0.04	10	2.03	90.00	0.23
32		8898	9	9	2.11	94.54	0.09	9	8.59	94.54	0.02	9	2.05	94.54	0.06

表3

图5

表4

参考文献 12

1	Miltenburg G J, Wijngaard J. The U-line line balancing problem[J]. Management Science, 1994, 40(10):1378-1388.
2	Li Z X, Kucukkoc I, Tang Q H. New MILP model and station-oriented ant colony optimization algorithm for balancing U-type assembly lines[J]. Computers & Industrial Engineering, 2017, 112:107-121.
3	Li Z X, Kucukkoc I, Zhang Z K. Branch, bound and remember algorithm for U-shaped assembly line balancing problem[J]. Computers & Industrial Engineering, 2018, 124:24-35.
4	Babazadeh H, Alavidoost M H, Zarandi M H F, et al. An enhanced NSGA-II algorithm for fuzzy bi-objective assembly line balancing problems[J]. Computers & Industrial Engineering, 2018, 123:189-208.
5	Fathi M, Alvarez M J, Rodriuez V. A new heuristic-based bi-objective simulated annealing method for U-shaped assembly line balancing[J]. European Journal of Industrial Engineering, 2016, 10(2):145-169.
6	Aydogan E K, Delice Y, Ozcan U, et al. Balancing stochastic U-lines using particle swarm optimization[J]. Journal of Intelligent Manufacturing, 2019, 30(1):97-111.
7	郑巧仙,何国良,李明,等. 第2类U型装配线平衡问题的双阶段蚁群算法[J]. 计算机科学, 2017, 44(6):206-211, 225.
	Zheng Qiao-xian, He Guo-liang, Li Ming, et al. Two stage ant colony optimization for type-2 of U-shaped assembly line balncing problem[J]. Computer Science, 2017, 44(6):206-211, 225.
8	童艺川,吴锋. U型装配线的启发式平衡方法[J]. 南京理工大学学报, 2000, 24(5):394-397.
	Tong Yi-chuan, Wu Feng. Heuristic balancing method for U-shaped assembly line[J]. Journal of Nanjing University of Science and Technology, 2000, 24(5):394-397.
9	Küçükkoç I, Zhang D Z. Balancing of parallel U-shaped assembly lines[J]. Computers & Operations Research, 2015,64:233-244.
10	Li M, Tang Q H, Zheng Q X, et al. Rules-based heuristic approach for the U-shaped assembly line balancing problem[J]. Applied Mathematical Modeling, 2017, 48:423-439.
11	焦玉玲,邢小翠,朱春凤,等. 简单直线和U型装配线平衡中的改进阶位法[J]. 同济大学学报:自然科学版, 2019, 47(1):143-148.
	Jiao Yu-ling, Xing Xiao-cui, Zhu Chun-feng, et al. Modified ranked positional weight technique for assembly line balancing of simple line and U-shape[J]. Journal of Tongji University(Natural Science), 2019, 47(1):143-148.
12	焦玉玲,李名鹃,王占中,等. 一种随机双U型装配线优先权值平衡方法[J]. 吉林大学学报:工学版, 2020, 50(6):2087-2093.
	Jiao Yu-ling, Li Ming-juan, Wang Zhan-zhong, et al. A random double U-shaped assembly line balancing method using priority value[J]. Journal of Jilin University(Engineering and Technology Edition), 2020, 50(6):2087-2093.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

工作站号	作业	工作站时间	空闲时间
1	1，11	10	0
2	2，7，10	10	0
3	4，6	9	1
4	3，9	10	0
5	5，8	7	3

指标	不同数值占比	IHA/%	PUH/%	GA/%
E值	E>85%	56.25	56.25	62.50
E值	E≤85%	43.75	43.75	37.50
V值	V>0.25	15.63	25.00	0.00
V值	V≤0.25	84.38	75.00	100.00
CPU时间/s	CPU>2.0	43.75	78.13	59.38
CPU时间/s	CPU≤2.0	56.25	21.88	40.63

[1]	杨聚芬，姜桂艳，马明辉. 基于因子定理的路网交通运行可靠性在线分析[J]. 吉林大学学报(工学版), 2015, 45(1): 68-74.
[2]	吕锋, 杨印生, 郭长青. 基于改进模糊物元模型的设备重要度评价新方法[J]. 吉林大学学报(工学版), 2014, 44(01): 111-116.

求解U型装配线平衡的改进启发式算法

Improved heuristic algorithm for U⁃shaped assembly line balancing

RICH HTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 12

相关文章 2

Metrics

本文评价

推荐阅读 0