机械加工车间设备布局建模与算法研究
|
摘要
制造系统设备布局设计是工业工程领域中最重要的研究内容之一,布局设计的好坏不仅关系到工厂的生产效率、厂房的利用率,也与设备的使用寿命、生产的安全性有重要关系。传统的设备布局主要依靠布局设计者的经验,缺乏科学的理论分析和定量化的计算,布局成本高、周期长。本文研究制造系统设备布局设计的数学优化方法,结合计算机仿真,完成生产线的优化配置。
本文首先对设备布局问题进行了详细的综述,总结了设备布局问题的有关概念,应用范围,主要要素以及布局基本原则,阐述了制造系统设备布局设计的传统理论方法——系统布局设计。
本文对设备布局问题建模时,物流成本考虑物流交叉的影响。在该思路下,定义逆流和顺流,横向物流和纵向物流,按照布局者的要求赋予不等的物流成本权重,在优化求解时自动排除一些物流交叉程度高的方案,实现最小化物流成本和降低物流交叉程度的平衡。实例表明,布局设计者可以对该模型的参数设置进行调整,从而得到满足其具体需求的结果。常见的建模方法中,对顺流、逆流的成本权重不作区别,可看作本文模型的一种特例。在此思路基础上,分别对两类设备布局问题——二次分配问题和混合整数规划问题建立数学模型。
在求解环节,本文研究了禁忌搜索算法在设备布局求解中的应用。首先对禁忌搜索算法进行介绍,接着详细说明了禁忌搜索算法的重要参数、求解策略和求解步骤。针对设备布局的二次分配问题和混合整数规划问题,说明了实现禁忌搜索算法的关键问题:构造启发式算法求初始解,解的编码,和实现混合整数规划的两阶段求解法。最后设计数值实验,考察多项参数对算法整体性能的影响,从而有助于设计一套合适的参数完成计算,实例计算的对比也表明禁忌搜索算法的优越性;数值实验同时也表明,混合整数规划问题的两阶段求解法具有良好的求解效果。
最后,以某运输机器厂搬迁新厂房项目为应用案例,用本文介绍的方法建立模型并求解,完成车间的设备布局。实际案例证明了本文的模型和求解方法的可行性和有效性。
Manufacture system facility layout is one of the most important research areas in industry. The quality of layout has impact on the production efficiency, the factory utilizing rate, the life cycle of the facility, and the production safety. The traditional facility layout, which mainly depends on the designer's experience, lacks of theoretical analysis and quantifies calculation and costs considerable time to finish it. This paper studies on efficient facility layout techniques to solve this problem and achieve an optimized resource arrangement with the cooperation of computer simulation.
First this paper makes a literature review of the facility layout problem. It summarized the concept, application area, main element and design principles of this problem; it also introduces the traditional theory and method of facility layout-Systematical Layout Program.
This paper, focusing on the study of layout optimization, come out with a layout model with material flow direction, which considers the asymmetry between the horizon and vertical flow as well as the forward and backward flow, and gives them different weights so that the solution with highly crossed flow will be eliminated. The designer can get various layout results through different parameter setting. The past models mostly ignored the asymmetry referred above, so that they can be a particular instance of the model in this paper. Then this paper studies two main kinds of layout problem: Quadratic Assignment Problem and Mixed Integer Programming.
To solve this problem, this paper studies the application of Taboo Search algorithm in layout problem. First this paper gives an introduction of Taboo search and its key parameters, solving strategies and process. For the QAP problem, this paper gives a heuristic algorithm to get an initial solution, and for the MIP problem, this paper constructs a two stages method. At last this paper gives a numerical experiment, through which the parameters' effects for the performance of algorithm were tested. Then in an instance, an appropriate set of parameters can be determined for a special problem and get better solution than the existing method. The numerical experiment also shows that the two stages method can solve the problem with a satisfying result.
In the practice project, a facility layout problem from a roller production company was studied and the model and the method introduced by this paper were proved to be feasible and effective.
本文首先对设备布局问题进行了详细的综述,总结了设备布局问题的有关概念,应用范围,主要要素以及布局基本原则,阐述了制造系统设备布局设计的传统理论方法——系统布局设计。
本文对设备布局问题建模时,物流成本考虑物流交叉的影响。在该思路下,定义逆流和顺流,横向物流和纵向物流,按照布局者的要求赋予不等的物流成本权重,在优化求解时自动排除一些物流交叉程度高的方案,实现最小化物流成本和降低物流交叉程度的平衡。实例表明,布局设计者可以对该模型的参数设置进行调整,从而得到满足其具体需求的结果。常见的建模方法中,对顺流、逆流的成本权重不作区别,可看作本文模型的一种特例。在此思路基础上,分别对两类设备布局问题——二次分配问题和混合整数规划问题建立数学模型。
在求解环节,本文研究了禁忌搜索算法在设备布局求解中的应用。首先对禁忌搜索算法进行介绍,接着详细说明了禁忌搜索算法的重要参数、求解策略和求解步骤。针对设备布局的二次分配问题和混合整数规划问题,说明了实现禁忌搜索算法的关键问题:构造启发式算法求初始解,解的编码,和实现混合整数规划的两阶段求解法。最后设计数值实验,考察多项参数对算法整体性能的影响,从而有助于设计一套合适的参数完成计算,实例计算的对比也表明禁忌搜索算法的优越性;数值实验同时也表明,混合整数规划问题的两阶段求解法具有良好的求解效果。
最后,以某运输机器厂搬迁新厂房项目为应用案例,用本文介绍的方法建立模型并求解,完成车间的设备布局。实际案例证明了本文的模型和求解方法的可行性和有效性。
Manufacture system facility layout is one of the most important research areas in industry. The quality of layout has impact on the production efficiency, the factory utilizing rate, the life cycle of the facility, and the production safety. The traditional facility layout, which mainly depends on the designer's experience, lacks of theoretical analysis and quantifies calculation and costs considerable time to finish it. This paper studies on efficient facility layout techniques to solve this problem and achieve an optimized resource arrangement with the cooperation of computer simulation.
First this paper makes a literature review of the facility layout problem. It summarized the concept, application area, main element and design principles of this problem; it also introduces the traditional theory and method of facility layout-Systematical Layout Program.
This paper, focusing on the study of layout optimization, come out with a layout model with material flow direction, which considers the asymmetry between the horizon and vertical flow as well as the forward and backward flow, and gives them different weights so that the solution with highly crossed flow will be eliminated. The designer can get various layout results through different parameter setting. The past models mostly ignored the asymmetry referred above, so that they can be a particular instance of the model in this paper. Then this paper studies two main kinds of layout problem: Quadratic Assignment Problem and Mixed Integer Programming.
To solve this problem, this paper studies the application of Taboo Search algorithm in layout problem. First this paper gives an introduction of Taboo search and its key parameters, solving strategies and process. For the QAP problem, this paper gives a heuristic algorithm to get an initial solution, and for the MIP problem, this paper constructs a two stages method. At last this paper gives a numerical experiment, through which the parameters' effects for the performance of algorithm were tested. Then in an instance, an appropriate set of parameters can be determined for a special problem and get better solution than the existing method. The numerical experiment also shows that the two stages method can solve the problem with a satisfying result.
In the practice project, a facility layout problem from a roller production company was studied and the model and the method introduced by this paper were proved to be feasible and effective.
引文
[1]赵玲,王培麟.企业物流系统分析与再布置设计研究[J].番禺职业技术学院学报,2005,4(4):529.
[2] Dowsland K A,Dowsland W B.Packing problems[J].European Journal ofOperational Research,1992,56:2-14
[3] Dyckhoff H.A typology of cutting and packing problem[J].European Journal ofOpetational Research,1990,44:145-159
[4] Dowsland W B.Two and three dimensional packing problems and solution methods[J].New Zealand Operational Research,1985,13(1):118-119
[5]齐继阳,竺长安,曾议.遗传算法在设备布局设计中的应用[J] .中国设备工程,2005(10) :426.
[6]李火生,李志华,钟毅芳,等.生产车间设备布局线性模型及算法研究[J] .计算机工程与应用,2002 ,38 (11) :2212225.
[7]锁小红,刘战强.制造系统设备布局的建模理论与求解方法[J]计算机集成制造系统.Vol.13 No.10
[8] Dudzinski K.Exact methods for the knapsack problem and its generalizations.European Journal of Operational Research,1987,28:3-21
[9] Hellstrom B J,Kannal L N.Knapsack packing networks.IEEE Transactions onNeural networks,1992,3(2):302-307,
[10] Urban.TL. Computational Performance and Efficiency of Lower-bound Procedures of the Dynamic Facility Layout. European Journal of Operational Researeh.1992,57:271一277
[11]康立山,谢云,尤矢勇,罗祖华.非数值并行算法-模拟退火算法:第一册[M]背景科学出版社2003
[12]王凌.智能优化算法机器应用[M]北京清华大学出版社2003
[13] Wang Dingyi Wang Liya. Application of Genetic Algorithms in Facility Layout[王定益,王丽亚.一种改进遗传算法在生产车间设备布局中的应用[J]计算机工程与应用2005,17(5):156~160]
[14]龚全胜.基于遗传算法的制造系统虚拟设备布局设计[D]湖北武汉:华中科技大学,2004
[15]柏莆荣,秦永法.基于智能优化算法的设备布局设计[J]组合机床与自动化加工技术2004,10(2)73~79
[16] Amine Drira, Henri Pierreval, Sonia Hajri-Gabouj.Facility layout problems: A survey[J].Annual Reviews in Control, Volume 31, Issue 2, 2007, Pages 255-267
[17]贾振元,等.计算机仿真技术在制造系统规划设计及运行中的应用[J] .柴油机设计与制造,1998.3,26-29
[18]熊光楞,范文慧.21世纪制造业的建模与仿真技术[J].系统仿真学报.2004.第16卷,第9期.1884-1886
[19]王红军.基于eM_plant的FMS仿真建模技术研究[J]新技术新工艺.机械加工与自动化2004.第7期,9-11
[20]康凤举,杨惠珍,高立娥.现代仿真技术与应用[M].北京:国防工业出版社.2006
[21]梁海峰,刘玉君,邓燕萍.基于仿真的自动化钢料加工车间设计及生产效率评价[J].造船技术.2005.第3期,27-30
[22]王红军.变速箱生产线的建模与仿真技术研究[J].北京机械工业学院学报.2006.第21卷,第1期,11-14
[23]冯惠军,冯允成.一个面向对象的仿真建模框架[J].系统工程理论与实践.1999.5,61-66
[24]邓子琼,等.柔性制造系统建模及仿真[M] .北京:国防工业出版社,1993
[25]肖杰华,陈立平,郭宇,王书亭.面向生产制造过程的虚拟仿真系统建模研究[J].计算机工程.2002.第28卷,第6期,44-46
[26]孙威,张浩,朱志浩,马玉敏.数字化工厂技术在生产线规划中的应用[J].计算机辅助工程2005.14卷,3期,43-46
[27]候扬,范秀敏,严隽琪,王丽亚.基于仿真的制造系统对象建模及应用[J],计算机集成制造系统CIMS,2001,第7卷,第5期,42-46
[28]范秀敏,任培恩,卫东,皮兴忠.基于标准作业时间和仿真的装配线规划[J].工业工程与管理.2001.第5期,10-13
[29]吴耀华,颜永年,曾庆宏.基于Petri网模型的物流系统建模[J].机械工业自动化, 1996, (3): 6-8.
[30]常发亮,刘长有自动化立体仓库输送系统调度的优化仿真及其应用研究[J];系统仿真学报; 1998年05期
[31]林立千,设施规划与物流中心设计[M]北京,清华大学出版社,2003
[32]龚全胜李世其.[D]基于遗传算法的制造系统虚拟设备布局设计湖北武汉华中科技大学
[33]朱耀祥朱立强设施规划与物流[M]北京:机械工业出版社2004
[34]宋华明韩玉启基于遗传算法的U型生产线平衡[J]系统工程学报2002.17(5)424-429
[35] Lawler EL. The quadratic assignment problem[J]. Management Science,1963,9(4):586-599
[36]常政威,谢晓娜,熊光泽,求解二次分配问题的改进禁忌搜索算法,微电子学与计算机Vol25 No.2 2008.02
[37] M. Ficko, M. Brezocnik, J. Balic,Designing the layout of single-and multiple-rows flexible manufacturing system by genetic algorithms[J],Journal of Materials Processing Technology(2004) 150–158
[38] Sai-On Cheung), Thomas Kin-Lun Tong, Chi-Ming Tam. Site pre-cast yard layout arrangement through genetic algorithms[J]. Automation in Construction 11(2002).35–46
[39] Sunderesh S. Heragu, Andrew Kusiak.Efficient models for the facility layout problem[J].European Journal of Operational Research, Volume 53, Issue 1, 5 July 1991, Pages 1-13
[2] Dowsland K A,Dowsland W B.Packing problems[J].European Journal ofOperational Research,1992,56:2-14
[3] Dyckhoff H.A typology of cutting and packing problem[J].European Journal ofOpetational Research,1990,44:145-159
[4] Dowsland W B.Two and three dimensional packing problems and solution methods[J].New Zealand Operational Research,1985,13(1):118-119
[5]齐继阳,竺长安,曾议.遗传算法在设备布局设计中的应用[J] .中国设备工程,2005(10) :426.
[6]李火生,李志华,钟毅芳,等.生产车间设备布局线性模型及算法研究[J] .计算机工程与应用,2002 ,38 (11) :2212225.
[7]锁小红,刘战强.制造系统设备布局的建模理论与求解方法[J]计算机集成制造系统.Vol.13 No.10
[8] Dudzinski K.Exact methods for the knapsack problem and its generalizations.European Journal of Operational Research,1987,28:3-21
[9] Hellstrom B J,Kannal L N.Knapsack packing networks.IEEE Transactions onNeural networks,1992,3(2):302-307,
[10] Urban.TL. Computational Performance and Efficiency of Lower-bound Procedures of the Dynamic Facility Layout. European Journal of Operational Researeh.1992,57:271一277
[11]康立山,谢云,尤矢勇,罗祖华.非数值并行算法-模拟退火算法:第一册[M]背景科学出版社2003
[12]王凌.智能优化算法机器应用[M]北京清华大学出版社2003
[13] Wang Dingyi Wang Liya. Application of Genetic Algorithms in Facility Layout[王定益,王丽亚.一种改进遗传算法在生产车间设备布局中的应用[J]计算机工程与应用2005,17(5):156~160]
[14]龚全胜.基于遗传算法的制造系统虚拟设备布局设计[D]湖北武汉:华中科技大学,2004
[15]柏莆荣,秦永法.基于智能优化算法的设备布局设计[J]组合机床与自动化加工技术2004,10(2)73~79
[16] Amine Drira, Henri Pierreval, Sonia Hajri-Gabouj.Facility layout problems: A survey[J].Annual Reviews in Control, Volume 31, Issue 2, 2007, Pages 255-267
[17]贾振元,等.计算机仿真技术在制造系统规划设计及运行中的应用[J] .柴油机设计与制造,1998.3,26-29
[18]熊光楞,范文慧.21世纪制造业的建模与仿真技术[J].系统仿真学报.2004.第16卷,第9期.1884-1886
[19]王红军.基于eM_plant的FMS仿真建模技术研究[J]新技术新工艺.机械加工与自动化2004.第7期,9-11
[20]康凤举,杨惠珍,高立娥.现代仿真技术与应用[M].北京:国防工业出版社.2006
[21]梁海峰,刘玉君,邓燕萍.基于仿真的自动化钢料加工车间设计及生产效率评价[J].造船技术.2005.第3期,27-30
[22]王红军.变速箱生产线的建模与仿真技术研究[J].北京机械工业学院学报.2006.第21卷,第1期,11-14
[23]冯惠军,冯允成.一个面向对象的仿真建模框架[J].系统工程理论与实践.1999.5,61-66
[24]邓子琼,等.柔性制造系统建模及仿真[M] .北京:国防工业出版社,1993
[25]肖杰华,陈立平,郭宇,王书亭.面向生产制造过程的虚拟仿真系统建模研究[J].计算机工程.2002.第28卷,第6期,44-46
[26]孙威,张浩,朱志浩,马玉敏.数字化工厂技术在生产线规划中的应用[J].计算机辅助工程2005.14卷,3期,43-46
[27]候扬,范秀敏,严隽琪,王丽亚.基于仿真的制造系统对象建模及应用[J],计算机集成制造系统CIMS,2001,第7卷,第5期,42-46
[28]范秀敏,任培恩,卫东,皮兴忠.基于标准作业时间和仿真的装配线规划[J].工业工程与管理.2001.第5期,10-13
[29]吴耀华,颜永年,曾庆宏.基于Petri网模型的物流系统建模[J].机械工业自动化, 1996, (3): 6-8.
[30]常发亮,刘长有自动化立体仓库输送系统调度的优化仿真及其应用研究[J];系统仿真学报; 1998年05期
[31]林立千,设施规划与物流中心设计[M]北京,清华大学出版社,2003
[32]龚全胜李世其.[D]基于遗传算法的制造系统虚拟设备布局设计湖北武汉华中科技大学
[33]朱耀祥朱立强设施规划与物流[M]北京:机械工业出版社2004
[34]宋华明韩玉启基于遗传算法的U型生产线平衡[J]系统工程学报2002.17(5)424-429
[35] Lawler EL. The quadratic assignment problem[J]. Management Science,1963,9(4):586-599
[36]常政威,谢晓娜,熊光泽,求解二次分配问题的改进禁忌搜索算法,微电子学与计算机Vol25 No.2 2008.02
[37] M. Ficko, M. Brezocnik, J. Balic,Designing the layout of single-and multiple-rows flexible manufacturing system by genetic algorithms[J],Journal of Materials Processing Technology(2004) 150–158
[38] Sai-On Cheung), Thomas Kin-Lun Tong, Chi-Ming Tam. Site pre-cast yard layout arrangement through genetic algorithms[J]. Automation in Construction 11(2002).35–46
[39] Sunderesh S. Heragu, Andrew Kusiak.Efficient models for the facility layout problem[J].European Journal of Operational Research, Volume 53, Issue 1, 5 July 1991, Pages 1-13