Research on Mixed Flow Line Balancing and Scheduling Optimization with Multiple Constraints

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

Abstract

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

CLC Number:

TP399

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.

Figures/Tables 13

Fig. 1

Fig. 2

Fig. 3

Table 1

Table 2

Table 3

Table 4

Table 5

Fig. 4

Table 6

Comparison of results obtained by two algorithms

实例参数	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

Table 6

Fig. 5

Fig. 6

Table 7

References 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.

工序	工位
工序	1	2	3	4
1	1	1	1	1
2	1	1	1	1
3	0	1	0	0
4	1	1	1	1
5	1	1	1	1
6	1	1	1	1
7	0	0	1	0
8	1	1	1	1
9	1	1	1	1
10	1	1	1	1
11	1	1	1	1

工位	工序	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]	Zhenping Li, Guang Yang, Qianqian Han. Vehicle Routing Problem with Refined Oil Secondary Distribution Considering Workload Balance [J]. Journal of System Simulation, 2022, 34(2): 221-233.
[2]	Chikun Gong, Xunwei Wu, Lipeng Yuan. Control of Quadruped Robot Based on Impedance and Virtual Model [J]. Journal of System Simulation, 2022, 34(10): 2152-2161.
[3]	Li Gang, Zhang Caixia, Hu Shaolin, Wang Xiangdong, Guo Jing. WSN Clustering Routing Protocol for Bridge Structure Health Monitoring [J]. Journal of System Simulation, 2022, 34(1): 62-69.
[4]	Tang Hong, Wang Dong, Song Bo, Chu Wenkui, He Linyuan. Classification of Flight Delay Based on Nonlinear Weighted XGBoost [J]. Journal of System Simulation, 2021, 33(9): 2261-2269.
[5]	Deng Wenlang, Li Yong, Pan Hongbin. Research on Control Strategy of Isolated AC-DC Matrix Converter under Input Unbalance [J]. Journal of System Simulation, 2021, 33(7): 1729-1738.
[6]	Dong Shuqin, Zhang Bin. Network Traffic Anomaly Detection Method for Imbalanced Data [J]. Journal of System Simulation, 2021, 33(3): 679-689.
[7]	Dang Jianwu, Tan Ling. An Intrusion Detection Algorithm Based on IFOA and WELM [J]. Journal of System Simulation, 2021, 33(2): 331-338.
[8]	Luo Longxi, Wu Jianping, Chen Yun, Xu Zhe. System Dynamics Modeling for Simulation of Water Supply and Demand Relationship in Beijing [J]. Journal of System Simulation, 2019, 31(12): 2790-2801.
[9]	Wang Xiao, Liu Yaqi, Tao Yuben. Parallel Design and Load Balance of OpenMP Based Warfighting Simulation [J]. Journal of System Simulation, 2018, 30(6): 2206-2215.
[10]	Hu Xiaodong, Liu Qinglei, Liu Fuyu, Zhang Dexin. Gas-liquid Flow Characteristics Study on the Amino Acid Fermentation Tank [J]. Journal of System Simulation, 2018, 30(5): 1988-1996.
[11]	Ma Tianyu, Wang Yalin, Shen Kun, Liu Jinping. Prediction Model of Particle Size Distribution in Bauxite Continuous Ball Milling Process [J]. Journal of System Simulation, 2018, 30(2): 414-421.
[12]	Hao Yaohui, Han Jihong, Guo Hong, Liu Shuxin. Modeling of Distributed Service Composition System Based on Bipartite Network [J]. Journal of System Simulation, 2018, 30(1): 1-8.
[13]	Zhu Junjie, Liu Haoran. Simulation of Three-region Commutation Torque Ripple Reduction for Brushless DC Motor [J]. Journal of System Simulation, 2017, 29(8): 1719-1725.
[14]	Gao Mei, Wang Bingyuan, Zhang Dandan, Sun Zhaorong. Study on Balanced Energy-consumption Routing Protocol of Airfield Single-lamp Monitoring System [J]. Journal of System Simulation, 2017, 29(8): 1772-1779.
[15]	Xing Zhiwei, Tang Yunxiao. Flight Support Service Time Estimation of Hub Airport [J]. Journal of System Simulation, 2017, 29(11): 2856-2865.