多约束混流线平衡与排序优化问题研究

doi:10.16182/j.issn1004731x.joss.21-0679

摘要/Abstract

摘要：

针对G企业混流装配线设计不合理导致工位间负载不均衡及产品堆积现象，考虑工序与工位间匹配关系，节拍时间、工序优先关系等多约束，以减少工位数量、均衡工位间负载、减少产品等待时间为目标，建立混流装配线设计与产品排序问题的多目标混合整数规划模型，分别设计了分层算法和混合启发式算法；利用小规模算例验证了分层次算法的精确性，利用大规模算例验证了混合启发式算法高效性。基于本文算法对G企业装配线进行优化后，其工位间负载极差由15.6 min减少到0.1 min，优化后投产顺序对应的节拍时间降低了6 min。

关键词: 混流装配线, 平衡, 产品排序, 多目标混合整数规划, 分层次算法, 混合启发式算法

Abstract:

Aiming at the phenomena of unbalanced load between stations and product accumulation caused by unreasonable design of mixed flow line in G enterprise, based on the matching relationship between processes and stations, cycle time, process priority and other constraint, with the objectives of reducing the number of stations, balancing the workload between stations, and reducing the products waiting time, a multi-objective mixed integer programming model for mixed flow line balance and product scheduling problem is established. A hierarchical algorithm and a hybrid heuristic algorithm are designed respectively; the accuracy of the hierarchical algorithm is verified by small-scale examples, and the efficiency of the hybrid heuristic algorithm is verified by large-scale examples. After the optimization based on the algorithms of this paper, the difference of workload between stations of G enterprise is reduced from 15.6 minutes to 0.1 minutes, and the cycle time is reduced by 6 minutes.

Key words: mixed model assembly line, balance, product ranking, multi-objective mixed integer programming, hierarchical algorithm, hybrid heuristic algorithm

中图分类号:

TP399

李珍萍, 施莹, 吴凌云. 多约束混流线平衡与排序优化问题研究[J]. 系统仿真学报, 2023, 35(1): 27-40.

Zhenping Li, Ying Shi, Lingyun Wu. Research on Mixed Flow Line Balancing and Scheduling Optimization with Multiple Constraints[J]. Journal of System Simulation, 2023, 35(1): 27-40.

图/表 13

图1

图2

图3

表1

表2

表3

表4

表5

图4

表6

2种算法计算结果对比分析

实例参数	c/min	分层次求解法			启发式求解			( $f 2 - f 1$ )/min
$I / S / (p 1, p 2, ⋯, p M)$	c/min	$f 1$ /min	$T 1$ /min	$C P U 1$ /s	$f 2$ /min	$T 2$ /min	$C P U 2$ /s	( $f 2 - f 1$ )/min
44-4-1-2-2	64	3.7	419.1	6.2	8.6	433.2	2 s	4.9
44-4-3-4-3	64	5.2	706.9	18	7.1	693.4	2.1 s	1.9
44-5-1-2-2	44.8	0.2	390.2	47	1.3	397.2	2.7 s	1.1
44-5-3-4-3	44.8	0.4	597.8	32	1.6	603.7	2.9 s	1.2
44-6-1-2-2	37.3	0.2	380.6	102	0.2	374.6	2.6 s	0
44-6-3-4-3	37.3	0.3	536.3	576	1.4	556	3.2 s	1.1
72-4-1-2-2	91	4.9	732	8.6	6	748.5	<10 s	1.1
72-4-3-4-3	93	31.2	1 190.6	29	38.2	1 207.1	<10 s	7
72-5-1-2-2	73	0.1	658.5	345	0.1	634.2	<10 s	0
72-5-3-4-3	73	0.1	1 027.4	60	2.1	1 032.2	<10 s	2
72-6-1-2-2	61	0.1	630	242	0.1	592.9	<10 s	1.2
72-6-3-4-3	61	0.2	935.2	1 410	1.3	897.4	<10 s	1.1
100-4-1-2-2	161	239	1 139.9	52	312	1 142.5	<10 s	73
100-4-3-4-3	161	471	1 921.9	54	563	1 957.9	<10 s	92
100-5-1-2-2	101	0.1	919.8	107.8	1.3	936.9	<10 s	1.2
100-5-3-4-3	101	0.1	1 405.4	125	0.8	1 456.4	<10 s	0.7
100-6-1-2-2	85	0.1	860.4	72.8	0.1	866.5	<10 s	1.1
100-6-3-4-3	85	0.1	1 261.8	3 000	1.4	1 276.9	<10 s	1.3

表6

图5

图6

表7

参考文献 27

1	李金霖. 需求不确定环境下可调整产能的混流线平衡研究[D]. 西安: 西安交通大学, 2017.
	Li Jinlin. Study on Mixed Flow Line Equilibrium with Adjustable Capacity under Uncertain Demand[D]. Xi'an: Xi'an Jiaotong University, 2017.
2	Zhang B, Xu L, Zhang J. Balancing and Sequencing Problem of Mixed-model U-shaped Robotic Assembly Line: Mathematical Model and Dragonfly Algorithm Based Approach[J]. Applied Soft Computing(S1568-4946), 2021, 98: 106739.
3	宋华明. 装配流水线平衡和投产排序模型算法与仿真[M]. 北京: 电子工业出版社, 2016.
	Song Huaming. Algorithm and Simulation of Assembly Line Balancing and Production Scheduling Model[M].Beijing: Electronic Industry Press, 2016.
4	Hou L, Wu Y, Lai R, et al. Product Family Assembly Line Balancing Based on an Improved Genetic Algorithm[J]. The International Journal of Advanced Manufacturing Technology (S0268-3768), 2014, 70(9-12): 1775-1786.
5	杨武成, 程文明. 多人共站第一类混流配线平衡问题的优化研究[J]. 西南交通大学学报, 2021, 56(5): 981-988.
	Yang Wucheng, Cheng Wenming. Study on the Optimization of the First Type Mixed Flow LineEquilibrium Problem with Multi Person CO Station[J]. Journal of Southwest Jiaotong University, 2021, 56(5): 981-988.
6	徐责, 宋小欣, 付建林. 考虑人员能力差异的多人共站混流线平衡研究[J]. 现代制造程, 2020(11): 33-40.
	Xu Ze, Song Xiaoxin, Fu Jianlin. Study on the Balance of Multi Person CO Station Mixed Flow Line Considering the Difference of Personnel Ability[J]. Modern Manufacturing Process, 2020(11): 33-40.
7	邓超, 胡瑞飞, 蒋捷峰, 等. 考虑工人分配的多目标装配线平衡优化[J]. 组合机床与自动化加工技术, 2021(6): 116-121, 126.
	Deng Chao, Hu Ruifei, Jiang Jiefeng. Multi Objective Assembly Line Balancing Optimization Considering Worker Allocation[J]. Modular Machine Tool and Automatic Processing Technology, 2021(6): 116-121, 126.
8	彭运芳, 梁玉珍, 夏蓓鑫. 基于改进型遗传算法的混流U型装配线第二类平衡问题[J]. 上海大学学报(自然科学版), 2021, 27(2): 360-368.
	Peng Yunfang, Liang Yuzhen, Xia Beixin. The Second Type Balance Problem of Mixed Flow U-type Assembly Line Based on Improved Genetic Algorithm[J]. Journal of Shanghai University (Natural Science Edition), 2021, 27(2): 360-368.
9	段移庭, 苏平, 郑晨鸣. 随机型双边混流线平衡问题的两阶段求解方法研究[J]. 工业工程, 2016, 19(2): 134-142.
	Duan Yiting, Su Ping, Zheng Chenming. Study on Two-stage Solution of Stochastic Two-sided Mixed Flow Line Equilibrium Problem[J]. Industrial Engineering, 2016, 19(2): 134-142.
10	吴意, 唐秋华, 张利平, 等. 多约束双边装配线平衡的改进万有引力搜索算法[J]. 现代制造工程, 2016(11): 6-13, 55.
	Wu Yi, Tang Qiuhua, Zhang Liping, et al. Improved Gravity Search Algorithm for Multi Constraint Bilateral Assembly Line Balance[J]. Modern Manufacturing Engineering, 2016 (11): 6-13, 55.
11	刘晋飞, 李杰林, 马学明, 等. 基于平均停歇时间的多品种混流生产线智能排序策略[J]. 同济大学学报(自然科学版), 2020, 48(11): 1676-1686.
	Liu Jinfei, Li Jielin, Ma Xuemin, et al. Intelligent Scheduling Strategy for Multi Variety Mixed Model Production Line Based on Average Stopping Time[J]. Journal of Tongji University (Natural Science Edition), 2020, 48(11): 1676-1686.
12	刘琼, 范正伟, 张超勇, 等. 基于多目标猫群算法的混流装配线排序问题[J]. 计算机集成制造系统, 2014, 20(2): 333-342.
	Liu Qiong, Fan Zhengwei, Zhang Chaoyong, et al. Mixed Model Assembly Line Scheduling Problem Based on Multi-objective Cat Swarm Algorithm[J]. Computer Integrated Manufacturing System, 2014, 20(2): 333-342.
13	翁耀炜, 鲁建厦, 邓伟. 基于禁忌粒子群算法的混流装配线排序研究[J]. 机电工程, 2013, 30(4): 430-434.
	Weng Yaowei, Lu Jianxia, Deng Wei. Research on Mixed Model Assembly Line Scheduling Based on Tabu Particle Swarm Optimization[J]. Mechanical and Electrical Engineering, 2013, 30(4): 430-434.
14	楚克明, 吴立云. 自适应遗传算法在混流装配线排序中的应用[J]. 现代制造工程, 2019(9): 37-40.
	Chu Keming, Wu Liyun. Application of Adaptive Genetic Algorithm in Mixed Model Assembly Line Scheduling[J]. Modern Manufacturing Engineering, 2019(9): 37-40.
15	赵小松, 赵舒萌, 刘娜, 等. 考虑疲劳和恢复的混流线平衡问题[J]. 系统工程学报, 2020, 35(2): 265-275.
	Zhao Xiaosong, Zhao Shumeng, Liu Na, et al. Mixed Flow Line Equilibrium Considering Fatigue and Recovery[J]. Journal of Systems Engineering, 2020, 35(2): 265-275.
16	姜东, 唐秋华, 李梓响, 等. 多目标模拟退火算法求解混装线平衡与排序[J]. 机械设计与制造, 2018(9): 189-192.
	Jiang Dong, Tang Qiuhua, Li Zixiang, et al. Multi Objective Simulated Annealing Algorithm for Balancing and Sequencing of Mixed Loading Lines[J]. Mechanical Design and Manufacturing, 2018(9): 189-192.
17	Manavizadeh N, Rabbani M, Moshtaghi D, et al. Mixed-model Assembly Line Balancing in the Make-to-order and Stochastic Environment using Multi-objective Evolutionary Algorithms[J]. Expert Systems with Applications (S0957-4174), 2012, 39(15): 12026-12031.
18	Razali M M, Rashid M F F A, Make M R A. Mathematical Modelling of Mixed-model Assembly Line Balancing Problem with Resources Constraints[J].IOP Conference Series: Materials Science and Engineering. IOP Publishing (S1757-8981), 2016, 160(1): 012002.
19	王成军, 刘佳敏. 考虑操作者工作负荷的混流线平衡问题研究[J]. 重庆理工大学学报(自然科学), 2020, 34(7): 100-107.
	Wang Chengjun, Liu Jiamin. Study on Mixed Flow Line Balance Considering Operator Workload[J]. Journal of Chongqing University of Technology (Natural Science), 2020, 34 (7): 100-107.
20	Hazır Ö, Dolgui A. Assembly Line Balancing under Uncertainty: Robust Optimization Models and Exact Solution Method[J]. Computers & Industrial Engineering(S0360-8352), 2013, 65(2): 261-267.
21	严能, 徐子奇, 舒帆. 基于 Lingo 的发动机装配线多目标平衡问题研究[J]. 物流工程与管理, 2015, 37(3): 233-236.
	Yan Neng, Xu Ziqi, Shu Fan. Research on Multi Objective Balancing of Engine Assembly Line Based on Lingo[J]. Logistics Engineering and Management, 2015, 37(3): 233-236.
22	Sikora C G S. Benders' Decomposition for the Balancing of Assembly Lines with Stochastic Demand[J]. European Journal of Operational Research (S0377-2217), 2021, 292(1): 108-124.
23	奚浩. 基于改进CCGA算法的混装线平衡与排序研究[D]. 青岛: 青岛理工大学, 2020.
	Xi Hao. Research on Balance and Sequencing of Mixed Loading Line Based on Improved CCGA Algorithm[D]. Qingdao: Qingdao University of Technology, 2020.
24	Hamzadayi A, Yildiz G. A Genetic Algorithm Based Approach for Simultaneously Balancing and Sequencing of Mixed-model U-lines with Parallel Workstations and Zoning Constraints[J]. Computers & Industrial Engineering, 2012, 62(1): 206-215.
25	谷新军, 郭秀萍. 随机混流U型拆卸线平衡排序问题多目标进化算法优化[J]. 运筹与管理, 2017, 26(9): 52-61.
	Gu Xinjun, Guo Xiuping. Multi Objective Evolutionary Algorithm Optimization for Stochastic Mixed Flow U-shaped Disassembly Line Equilibrium Scheduling Problem[J]. Operations Research and Management, 2017, 26(9): 52-61
26	Hazır Ö, Dolgui A. Assembly Line Balancing under Uncertainty: Robust Optimization Models and Exact Solution Method[J]. Computers & Industrial Engineering(S0360-8352), 2013, 65(2): 261-267.
27	Boysen N, Fliedner M, Scholl A. Assembly Line Balancing: Which Model to Use When?[J]. International Journal of Production Economics (S0925-5273), 2008, 111(2): 509-528.

工位	工序	MPS工作时间/min	最大工作量/min	最小工作量/min
1	1、 4	48.6	58.2	48.6
2	3、 5	55
3	2、 6、 7、 8、 10	58.2
4	9、 11	56

工位	工序	MPS工作时间/min	工位最大工作量/min	工位最小工作量/min
1	1、 2、 4	66.6	66.6	40.2
2	3、 5	55
3	6、 7、 8、 10	40.2
4	9、 11	56

	工位	工位负载/ min	工位负载极差	MPS 排序	一组MPS 完成时间/min		工位	工位负载/ min	工位负载极差	MPS 排序	一组MPS 完成时间/min
原方案	1	421.6	15.6	[ABCBC]	866.5	优化方案	1	415.8	0.1	[CBACB]	860.4
	2	414.2					2	415.9
	3	419.2					3	415.8
	4	418.8					4	415.8
	5	406					5	415.9
	6	415.3					6	415.9

[1]	罗兴华, 耿佳, 李明, 刘备, 王磊, 宋志平. 航空发动机机载模型迭代计算优化方法研究[J]. 系统仿真学报, 2022, 34(12): 2649-2658.
[2]	宫赤坤, 吴浔炜, 袁立鹏. 基于阻抗和虚拟模型的四足机器人控制方法[J]. 系统仿真学报, 2022, 34(10): 2152-2161.
[3]	唐红, 王栋, 宋博, 褚文奎, 何林远. 基于非线性赋权XGBoost算法的航班延误分类预测[J]. 系统仿真学报, 2021, 33(9): 2261-2269.
[4]	邓文浪, 李勇, 盘宏斌. 输入不平衡下隔离型AC-DC矩阵变换器控制策略研究[J]. 系统仿真学报, 2021, 33(7): 1729-1738.
[5]	董书琴, 张斌. 面向不平衡数据的网络流量异常检测方法[J]. 系统仿真学报, 2021, 33(3): 679-689.
[6]	罗龙溪, 吴建平, 陈云, 徐哲. 基于系统动力学的北京供需水关系仿真研究[J]. 系统仿真学报, 2019, 31(12): 2790-2801.
[7]	李晗, 范文慧, 冯袁, 朱梦妮, 张生晓. 基于系统动力学的汽车连杆生产线建模与仿真[J]. 系统仿真学报, 2018, 30(9): 3351-3359.
[8]	延渊渊, 范文慧, 冯袁. 汽车连杆生产线的建模与仿真[J]. 系统仿真学报, 2018, 30(9): 3360-3365.
[9]	胡效东, 柳庆磊, 刘馥瑜, 张德新. 氨基酸发酵罐内部气液流动特性研究[J]. 系统仿真学报, 2018, 30(5): 1988-1996.
[10]	马天雨, 王雅琳, 沈坤, 刘金平. 铝土矿连续球磨过程粒度分布预测模型[J]. 系统仿真学报, 2018, 30(2): 414-421.
[11]	李宗帅, 陈静. 一种模拟基底神经节机理的自主认知模型[J]. 系统仿真学报, 2018, 30(2): 427-434.
[12]	陈静. 柔性机器人多层启发式动态规划平衡认知研究[J]. 系统仿真学报, 2018, 30(1): 147-155.
[13]	朱俊杰, 刘浩然. 无刷直流电机三段式换相转矩脉动抑制仿真研究[J]. 系统仿真学报, 2017, 29(8): 1719-1725.
[14]	赵志刚, 李巍, 李有德, 王砚麟, 马延. 多机器人欠约束绳牵引系统静平衡工作空间分析[J]. 系统仿真学报, 2017, 29(4): 708-713.
[15]	邢志伟, 唐云霄. 枢纽机场航班保障服务时间估计[J]. 系统仿真学报, 2017, 29(11): 2856-2865.