多约束条件下双边U型装配线平衡与协同优化

doi:10.13229/j.cnki.jdxbgxb.20211050

摘要/Abstract

摘要：

针对流水装配线效率提升和布局优化的问题，结合双边线和U型线各自的优点建立双边U型装配线平衡协同优化模型。定义了一种新型双边U型装配线P?l分区布局，简化了双边U型装配线平衡问题的平衡系统。考虑任务方位和交叉工作站内作业时间协同排序，以最小化位置数量为主要目标，最小化工作站数量为次要目标，建立多约束条件下的双边U型装配线平衡数学模型，提出基于多级优先规则的启发式算法求解模型。计算了20个经典算例，将启发式算法计算结果与改进粒子群算法、双目标整数规划方法结果进行对比，最优结果数量占比95%，验证了协同优化模型算法的有效性，为双边U型装配线平衡建模与求解提供有益参考。

关键词: 物流工程, 双边U型装配线平衡, 多级优先规则的启发式算法, 协同优化, 分区布局

Abstract:

Aiming at the efficiency improvement and layout optimization of the assembly line， combined with the advantages of the two-sided line and the U-type line， a collaborative optimization model of two-sided U-type assembly line is proposed. A new design with $P - l$ partition layout is defined to simplify the balancing system of two-sided U-type assembly line balancing problem. Considering the task orientation and time sequencing in cross-workstation， to minimize the number of positions as the primary objective and minimize the number of workstations as the secondary objective， the mathematical model of two-sided U-type assembly line balance multi- constraint is established. And a heuristic algorithm based on multi-level priority rules is proposed to solve the model. 20 classic examples are calculated. The results of the heuristic algorithm are compared with the results of the modified particle swarm optimization algorithm and the bi-objective integer programming model method. The number of optimal results accounts for 95%， which verifies that the collaborative optimization model and algorithm are reasonable， and provides a useful reference for the modeling and solution of two-sided U-type assembly line balancing.

Key words: logistics engineering, two-sided U-type assembly line balancing, heuristic algorithm of a multi-priority rule, collaborative optimization, partition layout

中图分类号:

TB491

焦玉玲,邓雪,李琳,刘文佳,张天泽,曹楠. 多约束条件下双边U型装配线平衡与协同优化[J]. 吉林大学学报(工学版), 2023, 53(7): 2053-2060.

Yu-ling JIAO,Xue DENG,Lin LI,Wen-jia LIU,Tian-ze ZHANG,Nan CAO. Balancing and collaborative optimization of two⁃sided U⁃type assembly line with multi⁃constraint[J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(7): 2053-2060.

图/表 7

图1

表1

符号说明"

$C$	装配线节拍	$U A$	未分配作业集合
$p$	位置循环变量， $P = 1,2, ?, N P$	$C A l 1$	满足优先关系的候选作业集， $l = 1,2, 3,4$
$l$	区域循环变量， $l = 1,2, 3,4$	$C A l 2$	满足操作方位约束的候选作业集
$N K$	工作站总数	$C A l 3$	满足当前区域工作站允许开始时间候选作业集
$N P$	位置总数	$C A l 4$	满足节拍约束的候选作业集
$ω p, l$	位置 $p$ 区域 $l$ 处工作站开启为1，否则为0	$A p, l$	分配至位置 $p$ 区域 $l$ 工作站的作业集合
$C r o p$	位置 $p$ 处交叉工作站指示变量（0为不交叉；1为交叉；2为未定义）	$T P, l s$	位置 $p$ 区域 $l$ 处工作站允许开始时间
$t i$	作业 $i$ 的操作时间，作业编号 $i ?$	$T p, l$	位置 $p$ 区域 $l$ 处工作站总时间
$t i s$	作业 $i$ 的开始时间	$g$	分配到装配线右边为1，装配线左边为0
$t i f$	作业 $i$ 的完成时间	$x i, p, l, g$	作业 $i$ 分配到位置 $p$ 区域 $l$ 的工作站为1，未分配为0
$H i$	作业 $i$ 的时间阶位值	$v i, j$	作业 $i$ 在作业 $j$ 之前完成为1，否则为0
$Q$	所有作业集合	$M$	一个很大的数
$B s e t$	优先关系集合， $i$ 是 $j$ 的先行作业， $(i, j) ∈ B s e t$

表1

表2

图2

表3

时间阶位值计算结果"

参数符号	作业编号
参数符号	1	2	3	4	5	6	7	8	9	10	11	12
$t i$	2	3	2	3	1	1	3	3	2	2	2	1
$H i$	10	17	8	8	14	6	5	5	5	2	3	1

表3

图3

表4

参考文献 12

1	Bartholdi J J. Balancing two-sided assembly lines: a case study[J]. International Journal of Production Research, 1993, 31(10): 2447-2461.
2	Miltenburg G J. The U-line line balancing problem[J]. Management Science, 1994, 40(10): 1378-1388.
3	Yegul M F, Agpak K, Yavuz M. A new algorithm for U-shaped two-sided assembly line balancing[J]. Transaction of The Canadian Society for Mechanical Engineering, 2010, 34(2): 225-241.
4	Agpak K, Yegul M F, Gokcen H. Two-sided U-type assembly line balancing problem[J]. International Journal of Production Research, 2012, 50(18): 5035-5047.
5	Delice Y, Aydogan E K, Ozcan U. Stochastic two-sided U-type assembly line balancing: a genetic algorithm approach[J]. International Journal of Production Research, 2016, 54(11): 3429-3451.
6	Delice Y, Aydogan E K, Ozcan U, et al. Balancing two-sided U-type assembly lines using modified particle swarm optimization algorithm[J]. 4OR-A Quarterly Journal of Operations Research, 2017,15(1):37-66.
7	Delice Y, Aydogan E K, Soylemez I, et al. An ant colony optimisation algorithm for balancing two-sided U-type assembly lines with sequence-dependent set-up times[J]. SADHANA-Academy Proceedings in Engineering Sciences, 2018, 43(12): No.133588301.
8	焦玉玲, 邢小翠, 朱春凤等. 简单直线和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.
9	Zhang Zi-kai, Tang Qiu-hua, Li Zi-xiang, et al. Modelling and optimisation of energy-efficient U-shaped robotic assembly line balancing problems[J]. International Journal of Production Research,2019(17): 5520-5537.
10	Zhang Zi-kai, Tang Qiu-hua, Zhang Li-ping. Mathematical model and grey wolf optimization for low-carbon and low-noise U-shaped robotic assembly line balancing problem[J]. Journal of Cleaner Production,2019, 215: 744-756.
11	焦玉玲, 李名鹃, 王占中, 等. 一种随机双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.
12	Jiao Yu-ling, Jin Han-qi, Xing Xiao-cui, et al. Assembly line balance research methods, literature and development review[J]. Concurrent Engineering, 2021, 29(2): 183-194.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

算例	节拍	理论值	HAMPR			PSO^［6］		BIOIP^［4］
			双边U型			双边U型		双边U型		双边直线
			NP	NK	Cro	NP	NK	NP	NK	NP	NK
P9	3	6	2	6	0	2	6	2	6	3	6
	4	5	2	5	0	2	5	2	5	3	5
	5	4	1	4	0	1	4	1	4	2	4
	6	3	1	3	0	1	3	1	3	2	3
P12	5	5	2	5	1	2	5	2	5	4	5
	6	5	2	5	1	2	5	2	5	3	5
	7	4	1	4	0	1	4	1	4	2	4
	8	4	1	4	0	1	4	1	4	2	4
	15	6	2	6	2	2	6	2	6	4	6
P16	16	6	2	6	0	2	6	2	6	3	6
	18	5	2	5	1	2	5	2	5	4	5
	19	5	2	5	1	2	5	2	5	3	5
	20	5	2	5	1	2	5	2	5	3	5
	21	4	2	5	2	2	4	2	4	4	4
P24	22	4	2	4	2	1	4	1	4	2	4
	18	8	3	8	2	2	8	2	8	4	8
	20	7	3	8	2	2	7	2	7	4	7
	25	6	2	6	2	2	6	2	6	3	6
	30	5	2	5	2	2	5	2	5	3	5
	40	4	1	4	0	1	4	1	4	2	4

[1]	刘洋,刘吉成. 基于大数据与粒子群的清洁能源协同优化调度方法[J]. 吉林大学学报(工学版), 2023, 53(5): 1443-1448.
[2]	马苗苗,刘立成,王鑫,杨茂. 风光发电与新能源汽车协同优化调度策略[J]. 吉林大学学报(工学版), 2022, 52(9): 2096-2106.
[3]	宗芳,李宇暄,张慧永,高飞. 一带一路沿线配送中心选址模型[J]. 吉林大学学报(工学版), 2022, 52(11): 2592-2599.
[4]	郭洪强, 何洪文, 卢兵. 电动汽车复合制动预测模型[J]. 吉林大学学报(工学版), 2015, 45(3): 696-702.
[5]	李邦国, 陈潇凯, 林逸. 协同优化方法的改进及应用[J]. 吉林大学学报(工学版), 2010, 40(06): 1497-1501.
[6]	戴红,，杨兆升，肖萍萍. 交通流诱导与控制协同优化模型的遗传算法求解[J]. 吉林大学学报(工学版), 2006, 36(增刊1): 157-0160.