基于有向网络理论的U型装配线平衡问题研究
|
摘要
针对制造企业的复杂装配线工作站优化设计和生产柔性化要求,提出基于有向网络理论的解决办法.首先结合装配线平衡问题简单算例,说明装配流水线作业流程图满足有向图特征,并用矩阵表示,将复杂网络图信息转换为可计算的数据信息,实现了流水装配线平衡的计算机计算与程序设计.其次以29个节点装配流程为例,在满足作业元素的时间、流水节拍以及作业元素优先关系的约束条件下,以装配线时间损失率最小为优化目标,建立装配线平衡问题的数学模型.最后利用有向图网络理论计算装配线平衡问题和U型装配线设计,平衡率达到93.81%,验证了有向网络图理论求解生产线平衡问题的合理性和有效性,并实现了计算机程序计算.本研究为制造企业大型流水线设备自动化设计提供了一种新方法.
For the optimization design and flexible production requirements of work stations for complex assembly lines in manufacturing enterprises,a solution based on the directed net theory is proposed. Firstly,combining with a simple example of assembly line balancing problem,it shows that the flow chart of assembly line satisfies the features of directed graph and is represented by directed graph matrix,which converts complex network graph information into computable data and realizes the assembly line of computer calculation and program design. Secondly,assembly line with 29 nodes is taken as an example; the mathematical model of assembly line balancing problem is established with the minimum time loss of assembly line as the optimization objective,under the constraint of the time,cycle-time and precedence of job elements. At last,the balancing problem of assembly line and the design of U assembly line are calculated by the use of the network theory of directed graph and line balance rate reaches 93. 81%,which verifies the rationality and validity of the directed net theory to solve the assembly line balancing problem and realizes the calculation of computer program,which provides a new method for automation design of large-scale assembly line equipment in manufacturing enterprises.
For the optimization design and flexible production requirements of work stations for complex assembly lines in manufacturing enterprises,a solution based on the directed net theory is proposed. Firstly,combining with a simple example of assembly line balancing problem,it shows that the flow chart of assembly line satisfies the features of directed graph and is represented by directed graph matrix,which converts complex network graph information into computable data and realizes the assembly line of computer calculation and program design. Secondly,assembly line with 29 nodes is taken as an example; the mathematical model of assembly line balancing problem is established with the minimum time loss of assembly line as the optimization objective,under the constraint of the time,cycle-time and precedence of job elements. At last,the balancing problem of assembly line and the design of U assembly line are calculated by the use of the network theory of directed graph and line balance rate reaches 93. 81%,which verifies the rationality and validity of the directed net theory to solve the assembly line balancing problem and realizes the calculation of computer program,which provides a new method for automation design of large-scale assembly line equipment in manufacturing enterprises.
引文
[1]汪小帆,李翔,陈关荣.网络科学导论[M].北京:高等教育出版社,2012.
[2]CHUNG F.Graph theory in the information age[J].Notices of AMS,2010,57(6):726-732.
[3]RIGGS R J,BATTAIA O,HU S J.Disassembly line balancing under high variety of end of life states using a joint precedence graph approach[J].Journal of Manufacturing Systems,2015,37(4):638-648.
[4]刘新华,张旭堂,刘文剑.基于改进最大最小蚂蚁系统的多工艺路线决策方法[J].计算机集成制造系统,2008,14(12):2414-2420.LIU Xin-hua,ZHANG Xu-tang,LIU Wen-jian.Multiprocess routes decision-making methodology based on improved max-min ant system[J].Computer Integrated Manufacturing Systems,2008,14(12):2414-2420.
[5]黄伟军,蔡力钢,胡于进,等.基于遗传算法与有向图拓扑排序的工艺路线优化[J].计算机集成制造系统,2009,15(2):1770-1779.HUANG Wei-jun,CAI Li-gang,HU Yu-jin,et al.Process planning optimization based on genetic algorithm and topological sort algorithm for digraph[J].Computer Integrated Manufacturing Systems,2009,15(2):1770-1779.
[6]卢素伟.基于有向加权图的复杂产品生产线性能分析与优化[D].西安:西安电子科技大学,2014.
[7]KUCUKKOC I,ZHANG D Z.Balancing of parallel Ushaped assembly lines[J].Computers&Operations Research,2015,64(C):233-244.
[8]MILTENBURG J.Balancing U-lines in a multiple U-line facility[J].European Journal of Operational Research,1998,109(1):1-23.
[9]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.
[10]BENNETT G B,BYRD J J.A trainable heuristic procedure for the assembly line balancing problem[J].AIIE Transactions,1976,8(2):195-201.
[11]刘俨后,左敦稳,张丹.斗链装配线的建模与平衡点特性[J].华南理工大学学报(自然科学版),2014,42(4):111-117.LIU Yan-hou,ZUO Dun-wen,ZHANG Dan.Modeling and balance point characteristics of bucket brigades assembly line[J].Journal of South China University of Technology(Natural Science Edition),2014,42(4):111-117.
[12]王海英,黄强,李传涛.图论算法及其MATLAB实现[M].北京:北京航空航天大学出版社,2010.
[13]吴尔飞.双边装配线平衡技术的研究[D].上海:上海交通大学,2009.
[14]宋华明.装配流水线平衡和投产排序:模型、算法与仿真[M].北京:电子工业出版社,2016.
[15]陈荣秋,马士华.生产运作管理(第二版)[M].北京:高等教育出版社,2009.
[2]CHUNG F.Graph theory in the information age[J].Notices of AMS,2010,57(6):726-732.
[3]RIGGS R J,BATTAIA O,HU S J.Disassembly line balancing under high variety of end of life states using a joint precedence graph approach[J].Journal of Manufacturing Systems,2015,37(4):638-648.
[4]刘新华,张旭堂,刘文剑.基于改进最大最小蚂蚁系统的多工艺路线决策方法[J].计算机集成制造系统,2008,14(12):2414-2420.LIU Xin-hua,ZHANG Xu-tang,LIU Wen-jian.Multiprocess routes decision-making methodology based on improved max-min ant system[J].Computer Integrated Manufacturing Systems,2008,14(12):2414-2420.
[5]黄伟军,蔡力钢,胡于进,等.基于遗传算法与有向图拓扑排序的工艺路线优化[J].计算机集成制造系统,2009,15(2):1770-1779.HUANG Wei-jun,CAI Li-gang,HU Yu-jin,et al.Process planning optimization based on genetic algorithm and topological sort algorithm for digraph[J].Computer Integrated Manufacturing Systems,2009,15(2):1770-1779.
[6]卢素伟.基于有向加权图的复杂产品生产线性能分析与优化[D].西安:西安电子科技大学,2014.
[7]KUCUKKOC I,ZHANG D Z.Balancing of parallel Ushaped assembly lines[J].Computers&Operations Research,2015,64(C):233-244.
[8]MILTENBURG J.Balancing U-lines in a multiple U-line facility[J].European Journal of Operational Research,1998,109(1):1-23.
[9]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.
[10]BENNETT G B,BYRD J J.A trainable heuristic procedure for the assembly line balancing problem[J].AIIE Transactions,1976,8(2):195-201.
[11]刘俨后,左敦稳,张丹.斗链装配线的建模与平衡点特性[J].华南理工大学学报(自然科学版),2014,42(4):111-117.LIU Yan-hou,ZUO Dun-wen,ZHANG Dan.Modeling and balance point characteristics of bucket brigades assembly line[J].Journal of South China University of Technology(Natural Science Edition),2014,42(4):111-117.
[12]王海英,黄强,李传涛.图论算法及其MATLAB实现[M].北京:北京航空航天大学出版社,2010.
[13]吴尔飞.双边装配线平衡技术的研究[D].上海:上海交通大学,2009.
[14]宋华明.装配流水线平衡和投产排序:模型、算法与仿真[M].北京:电子工业出版社,2016.
[15]陈荣秋,马士华.生产运作管理(第二版)[M].北京:高等教育出版社,2009.