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

专业文献综述题目:车间布局问题综述姓名:施景娥学院:工学院专业:工业工程班级:工业工程62班学号:3116220指导教师:熊燕华职称:讲师2009年11月22日南京农业大学教务处制１车间布局问题综述工业工程专业施景娥指导教师熊燕华摘要：本文概述了车间布局的相关概念，强调了研究车间布局的重大意义。在分析了前人的相应的车间布局模型，主要包括离散模型、连续模型、模糊模型和多目标布局模型等问题模型的基础上，详细阐述了SLP、单位对两两交换法、CRAFT、MULTIPLE、模拟退火算法和遗传算法等各类车间布局问题解法的概念，并分析了其优缺点。关键词：车间布局；系统布置设计；MULTIPLE；遗传算法；模拟退火算法AReviewofWorkshopLayoutProblemStudentmajoringinIndustrialEngineeringJingEShiTutorYanhuaXiongABSTRACT:Thisthesissummarizestherelatedconceptsofthefacilitieslayoutandstressesthegreatsignificanceoftheresearchofworkshoplayout.Onthebasisofanalysestherelevantmodelsoftheworkshoplayoutbyourpredecessorslikedispersedmodel,continuousmodel,mistymodelandmultipletargetmodel,thethesisexpatiatestheconceptionandassessestheadvantagesandthedisadvantagesofthesolutionsofworkshoplayoutproblem,suchasSystematicLayoutPlanning,CRAFT,MULTIPLE,SimulatedAnnealing,GeneticAlgorithm.KEYWORDS:WorkshopLayout；SLP；MULTIPLE；GeneticAlgorithm；SimulatedAnnealing1引言近年来，随着生产技术和设备的快速发展，只有少数公司能够在基本维持其市场地位不变的情况下保留它们的老设施和布置方案。为提高生产率，只要新技术确实可行，就要尽快采用。新技术的使用必将使得生产工艺和设备的改变，而这种改变所带来的整体系统不协调问题只能通过重新进行布局设计才能实现。制造设施中20%—50%的总运营成本是物料搬运成本，而且一般认为有效的布局设计可以将这些成本降低到10%—30%[1]。布局的含义较为广泛,可依序分为设施布局、工厂布局、车间布局和设备布局。设施布局是指企业根据经营目标和生产纲领,在确定的空间内,从原材料的接收、零件和产品的制造直到成品的包装、发运的全过程,将人员、设备、物料所需空间做适当、有效地分配与组合,以获得最大的生产经济效益,工厂布局为设施布局的一部分,包括工厂总体布局和车间布局;车间布局主要解决各生产工部、工段、服务辅助部门、储存设施等作业单位和工作地、设备、通道、管线之间的相互位置,以及物料搬运的流程和方式[2]。设备布局是指在一定的生产环境下,制造系统设计人员根据生产目标确定制造系统中各设备的布置形式和位置。本文主要研究车间布局。本文所研究的制造业生产系统的车间布局问题是我国实际生产中的现实问题，也是很多国有大型制造业企业亟待解决的难题。设计一个优良的设备布局可以给我们的企业带来诸多好处：优良的车间布局不仅可以减少生产系统中的物料搬运费用，从而降低企业的总体运营成本，还能加快物料处理效率，减少在制品的停留时间和数量，提高企业生产效率，使企业对市场需求做出及时地响应，增强企业的市场竞争能力。所以，探讨研究制造系统的车间布局问题具有很重要的理论意义和实际应用价值。本文分析了离散模型、连续模型、模糊模型和多目标布局模型等车间布局的问题模型，探讨并总结了三种解法类型即确定性算法、启发式算法和智能算法的各具体算法和其优缺点，为进一步研究车间布局问题奠定了良好的基础。2车间布局的问题模型对于车间布局问题，根据影响生产的要素和问题的类型（静态布局、动态布局），可以设计不同的数学模型来表达并求解。车间布局问题模型的设计主要以图论、神经网络、２单目标和多目标规划等数学理论作为基础。设备布局模型主要有：离散模型、连续模型，在某些数据不确定的情况下，还可建立模糊模型[3]。2.1离散模型有些车间的布局是离散的，最常见的离散模型是QAP（QuadraticAssignmentProblem，QAP，二次分配）模型。QAP模型的目标函数为：111111min,(..1,1,1,2,...,,{0,1},,{1,2,...,})nnnnnnkijjlijklijijijijkljifcxxstxxinxijn其中ijf表示设备i和j之间的物流量，kjlc是布局在排列k时单位由地点j到的运输成本[4]。将工厂的区域划分为大小相等的长方形块，每个车间由不同的块组合而成[5]，如图1-1所示。优化目标是找到一个布局方案使物流总费用Cost(A)最小。Edwards等[6]，Lewis和Block[7]（点位描述），Christopher和Wilhelm[8]，Hillier[9]（等面积描述），Drezner[10]（圆形描述）等人所提出的算法均属此类。图1-1离散模型2.2连续模型一些文献涉及的实际问题要求布局是连续的，如图1-2所示。通常可以用MIP（MixedIntegerProgramming，MIP混合整数规划）（Das，1993）[11]来表达。MIP模型的目标函数为：min()mmmmmmfdxdxdydy，其中fm为设备i和j之间的流量，mdx，mdy分别为设备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多目标布局模型在大多数布局问题中，最通常的布局目标是对整个车间中的物流消耗（MaterialFlowCost）最小化，其他的布局目标还包括车间物流路径最短，空间利用率最大化，设备投资最小化，以及设备放置柔性等目标[15]。在布局方法中采用的布局目标一般不能涵盖所有的布局目标，在实际问题中，目标函数往往并非只有一个。例如，Dweiri和Meier在1996年的文章中同时要求物料流量、信息流量最小。大多数研究人员使用AHP（AnalyticHierarchyProcess，AHP层次分析法）的方法将不同目标加以综合最终形成单目标，还可使用其它数学方法将多目标问题转化为单目标问题（Chen和Sha，2005）[16]。3车间布局问题的解法车间布局问题的求解方法主要有三种类型：确定性算法、启发式算法和智能算法。确定性算法得到的解非常精确，也称精确算法，但对计算时所需存储器和CPU时间要求较高，因此只适于解决小规模的布局问题；启发式算法和智能算法运算速度较快，适合大规模布局问题。3.1确定性算法车间布局问题的算法可分为两类：最优算法和次优算法。早期的布局设计算法的研究主要集中在能够提供最优解的确定性方法上，被采用比较频繁的有非线性规划法、分支定界法以及混合整数规划法。Burkard和Bonninger在1983年提出了求解QAP模型的割平面法[17]。KaKu等在1986年提出了一种分支定界法,对于大规模问题,其求解效果比Lawler的算法好[18]。Meller在1999年使用分支定界法法求解了在给定的正方形区域内对n个长方形设备进行布局。由于确定性算法本事存在比较大的缺陷，不适合求解大规模布局问题，学者开始转向对次优算法即启发式算法和智能算法的研究。3.2启发式算法启发式算法有构造型算法和改进型算法这两类。构造型算法即从开始到结束只构造一个解，就是根据算法步骤将设备分配到位置，通常是每次一台设备，直至获得完整的布局。改进算法，即在设计一个初始布局的基础上，通过一些移动规则，不断改进原有布局，直到获得最优解。构造型布置算法主要有系统布置设计（SystematicLayoutPlanning，SLP）法和图论法。由于图论方法与SLP法极为相似，因此这里只介绍SLP法。“系统布置设计”的布置方法是RichardMuther于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