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

doi:10.13229/j.cnki.jdxbgxb20200606

Abstract

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

CLC Number:

TB491

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.

Figures/Tables 9

Fig.1

Fig.2

Table 1

Comprehensive rank value of Jackson-11 job"

	作业
	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

Table 1

Fig.3

Table 2

Fig.4

Table 3

Balance results and indicators comparison"

序号	算例名称	$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

Table 3

Fig.5

Table 4

References 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

Comments

Recommended 0

No Suggested Reading articles found!

工作站号	作业	工作站时间	空闲时间
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]	YANG Ju-fen,JIANG Gui- yan,MA Ming-hui. Online analysis of traffic operating reliability of road network based on factor theorem [J]. 吉林大学学报(工学版), 2015, 45(1): 68-74.
[2]	LYU Feng, YANG Yin-sheng, GUO Chang-qing. New approach of criticality analysis of equipment based on improved fuzzy matter-element model [J]. 吉林大学学报(工学版), 2014, 44(01): 111-116.

Improved heuristic algorithm for U⁃shaped assembly line balancing

RICH HTML

PDF (PC)

Abstract

Cite this article

share this article

Figures/Tables 9

References 12

Related Articles 2

Metrics

Comments

Recommended 0