车间布局问题综述-施景娥.doc

专业文献综述题 目: 车间布局问题综述 姓 名: 施景娥 学 院: 工学院 专 业: 工业工程 班 级: 工业工程62班 学 号: 3116220 指导教师: 熊燕华 职称: 讲师 2009年11月22日南京农业大学教务处制车间布局问题综述工业工程专业 施景娥 指导教师 熊燕华摘要：本文概述了车间布局的相关概念，强调了研究车间布局的重大意义。在分析了前人的相应的车间布局模型，主要包括离散模型、连续模型、模糊模型和多目标布局模型等问题模型的基础上，详细阐述了SLP、单位对两两交换法、CRAFT、MULTIPLE、模拟退火算法和遗传算法等各类车间布局问题解法的概念，并分析了其优缺点。关键词：车间布局；系统布置设计；MULTIPLE；遗传算法；模拟退火算法 A Review of Workshop Layout ProblemStudent majoring in Industrial Engineering JingE ShiTutor Yanhua XiongABSTRACT: This thesis summarizes the related concepts of the facilities layout and stresses the great significance of the research of workshop layout. On the basis of analyses the relevant models of the workshop layout by our predecessors like dispersed model, continuous model, misty model and multiple target model, the thesis expatiates the conception and assesses the advantages and the disadvantagesof the solutionsof workshop layout problem, such as Systematic Layout Planning, CRAFT, MULTIPLE, Simulated Annealing, Genetic Algorithm.KEY WORDS: Workshop Layout；SLP；MULTIPLE；Genetic Algorithm；Simulated Annealing1 引言 近年来，随着生产技术和设备的快速发展，只有少数公司能够在基本维持其市场地位不变的情况下保留它们的老设施和布置方案。为提高生产率，只要新技术确实可行，就要尽快采用。新技术的使用必将使得生产工艺和设备的改变，而这种改变所带来的整体系统不协调问题只能通过重新进行布局设计才能实现。制造设施中20%50%的总运营成本是物料搬运成本，而且一般认为有效的布局设计可以将这些成本降低到10%30%1。布局的含义较为广泛,可依序分为设施布局、工厂布局、车间布局和设备布局。设施布局是指企业根据经营目标和生产纲领,在确定的空间内,从原材料的接收、零件和产品的制造直到成品的包装、发运的全过程,将人员、设备、物料所需空间做适当、有效地分配与组合,以获得最大的生产经济效益,工厂布局为设施布局的一部分,包括工厂总体布局和车间布局;车间布局主要解决各生产工部、工段、服务辅助部门、储存设施等作业单位和工作地、设备、通道、管线之间的相互位置,以及物料搬运的流程和方式2。设备布局是指在一定的生产环境下,制造系统设计人员根据生产目标确定制造系统中各设备的布置形式和位置。本文主要研究车间布局。本文所研究的制造业生产系统的车间布局问题是我国实际生产中的现实问题，也是很多国有大型制造业企业亟待解决的难题。设计一个优良的设备布局可以给我们的企业带来诸多好处：优良的车间布局不仅可以减少生产系统中的物料搬运费用，从而降低企业的总体运营成本，还能加快物料处理效率，减少在制品的停留时间和数量，提高企业生产效率，使企业对市场需求做出及时地响应，增强企业的市场竞争能力。所以，探讨研究制造系统的车间布局问题具有很重要的理论意义和实际应用价值。本文分析了离散模型、连续模型、模糊模型和多目标布局模型等车间布局的问题模型，探讨并总结了三种解法类型即确定性算法、启发式算法和智能算法的各具体算法和其优缺点，为进一步研究车间布局问题奠定了良好的基础。2 车间布局的问题模型对于车间布局问题，根据影响生产的要素和问题的类型（静态布局、动态布局），可以设计不同的数学模型来表达并求解。车间布局问题模型的设计主要以图论、神经网络、单目标和多目标规划等数学理论作为基础。设备布局模型主要有：离散模型、连续模型，在某些数据不确定的情况下，还可建立模糊模型3。2.1 离散模型有些车间的布局是离散的，最常见的离散模型是QAP（Quadratic Assignment Problem，QAP，二次分配）模型。QAP 模型的目标函数为：其中表示设备i 和j之间的物流量，是布局在排列k 时单位由地点j 到的运输成本4。将工厂的区域划分为大小相等的长方形块，每个车间由不同的块组合而成5，如图1-1所示。优化目标是找到一个布局方案使物流总费用Cost(A)最小。Edwards等6，Lewis和Block7（点位描述），Christopher和Wilhelm8，Hillier9（等面积描述），Drezner10（圆形描述）等人所提出的算法均属此类。图1-1 离散模型2.2 连续模型一些文献涉及的实际问题要求布局是连续的，如图1-2所示。通常可以用MIP（Mixed Integer Programming，MIP混合整数规划）（Das，1993）11来表达。MIP模型的目标函数为：，其中fm为设备i和j之间的流量， 分别为设备i和j之间的x、y方向的距离）。图1-2 连续模型连续模型大都用于解决静态设备的精确定位问题，很少用于解决动态设备布局问题，但Dunker在2005年用连续模型研究了非等面积动态设备布局问题。2.3 模糊模型模糊模型是用模糊数学语言描述客观事物的某些特征和内在联系而建立的模型。在许多实际问题中，影响车间布局的数据往往是模糊的，不是确切的。模糊逻辑可以用来对不精确的问题进行处理。基于模糊概念的一些方法可以用于设计模糊布局。甘骏人在1989的文章中，在布局设计研究时应用了模糊自动布局算法和模糊聚类分析法，从连接矩阵出发，推出一个适合布局的模糊相似关系，提出了一种灵活的、快速的新布局算法，该算法在工厂布局设计中具有一定普遍性和实用性12。Raoot和Rakshit在1991年的文章中，使用了语言变量定义设备与设备之间的内部关系从而寻找到最佳的设备布局。徐元博在1993年的文章中对机床总体布局进行模糊综合评判探索，也是模糊技术一个很成功的应用。该研究将机床的功能与性能模块化，对精度、生产率、经济性和造型质量等四大因素及其下的21个子因素进行分析，建立三级综合评价数学模型，把权重集和隶属度归一化处理，使模糊计算变为加权求和型13。Gen，Ida和Cheng在1995年解决多行多目标不等面积设备布局时，在考虑设备与设备之间的预留空间时用到了模糊的概念。叶德胜在2007年的文章中通过应用模糊数学中的模糊综合评价和模糊决策理论进行工厂系统布局优化设计14。2.4 多目标布局模型在大多数布局问题中，最通常的布局目标是对整个车间中的物流消耗（Material Flow Cost）最小化，其他的布局目标还包括车间物流路径最短，空间利用率最大化，设备投资最小化，以及设备放置柔性等目标15。在布局方法中采用的布局目标一般不能涵盖所有的布局目标，在实际问题中，目标函数往往并非只有一个。例如，Dweiri和Meier在1996年的文章中同时要求物料流量、信息流量最小。大多数研究人员使用AHP（Analytic Hierarchy Process，AHP层次分析法）的方法将不同目标加以综合最终形成单目标，还可使用其它数学方法将多目标问题转化为单目标问题（Chen和Sha，2005）16。3 车间布局问题的解法车间布局问题的求解方法主要有三种类型：确定性算法、启发式算法和智能算法。确定性算法得到的解非常精确，也称精确算法，但对计算时所需存储器和CPU时间要求较高，因此只适于解决小规模的布局问题；启发式算法和智能算法运算速度较快，适合大规模布局问题。3.1 确定性算法 车间布局问题的算法可分为两类：最优算法和次优算法。早期的布局设计算法的研究主要集中在能够提供最优解的确定性方法上，被采用比较频繁的有非线性规划法、分支定界法以及混合整数规划法。Burkard和Bonninger在1983年提出了求解QAP模型的割平面法17。Ka Ku等在1986年提出了一种分支定界法,对于大规模问题,其求解效果比Lawler 的算法好18。Meller在1999年使用分支定界法法求解了在给定的正方形区域内对n个长方形设备进行布局。由于确定性算法本事存在比较大的缺陷，不适合求解大规模布局问题，学者开始转向对次优算法即启发式算法和智能算法的研究。3.2 启发式算法启发式算法有构造型算法和改进型算法这两类。构造型算法即从开始到结束只构造一个解，就是根据算法步骤将设备分配到位置，通常是每次一台设备，直至获得完整的布局。改进算法，即在设计一个初始布局的基础上，通过一些移动规则，不断改进原有布局，直到获得最优解。构造型布置算法主要有系统布置设计（Systematic Layout Planning，SLP）法和图论法。由于图论方法与SLP法极为相似，因此这里只介绍SLP法。“系统布置设计”的布置方法是Richard Muther 于1961 年提出的，这时一种条理性很强、物流分析与作业单位关系密切程度分析相结合、求得合理布置的技术19。它的基础是作业单位相关图。求解过程为：基于输入数据和对作业单位的职能与相互关系的理解，可作出物流分许（从至表）和作业单位相互关系分析（作业单位相关图）。在这些分析的基础之上得到位置相关图。SLP的程序直接明了，计算简单方便，但是它的求解结果往往并非只有一个，要得到一个较优的布置方案是要靠直觉和经验的。目前解决布局问题运用的最多的就是SLP法，如李诗珍在2006年基于SLP思想研究配送中心布置设计20，马昌谱在2009年基于SLP分析与优化了装配车间生产系统21。改进型布置算法主要有作业单位对两两交换法、CRAFT和MULTIPLE等。作业单位两两交换法适用于部门面积相等的情况，可采用相邻交换和距离交换两种目标函数形式，但一般情况下比较经常使用距离交换。它对每一次迭代考察作业单位对位置所有可能的交换方式，采用“最速下降法”的思想，选取使总成本减少最多的部门单位对，当本次迭代的最小值比上次迭代的最小值还大或者是相差很小时，迭代结束。作业单位两两交换法的最终结果依赖于初始方案，即不同的初始方案得到的结果页不一样，因此，它的结果只能说是局部最优。CRAFT是指计算机化的设施关系分配法，是在1963年由Avmow，Bnffa，Vollman提出的。它可适用于部门面积不等的情况。引入了虚部门使得CRAFT既可用于矩形厂房，也可用于非矩形厂房。CRAFT的特征之一是在交换过程中只考虑相邻部门和等面积部门的交换，更符合实际情况。缺点是高度依赖路径和最终布置方案里部门的形状往往是不规则的。MULTIPLE是由Bozer、Meller和Erlebacher开发提出的。它可适用于部门面积不等的情况。通过采用空间填空曲线（SFC）使得迭代过程中任意两个部门均可进行交换。在实际过程中，经常采用手绘曲线代替SFC。1990年，Falkner和Benhajla介绍了在一间四层大厂房中使用MULTIPLE的情况22。MULTIPLE可获得在给定曲线下的最优解，但是给定的曲线不同，得到的最优解也不同。3.3 智能算法随着算法研究的深入，智能算法作为优化算法中的新概念越来越受到研究者的青睐。目前比较流行的智能算法有模拟退火算法（Simulated Annealing，SA）和遗传算法（Genetic Algorithm,GA）等。遗传算法的思想来源于自然界生物进化“优胜劣汰”、“适者生存”的自然遗传法则，是基于“适者生存”的一种高度并行、随机和自适应的优化算法。遗传算法进行全空间的并行搜索，搜索集中于性能高的部分，提高了搜索的效率，而且该算法具有的并行性使得对种群的遗传处理时可采用大量处理的模式，容易并行实现23。但是它在实践中也暴露了一些问题，典型的如局部搜索能力差、容易产生早熟（即过早收敛）。在1994年，Conway和Venkataraman使用遗传算法解决了Balakrishnan等人所提出的有限制条件的动态设备布局问题。Pierreval在2003年用遗传算法求解了设备布局问题24。印鉴在2002年的文章中提出了一个基于遗传算法求解二维不规则形状物体的自动最优布局问题25。模拟退火算法源于高温固体金属降温时的分子热运动现象，其出发点是物理中固体物质的退火过程和一般组合优化问题的相似性。它引入的物理系统退火过程的自然机理，避免了搜索过程阴陷入局部最优而无法自拔的弊端，提高了得到全局最优解的可靠性。当初始解与最优解相差较大时，那么得到最优解就需要较长的时间。Szykman等在1997年将模拟退火算法和空间约束条件结合起来, 对3 维组件的布局进行求解。这些组件需满足组件之间的最近、最远距离约束及相互位置约束和组件的旋转方向约束。空间约束条件包括组件之间的距离, 坐标轴内整个空间组件的平移和旋转, 以及其它组件的位置和方向26。McKendall在2006年提出了两种模拟退火算法来解决等面积动态设备布局问题。第一种方法是基于配对交换法产生邻域解；第二种方法是在第一种标准的模拟退火方法基础上加入了一个改进策略27。刘刚在2009年的模拟退火算法在车间设备布局中应用一文中给出模拟退火算法在车间布局评价中的具体应用方法， 提出了搬运矩阵的概念。然后，给出了一个具体的应用实例，并对优化结果进行了分析， 得出优化设计结果符合生产实际要求28。目前被使用得越来越多的是将遗传算法与模拟退火算法一起使用的混合智能算法。混合智能算法充分继承了遗传算法全局搜索能力强和模拟退火算法局部搜索能力强的优点，将二者完美结合，使得该算法能较快的得到最优解。寇猛在2006年的工厂设备布置计算机仿真一文中，将模拟退火机制融入到遗传算法的运算流程中，来进一步调整优化种群23。朱唯薇在2008年将混合智能算法的思想用于静态设备布局设计，并通过仿真实验与传统模拟退火算法、传统遗传算法、单亲遗传算法进行比较研究，并且提出了两种针对动态布局问题而设计的混合智能算法，并通过大量仿真实验，验证了算法的性能3。4 结论目前,有关工厂布局问题的研究较多,取得了较显著的成果。主要集中在运用系统布置设计（SLP）、模拟退火算法和遗传算法来解决和改善工厂布局，而对MULTIPLE、单位对两两交换法和CRAFT等改进型布置算法的研究较少。就目前的研究成果而言，对于系统布置设计一般采用手工计算的方式，对于模拟退火算法和遗传算法一般是计算机辅助完成。因此，我们可以尝试用计算机编程的方式实现使用MULTIPLE法解决车间布局问题，以充分发挥MULTIPLE法的优势，减小计算量，优化车间布局。参考文献：1伊俊敏,袁海波译.设施规划M.北京:机械工业出版社,2007.2王家善,吴清一,周佳平. 设施规划与设计M.北京:机械工业出版社,1995.3朱唯薇.基于混合智能算法的设备布局问题研究D.天津：天津大学管理学院,2008.4曹振新,朱云龙,宋崎. 制造系统的设备布局方法J.辽宁工程技术大学学报, 2005, 24: 413-416.5Wang,M.J.,Hu,M.H.,&Ku,M.H.A solution to the unequal area facilities layout problem by genetic algorithmJ.Computers in Industry,2005,56:207-220.6Edwards H K,Gillett B E and Hale M.E.Modular allocation echnique (MAT)J.Management Science,1970,17(3):161-170.7Lewis W P and block T E.On the application of computer aids to plant layout J.International Journal of Production Research,1980,18(1):11-20.8Christopher A P and Wilhelm W E.A perturbation scheme to improve Hilliers solution to the facilities layout problemJ.Management Science,1984,30(10):1238 -1249.9Hillier F S.Quantitative tools for plant layout analysisJ.Journal of Industrial Engineering,1963,14(1):33-40.10Drezner,Z.DISCON.A new method for the layout problemJ.Operations Research,1980, 25(6):1375-1384.11Das,S.K.A facility layout method for flexible manufacturing systemsJ.International Journal of Production Research,1993,31:279-297.12甘骏人.一种以模糊数学为基础的布局方法J.计算机学报,1989,11:840-847.13徐元博.机床总体布局模糊综合评判的探索J.陕西工业学报,1993,12:22-28.14叶德胜.模糊数学在工厂规划中的应用研究D.上海:上海交通大学,2007.15贝炳林.车间布局的综合评价D.上海:上海交通大学,2006.16Chen,C.W.,&Sha,D.Y. Heuristic approach for solving the multi-objective facility layout problemJ.International Journal of Production Research,2005,43:4493-4507.17Burkard R E,Bonnimger T.A heuristic for quadratic Boolean program with applications to quadratic assignment problemsJ.European Journal of Operational Research,1983,13 (4):374-386.18 Ka Ku B K,Thompson G L.An exact algorithm for the general quadratic assignment problemJ.European Journal of Operational Research,1986,23(3):382-390.19王家善.设施规划与设计J.工业工程,1998,1:11-14.20李诗珍,杜文宏.基于SLP思想的配送中心布置设计研究J.广东:科技管理研究,2006,10:246-248.21马昌谱.基于SLP的装配车间生产系统分析与优化J.物