基于改进型遗传算法的混流U型装配线第二类平衡问题

doi:10.12066/j.issn.1007-2861.2165

上海大学学报(自然科学版) ›› 2021, Vol. 27 ›› Issue (2): 360-368.doi: 10.12066/j.issn.1007-2861.2165

基于改进型遗传算法的混流U型装配线第二类平衡问题

彭运芳, 梁玉珍, 夏蓓鑫()

上海大学管理学院, 上海 200444

收稿日期:2019-04-15 出版日期:2021-04-30 发布日期:2021-04-27
通讯作者: 夏蓓鑫 E-mail:bxxia@shu.edu.cn
作者简介:夏蓓鑫(1984—), 男, 博士, 研究方向为制造系统建模与优化. E-mail:bxxia@shu.edu.cn
基金资助:
国家留学基金委资助项目(201906895026)

An improved genetic algorithm based mixed-model U-shaped assembly line balancing problem of type-Ⅱ

PENG Yunfang, LIANG Yuzhen, XIA Beixin()

School of Management, Shanghai University, Shanghai 200444, China

Received:2019-04-15 Online:2021-04-30 Published:2021-04-27
Contact: XIA Beixin E-mail:bxxia@shu.edu.cn

摘要/Abstract

摘要：

针对最小化生产节拍的第二类混流U型装配线平衡问题, 构建了混合整数规划模型, 并设计了改进型遗传算法求解. 在遗传算法的解码过程中, 采用3种搜索方式将工序分配到工作站, 比较了3种搜索方式下的工作站时间, 并参照期望生产节拍值筛选出最优的工作站分配方式, 再根据分配方式的寻优情况判断是否自动更新期望生产节拍值. 通过大量的标准算例, 证明了改进型遗传算法的有效性. 最后, 结合实际案例分析, 再次验证了混合整数规划模型和改进型遗传算法的有效性.

关键词: 混流装配线平衡, U型装配线, 混合整数规划, 改进型遗传算法

Abstract:

To solve the type-Ⅱ balancing problem of a mixed-model U-shaped assembly line to minimise the cycle time, a mathematical model was established and an improved genetic algorithm was designed. In the decoding process of the genetic algorithm, three search techniques were used to assign tasks to workstations, and workstation times under these search techniques were compared. The optimal assignment was selected according to the expected cycle time. The task assignment result determined whether to update the value of the expected cycle time automatically. The performance of the proposed improved genetic algorithm was proved by a set of benchmark instances. Finally, a practical balancing problem was analysed and effectively solved by the proposed method.

Key words: mixed-model assembly line balancing, U-shaped assembly line, mixed integer programming, improved genetic algorithm

中图分类号:

F273

彭运芳, 梁玉珍, 夏蓓鑫. 基于改进型遗传算法的混流U型装配线第二类平衡问题[J]. 上海大学学报(自然科学版), 2021, 27(2): 360-368.

PENG Yunfang, LIANG Yuzhen, XIA Beixin. An improved genetic algorithm based mixed-model U-shaped assembly line balancing problem of type-Ⅱ[J]. Journal of Shanghai University（Natural Science Edition）, 2021, 27(2): 360-368.

图/表 11

图1

图2

表1

图3

图4

图5

图6

图7

表2

表3

表4

参考文献 11

[1]	Simaria A S, Vilarinho P M. A genetic algorithm based approach to the mixed-model assembly line balancing problem of type Ⅱ[J]. Computers & Industrial Engineering, 2004,47(4):391-407.
[2]	Li Z, Tang Q, Zhang L P. Two-sided assembly line balancing problem of type Ⅰ: improvements, a simple algorithm and a comprehensive study[J]. Computers & Operations Research, 2017,79:78-93.
[3]	Tang Q H, Rao D, Li Z, et al. Improved iterated local search algorithm for type Ⅰ mixed-model two-sided assembly line balancing problem[J]. Computer Integrated Manufacturing Systems, 2018(2):390-399.
[4]	Nejad M G, Kashan A H, Shavarani S M. A novel competitive hybrid approach based on grouping evolution strategy algorithm for solving U-shaped assembly line balancing problems[J]. Production Engineering, 2018,12(10):1-12.
[5]	Li M, Tang Q, Zheng Q, et al. Rules-based heuristic approach for the U-shaped assembly line balancing problem[J]. Applied Mathematical Modelling, 2017,48:423-439.
[6]	Roshani A, Giglio D. Simulated annealing algorithms for the multi-manned assembly line balancing problem: minimizing cycle time[J]. International Journal of Production Research, 2017,55(10):21.
[7]	Moreira M C O, Pastor R, Costa A M, et al. The multi-objective assembly line worker integration and balancing problem of type-2[J]. Computers & Operations Research, 2017,82:114-125.
[8]	Oksuz M K, Buyukozkan K, Satoglu S I. U-shaped assembly line worker assignment and balancing problem: a mathematical model and two meta-heuristics[J]. Computers & Industrial Engineering, 2017. DOI: 10.1016/j.cie.2017.08.030. doi: 10.1016/j.cie.2018.04.001 pmid: 32288046
[9]	Ogan D, Azizoglu M. A branch and bound method for the line balancing problem in U-shaped assembly lines with equipment requirements[J]. Journal of Manufacturing Systems, 2015,36:46-54.
[10]	Han W, Yang H, Han B. The balance of mixed-model U-shaped assembly line based on a fuzzy goal programming[C]// International Conference on Information Management, Innovation Management and Industrial Engineering, IEEE. 2011: 493-497.
[11]	韩煜东, 董双飞, 谭柏川. 基于改进遗传算法的混装线多目标优化[J]. 计算机集成制造系统, 2015,21(6):1476-1485.
	Han Y D, Dong S F, Tan B C. Multi-objective optimization for mixed-model assembly line balancing problem based on improved genetic algorithm[J]. Computer Integrated Manufacturing Systems, 2015,21(6):1476-1485.

基于改进型遗传算法的混流U型装配线第二类平衡问题

An improved genetic algorithm based mixed-model U-shaped assembly line balancing problem of type-Ⅱ

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 11

相关文章 2

编辑推荐

Metrics

本文评价

[1]	刘婵娟, 胡志华. 基于滚动计划的堆场出口箱存储位置分配两阶段模型[J]. 上海大学学报(自然科学版), 2017, 23(5): 789-800.
[2]	于亚茹, 姚奕荣. 求解混合整数规划问题的指数变差积分算法[J]. 上海大学学报(自然科学版), 2017, 23(2): 276-289.