《关于设施布置问题的调查.doc》由会员分享，可在线阅读，更多相关《关于设施布置问题的调查.doc（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关于设施布置问题的调查摘要：布局问题在制造系统中有很多种类型。通常情况下，布局问题关系到工厂内设施的位置（例如，机器，部门）。据知他们极大地影响了系统的性能。这些问题大部分是NP很难解决的问题。许多关于设施布局的研究著作已经出版，已经有文献存在，但是他们不是最新的，或仅限于这些问题某些具体的方面。文献分析中给出了现在研究的很多成果，不仅限于布局设计的具体考虑。我们在总体框架之上分析了目前著作理论和使用的一些标准。像制造系统的特点，静态动态因素，连续离散表达等问题的提出和解决方法，结论部分我们指出几个研究方向。关键词：制造设施，设施布局，材料处理，动态布局的优化方法1、简介厂区内设施的相互关系，
2、通常称为“设施布局问题”，众所周知设施一经布置，在生产过程中将对生产成本、交货时间、生产能力造成很大的影响。良好的设施能促进整体的生产效率的提高并降低50%的总体运营费用（Tompkins et al，1996）。通常用仿真研究来衡量布局的效益和性能（Aleisa & Lin， 2005）。然而，已知的布局问题都很复杂，一般都是NP解决不了的，（Garey & Johnson， 1979）。因此，在过去的几十年里，在这些方面已经进行了大量的研究。一些已经调查公布了这方面的研究方向并分析了不同的趋势。然而这些调查都不是近期的（Hassan，1994；Kusiak & Heragu，1987； L
3、evary & Kalchik，1985），或者集中于布局设计非常具体的方面，如循环布局（Asef-Vaziri & Laporte ，2005），动态问题（Balakrishnan & Cheng， 1998）和设计进化理论（Pierreval， Caux， Paris， & Viguier， 2003）。 Benjaafar， Heragu，and Irani （2002）他们通过预期分析并且建议了研究方向。我们的结论将证明他们的研究命题仍然有效，但其他几个问题也得到提升。在这篇文章中，基于大量的参考文献，我们提出了一项布局问题的调查，首先，在第2节中，我们考虑了布局问题的几种可能的定义。
4、然后，我们提出可以用于分析当前文献的一个一般框架。第3部分说了车间主要功能的区别。第4部分，重点是论述动态规划问题。第5部分系统的阐述了设施布局问题。第6部分，介绍了解决这些问题的方法。虽然这些审查不可能详尽，但是它们都是从很多文献里得出的。2、布局问题的定义设施布局是为生产或服务提供所需的一切的安排。设施是一些能促进工作的的实体，可能是一台机床，工作中心，制造单元，一个机加工车间，一个部门，一个仓库等等（Heragu，1997）。通过研究大量的文献，发现研究者们没有就设施布置问题得到统一的确切的定义。最初研究的都是静态规划问题（相反的动态规划将在第3节专门讨论）。Koopmans and B
5、eckmann（1957）是最新考虑这类问题的人，他们将这类问题定义为一类工业问题，其目标是合理的布置设施设备，以减少它们之间的材料搬运成本。Meller，Narayanan，and Vance （1999）认为设施布置问题在于找到一种措施，将各种非重复的n边行的设施安排在一个特定长方形的场地内以便减少相互距离。Azadivar and Wang （2000）将设施布置问题定义为在许多设施之间测定其相互位置并保证各种配置之间有足够的空间。Lee and Lee（2002）认为设施布局问题在将特定的总空间划分为包括n个不同大小的区域，使各区域之间的材料搬运费用和管理费用减小到最小。Shayan
6、and Chittilappilly（2004）将设施布置定义为一个优化问题，试图通过考虑各设施间的材料搬运和设施的相互作用来处理系统的布局，使系统的设施布置更有效率。在这个领域已经有很多文章发表了，从图2.1我们能清楚的描述布局问题的构成本质特征，首先考虑到在文献中可能出现的不同因素，粗略的用树图表示。实际上因为关注的因素不同研究也不相同：车间的特点（例如：ail制造系统的特异性，设施形状、原材料处理系统和布局演变），什么是问题的根源（例如：问题的制定，目标和约束）和用于解决问题的方法（决议方法）。虽然以后可能会有比树图更好的表示方法，但是它对描述现有的研究工作是有帮助的。因此本文的其余部分
7、也是根据本组织中重要性、代表性的内容确定的。3、车间的特点对布局影响在本文中将会讨论车间的几种不同类型。实际上布局问题的研究取决于制造系统的特点。有几个因素和设计中的问题明确地区分了问题的本质并分别加以解决，特别是：生产种类和数量，材料处理系统选用，不同的部分允许零部件流动的种类和数量，机器可分配的楼层数目，设施形状和物料入口和出口的地点。由于其重要性，下面详细列出这些因素。图 2.13.1、产品种类和数量布局设计一般取决于产品品种和产量。现存的四种组织类型中即固定产品布局，工艺布局，产品布局和蜂窝布局（Dilworth，1996）。对这些关键的组织形似不同的作者有不同的看法。在固定产品布局中
8、，生产中流动的一般是生产设施（机械，工人等），在这种特定的布局类型中，产品不动，它是各种用于制造的资源在运动。这种布局是常见于大尺寸产品的制造行业，如船舶或飞机。工艺布局是将具有类似功能的设施布局在一起（同一类型的资源）。这样的组织适合产品种类繁多的生产。产品布局用于高产量，少品种的生产体系。设施是依据制造过程的连续性来组织的。在蜂窝布局中，机械被编成群组来完成有相似特征的零件，这些群组也要在工厂中有合理的布置位置。因此一些人，例如（Proth， 1992，） 和 （Hamann & Vernadat， 1992）已将所谓的蜂窝布置通常叫蜂窝机械布置。在这里更关心的是每个群组内机械的最合理的安
9、排。3.2设施形状和尺寸像图3.1所示的这两种设施的形状是十分常见的，换句话说一般为规则的长方形（Kim & Kim， 2000）和不规则的图形，一般的多边形至少包括一个270的角（Lee & Kim， 2000）。正像Chwif， Pereira Barretto， and Moscato （1998）所提及的那样一个设施都有一定的尺寸，确定一个固定的长度（Li）和固定的宽度（Wi）。在这样的情况下设施被称为固定的模块。这些作者也认为一个设施也能通过它的面积来固定，它的长宽比：ai=Li/Wi，上限为aiu，下限为ail因此ailaiaiu，Meller et al。 （1999）也引用这样
10、的观点。如果ai=ail=aiu，这就与固定形状的模型一样的了（Chwif et al， 1998）。图 3.13.3原材料处理系统一个材料处理系统保证了材料运送到适当的位置。物料搬运设备有传送机（皮带、滚筒、轮）自动导引小车（AGV），机械人等。（El-Baz， 2004），Tompkins等（1996）认为生产成本的20%50%都是由零件的搬运处理产生的，合理的布置处理设备可以使成本下降10%30%。在安排材料处理系统时，问题在于安排道路沿线的材料处理设施。设计取决于这两个方面的考虑：设施的布置和搬运设备的选择。材料处理设备的种类确定，决定了机械的布局方式（Devise & Pierrev
11、al， 2000； Heragu & Kusiak， 1988）。 Co，Wu， & Reisman （1989）同时指出设施布置也影响了处理设备的选择。同时解决这两个问题存在困难，要根据这两个问题的难度来确定解决的顺序（Hassan， 1994）。根据原材料的搬运方式来确定的主要布置方式有图3.2所示的几种；单排布局，多列布局，循环布局和开放领域的布局（Yang， Peters， & Tu， 2005）。图3.2当设施必须沿着直线布置时采用单列设施布置法，（Djellab & Gourgand， 2001； Ficko， Brezocnick，& Balic，2004； Kim， Kim，&
12、 Bobbie，1996； Kumar， Hadjinicola， & Lin， 1995）。在单列布置中我们可以考虑许多的基本形状，如：直线，半圆，和U形等（Hassan，1994）。循环布局用于处理将m个设施分派到1，2，、，m个位置，在区域内形成一个封闭网络的情况，在网络中物料将沿着一个方向移动（Chaieb， 2002； Cheng & Gen， 1998； Cheng， Gen，& Tosawa， 1996； Nearchou，2006； Potts & hitehead， 2001）。循环布置将物料进出点合并在一起，换句话说就是物料进出循环的场所在同一个地方。这个位置是1和m之间的
13、一个特殊的位置。多行布局涉及几排设施（Hassan， 1994），物料在同一行或不同行之间流动（Chen， Wang， & Chen， 2001； Ficko et al， 2004； Kim et al， 1996）。开放布局中设施布置的位置将不再受单行布置或循环布置那样的限制（Yang et al， 2005）。3.4、多层次布置现在当要在市区兴建厂房是，一般都有土地供应不足，价格昂贵的问题。由于可用的横向空间受到限制，需要研究使用垂直方向上的空间。这样，几个楼层上的设施的位置会相互相关相互联系如图3.3所示。这个图显示零件可以在给定的楼层水平移动（水平流方向），同时也有从一个楼层到另一个
14、楼层的非水平的流动（垂直流方向）。垂直运动的部件需要运输设备:电梯。在这种情况下，我们将设施在楼层间和同一层水平方向上的一系列布局问题称为多层楼房布局问题（Kochhar & Heragu， 1998）。图 3.3Johnson （1982）首次提出了多楼层布局的问题，他处理的是在一个多楼层中明确设施相对位置的问题，后来，其他的研究人员重点研究了从一层到另一层的垂直移动问题（Bozer，Meller，& Erlebacher， 1994； Meller & Bozer，1996， 1997）。电梯的使用常常能反应物料搬运系统的情况， （Lee，Roh，& Jeong， 2005）。电梯的数量和
15、位置是确定的（Lee et al，2005）或者通过优化之后能确定的（Matsuzaki，Takashi，& Yoshimoto，1999）。每个电梯的容量是有限的（Matsuzaki et al，1999），楼层数可能是已知的（Lee et al，2005），或者可以根据每层中设施的尺寸和数量来确定（Patsiatzis & Papageorgiou，2002）。3.5、回流和旁路回流和旁路（如图3.4所示）是两个可能发生在流水线布置中的两个特别的物流，它将影响产品的流动。回流是物流的一部分，是产品从一个设施流回到流水线上安排在这一设施之前的某个设施（Braglia，1996； Kouvel
16、is & Chiang， 1992； Zhou，1998），这种流动的数量要尽可能的少。Zhou（1998）把这个问题叫做生产线形成问题（PLFP），它要考虑机械的顺序（部分或全部）也使得回流的总重量最小，同时需要考虑机械本身的限制。图 3.4旁路发生在当零件需要绕过某些流水线上的设施向前流动时（Chen et al， 2001）。Hassan （1994）注意到当前在处理回流最小问题时已经有很多的方式了，但是在现有文献中针对解决旁路问题的建议几乎没有。3.6、进出点物料进出设施的位置常常是需要确定的，叫做Pick-up和Drop-off（P/D）点。尽管他们有可能在不同的地方（Kim & K
17、im，2000），一些研究人员还是将他们可能的位子确定也减小问题的复杂性（Das，1993；Rajasekharan， Peters， & Yang， 1998；Welgama & Gibson，1993），图3.5就是这样的一个例子。图 3.54、静态与动态布局问题在车间特点介绍中我们已经提到了不同的设计布置的差异。此外，众所周知的，现在制造工厂必须能快速的响应产品数量和结构的改变需求。Page（1991）指出，平均而言，公司40%的销售额是来自新产品。然而，改变产出产品的结构会改变生产流程，从而影响生产设施的布局。Gupta and Seifoddini（1990）指出，1/3 的美国公司
18、生产设施每2年就要进行一次重大的改组。许多好的作者在设计布局时已经尝试着考虑这一系列的重要的问题了。大多数文献在考虑布局问题时，通常都是当静态问题来考虑，换句话说他们认为在相当长的一段时间内车间里的关键数据和生产计划将保持不变。最近动态布局问题的思路已经被一些研究者多次提及，它需要考虑物料在多期处理流程中可能出现的变化（Balakrishnan， Cheng，Conway，& Lau， 2003； Braglia， Zanoni， & Zavanella， 2003； Kouvelis， Kurawarwala，& Gutierrez，1992；Meng，Heragu，& Zijm，2004）
19、。在这方面，规划期一般可能是几周，几个月或几年，在每一个时期内，估计流量数据保持不变，一个动态布局计划包括一系列的布局，每一个布局对应一个时间周期。图4.1显示在一个规划期的不同时期，六个等面积设施的不同安排。图 4.1目的是在规划期的每个周期确定一种布局，使原材料的处理费用总和最小，并重排时期间的成本 （Balakrishnan，Cheng，Conway，et al， 2003；Baykasoglu， Dereli，& Sabuncu， 2006）；重排成本时必须考虑到设施从一个位置移动到另一个的情形（Baykasoglu & Gindy，2001）。5、规划布局问题提出车间的特点和静态或动
20、态规划后，需要许多的关于布局的数学的公式，以至于能解决这些问题。有关静态和动态问题的公式可以基于多种类型的模型得出，它允许在一个布局中将不同问题不同因素之间的复杂关系表达出来。这种模型可以采用不同的原则，其中包括图论（Kim & Kim，1995； Leung， 1992； Proth， 1992）或者神经网络（Tsuchiya，Bharitkar， & Takefuji， 1996）；大多数研究人员认为，这些模型通常是提出和解决单个或者多个目标布局问题的优化方法。根据一些连续的或离散的数学方法我们能得出解决问题的公式，在现在的研究中常见的是二次分配法或者混合整数规划法。一些作者认为，在任何的
21、情况下可利用的数据都不可能是完全的，需要一些模糊的规划，这些方法将在下面讨论。5.1离散型规划布局有时候被认为是离散，像图8a所示。在这种情况下相关的优化问题有时是作为二次分配问题来解决的。厂区被分为等面积相同形状的矩形块，每一个矩形块可以放置一个设施（Fruggiero， Lambiase， & Negri， 2006）。如果设施面积不相同，他们可以占据不同的矩形块（Wang Hu， & Ku， 2005） 。图8这是个典型的问题，在设施相对位置确定的条件下尽量的减小物料处理的总成本（Balakrishnan，Cheng，& Wong，2003），方法如下:这里N是布局中设施的数量，fik是
22、从设施i到k的物流成本，djl是位置j到l的距离，Xij为设施i在位置j中的影响因素变量，在0，1之间取值。目标函数（1）表示每对设施之间物流成本的总和，公式（2）约束每个位置只有一个设施，公式（3）约束一个设施只放置在一个位置。例如，Kouvelis and Chiang（1992）and Braglia （1996）通过对离散布局的研究建议尽量减少零部件在单列布局中的回流。Afentakis（1989）也使用同类型的方法设计了一个循环布局，以最大限度的减小交通拥堵，既在所有的操作完成之前，零部件沿着这个循环移动的次数最小。在循环布局设计中针对交通拥堵的问题常有两种措施：Min-Sum 和
23、Min-Max。Min-Sum问题是尝试使所有零部件的共同拥堵最小，而 Min-Max问题则是尝试使每个设施之间的最大零件流拥堵最小（Cheng & Gen，1998；Cheng et al，1996；Nearchou，2006）。离散型布局通常于用于动态布局问题。论及的问题与相等大小的设施有关（Baykasoglu & Gindy，2001； Lacksonen & Enscore，1993），必须保证每一时期每一位置上只有一个设施，和每个设施在每个阶段只被分配在一个位置上（Baykasoglu & Gindy，2001；McKendall，Shang，& Kuppusamy， 2006），
24、预算约束可能增加单层工厂设施的重新配置（Balakrishnan， Robert Jacobs， & Venkataramanan，1992； Baykasoglu et al，2006）。，事实上，重组费用必须控制在预算的一定水平内。离散型布置不适合用来表示设施在厂区有确定位置的布置，也不能正确的模拟有特定约束的模型，像定位的设施，物料进出口，两个设施之间的空隙等。在这种情况下，许多研究人员认为用连续规划来表示会更加适合（Das，1993； Dunker，Radonsb，& Westkampera，2005；Lacksonen，1997）。5.2连续规划在许多文献中，设施规划表示都是连续的（
25、如图8b所示）。常用的方法是混合整数规划（Das， 1993），它要求所有设施都放在平面内，相互之间不允许重叠（Das， 1993； Dunker et al， 2005； Meller et al， 1999）。厂区的所有设施都根据其中心坐标（xi，yi）来确定其位置。半长li和半宽wi或者在的坐标系中设设施的长Li，宽Wi。这样就可以表示两个设施之间的距离了，例如标准直线表示（Chwif et al 1998）；在设施规划问题中物料入口和出口会对规划产生约束（Kim & Kim， 2000； Welgama & Gibson， 1993； Yang et al， 2005），在这种情况下，
26、零部件从设施i进入到设施j出来，所移动的距离就能够表示出来，由公式（5）给出（Kim & Kim， 2000）：这里（xio，yio）设施i的物料出口坐标，（xjI，yjI）为设施j的物料入口坐标。Chittratanawat，Noble（1999），Kim and Kim（1999），Aiello， Enea，和Galante （2002）认为确定P/D站点的位置是个特别的问题。显然厂区存在面积约束，要求厂区的总面积大于或者等于所有设施面积的总和，在分配每个机械的面积时必须考虑到操作这个机械所需要的其他资源的空间或者缓存区（Lacksonen，1997），两个设施之间的的空隙可以包括在设施的
27、占地面积内，也可以不包括在内（Braglia， 1996； Heragu & Kusiak， 1988， 1991）。另外一个很重要的制约因素是设施不能重叠。Welgama and Gibson （1993）给出了设施不重叠的两个条件：X方向的投影不重叠，Y方向的投影不重叠：其中（xit， yit）和（xib， yib）分别表示设施i和j左上角和右下角的坐标。Mir and Imam （2001）定义了Aij表示两个设施重叠的约束，布局的优化表示如下：当Aij0时 （8）最小化目标函数（Li，Wi）表示设施i的长和宽，（xi，yi）是设施i的坐标。在布局规划中还要考虑其他的约束，如某些提前定位
28、好的设施（Dunker et al。， 2005），给出这些约束之后，一个典型的优化问题如下表示：其中N表示设施的个数，fij表示物料从i设施的入口到j设施的出口的物流成本，（xio，yio）表示i设施的物料入口坐标，（xjI，yjI）表示j设施物料出口的坐标。用连续函数来表达动态设施布局的研究几乎没有。Dunker 等（2005）在动态环境中处理了设施大小不相同的问题，并且假设不同时期设施的大小是不一样的。5。3模糊规划在多数情况下，影响设施布局的数据不是完全清楚的。一些随机的方法，如排队论（Meng et al。 2004），是很少被使用的。而这样的问题又是经常遇上的，因此模糊理论被提出来
29、用于以解决数据不完整的或者具有不确定性的问题（Evans， Wilhlem， & Karwowsky， 1987； Grobelny， 1987a； Raoot & Rakshit， 1991），在设计布局中也已存在基于模糊理论的几种方法。Evans （1987） 等人讨论了在厂区内布置不等面积设施的问题，他们应用模糊理论来描述每一对设施之间密切的重要的关系。这些关系允许分析者确切说明被放置在任何地方，相互距离任意的一对设施的重要的联系，作者通过语言变量得出了一个关于这个问题的模糊规划并从中的到启发。Grobelny （1987a，1987b）提出了将n个设施分派到n个不同位置以使总的物流成本
30、最小的问题。数据会对布局的模糊语言变量模型和模糊推断产生影响，如联系密切度和交通强度。在可用空间内选择设施放置位置的过程中，一种基于二元模糊关系的启发式算发发展起来。这种方法的几个原则也被Raoot and Rakshit （1991）使用，他们用其来研究这样的问题，当设施的相互关系已经通过语言变量详细说明时，找出这些设施在厂区的最优布置。Gen， Ida， and Cheng （1995）讨论了不同面积多行多目标布局问题，他们研究的是由于间隙不能确定而被当做模糊问题来考虑的设施布置问题。在离散布局问题中，当大多数的零部件和大部分的信息都在设施之间循环流动，而其大部分的搬运设备被用来在设施之间
31、搬运零部件时，Dweiri and Meier （1996）将这些因素当做模糊因素来考虑。作者根据专家的判断得出了一个活动关系图（ARC），用它来详细的说明一对设施之间的关系。ACR是当时著名的集成CORELAP方法，用来找到设施的最佳位置。Aiello and Enea （2001）认为产品的市场需求是不确切的数据，可以当做模糊数来对待，当每部分都达到极限约束产能，其物料沿着单排设施流动时，总的物流成本是最低的。为了解决单排设施布局问题，他们用切分法切分了模糊需求，并给出了各种布局在水平下和成本。Deb and Bhattacharyya （2005）研究了在连续布局中物料进出点的位置设置，
32、以尽量减小物流的总费用。各项设施的位置取决于这些因素：人流，管理关系，环境关系和信息流，他们都有规定的言语变量（例如，高，中，低）。作者基于模糊 IFTHEN 规则，开发了一个模糊决策支持系统，可以使用它来确定设施在厂区的布置位置。5。4、多目标布局问题在有关布局的大多数文献中，主要目标都是使相关的物流目标函数值最小（总物流成本，物流时间，物流距离等）。为了更切合实际，一些研究人员认为多目标比单一目标更好。例如，Dweiri and Meier（1996）就提出以同时减小材料的处理流程，设备流和信息流为目的。大多数的作者通过层次分析法（Harmonosky & Tothero，1992；Yan
33、g & Kuo，2003）或者不同目标线性组合（Chen & Sha ，2005）将多个目标整合成单一目标。几乎没有人使用帕洛托法来生成一个一般解决办法。Aiello， Enea， and Galante（2006）讨论了最大距离（评估两个相连部门之间的需求）最小物流费用的问题，他们使用著名的Electre方法从一般解中找出一个最优解。55、不同问题同步解决这是很常见的，其他的问题必须和设施布置同时解决。例如，在布置单元制造系统时就会发生这样的情况，在单元制造系统中将两个机械的一个分派到单元中（单元形成问题），并确定每个机械在单元中的位置（单元内部布局），每个单元在车间的位置也有待确定。相比一
34、般顺次解决问题的方法，有时可以将这两个问题当作一个问题同时处理（Gupta， Gupta， Kumar， & Sundaram ， 1996）。6、决策评价方法在文献中有许多方法用了解决规划中的各种问题。他们的目标是找到一种好的解决方案，也满足决策者确定的条件，或者找到一个全局的或者区域性的最佳解决方案也满足给定的一个或多个性能指标，下面我们将介绍一些以产量为基础的优化算法。为了解决布局问题，可以尝试一下人工智能的方法。例如，庄家系统的提出（Heragu & Kusiak， 1990），Hamann and Vernadat （1992）也把这个方法用于单元内部布局。最近，在制造系统的设施规划
35、建设中居于人工神经网络的方法已经被应用了（Chung， 1999）。在文献中几种类型的优化方法已经被提出，下面我们将介绍一些确定的方法：分支定界法，近似算法，现代启发式算法。61、精确算法Kouvelis and Kim （1992）在大部分文献中提及了一种精确算法，单向循环布局问题的分支定界算法。Meller 等（1999）以使用这个方法解决将n个方形的设施放置在一个方形的可用面积内，他们依据非循环结构得出了一类不等式，以增加可解问题的范围，它也在分支定界法中使用。Kim and Kim （1999）研究了在一个设施面积固定的给定布局中寻找到P/D点的位置的问题，这个问题的目标是尽量减少P/
36、D两点之间总的物流量。为了找到每个设施P/D点的最佳位置作者提出了一个分支定界算法。Rosenblatt （1986）用动态规划方法来解决设施面积相等的动态布局问题。然而只有一些小的问题已经有了解决的优化实例（六个设施五个时段）。62、近似算法由于精确的方法是经常被发现并非适合大尺寸的问题，所以许多研究人员开发了现代启发式算法。建筑项目是建造完成一序列的设施，而改善从第一个方案开始，直到得到新的方案。启发式算法包括：CORELAP （Lee & Moore， 1967）， ALDEP （Seehof & Evans， 1967） ， COFAD （Tompkins & Reed， 1976），
37、 和SHAPE （Hassan， Hogg， & Smith， 1986）。启发式算法的改善范例：CRAFT （Armour&Buffa， 1963），FRAT （Khalil， 1973）和 DISCON （Drezner， 1987）。这里有几种基于启发式算法的方法，全局搜索的方法（禁忌算法和模拟退火算法）和演变算法（遗传和蚁群算法）。为了解决设备布置问题Chiang and Kouvelis （1996）提出了禁忌算法。他们将邻近的两个位置里的设施交换，包括一个长期的结构记忆，动态的禁忌列表，一个节约化的准则和多样化的战略。Chwif 等（1998）利用模拟退火算法来解决有尺寸高宽比的布
38、局问题。两个相近的程序被提了出来：一个是交换一对设施的位置，另一个是在布局平面内的四个主要方向（向上，向下，向左和向右）上随机的移动。McKendall 等 （2006）提出了两种退火的模拟算法来处理等面积的设施布置问题。第一种模拟算法是根据下降成对交换的方法随机的改变两个被优化设施的位置；第二种方法将第一个算法和改进策略相结合，称为前瞻和回顾式战略。遗传算法似乎变得很常用在解决设施布局问题方面（Pierreval et al， 2003），事实上使用这种方法已经有大量的研究成果发表：Banerjee and Zhou （1995）， Mak， Wong， & Chan （1998）， Tam
39、 and Chan （1998）， Azadivar and Wang （2000）， Wu and Appleton （2002）， Dunker， Radonsb， & Westka mpera （2003）， and Wang et al（2005）的静态布局问题，Balakrishnan and Cheng （2000）， Balakrishnan， Cheng， Conway， et al （2003）， and Dunker et al（2005）的动态布局问题。一个非常重要的问题是，在遗传算法使用时与候选方案的的平面编码图是关联的。一个极具代表性的连续性布局是分层树（Shayan
40、 & Chittilappilly， 2004），它由代表布置平面图分区的内部节点和代表设施的外部节点组成。每一个内部节点都可能被标记为h（水平）或者n（垂直），说明它是水平的还是竖直的部分而外部节点则标记为设施的编码（1，2，3，n代表n个设施）。每一个矩形分区的空间内都分配有对应的设施。图6.1给出了一个特定的布局和相应的分层树。Wu 和 Appleton （2002）提出了一种分层树来同时代表布局和过道并且适应调整遗传算子。图 6.1从一个给定的布局，分层树一般编码为一个字符串，才能使用特定的遗传算子。Tam （1992）提出编码由两部分二进制数字组成，一部分代表操作者，后面又分为三部分
41、：树结构，管理者和操作者。（Tam & Chan， 1998） Al-Hakim （2000）改进了Tam Chans的方法（1998）并提出了一个新的运算方法叫transplanting以确保结果的一致性。Shayan and Chittilappilly （2004）认为当用分层树时要避免被一般程序干扰。处理离散型布局问题时，编码方案不同于连续问题的表述。对于离散型问题，一种流行的布局编码是基于空间填充曲线（SFC）（Wang et al。， 2005）的方法。厂区内被划分成网格，空间填充曲线顺次地通过基本布局中的所有相连的方格（图10），空间填充曲线确保设施不被分裂（Bock & Hob
42、erg， 2007）。不过，这种技术需要许多规则验证所有设施的连续性，例如使用专家规则（Wang等， 2005）。定义一个空间填充方案时，解决方案必须进行编码。Islier （1998）将字符串分成三部分，分别表示设施系列编码，每个设施所需的范围和过道的宽度。最近，Wang 等人（2005）使用了五字段字符串染色体基因编码法。第一部分表示加工部门的顺序；第二个部分给出每个部门所需区域的面积；第三部分表示场地的大小（长和宽）；第四部分表示展开方向（1：水平，2：垂直）；第五部分表示扩展带。图6.2显示了一个实例。图 6.2在进化过程中目标函数被看成是一般的数学成本函数，它是从需要考虑的问题中派生
43、出来的。考虑到系统的性能，要采用更加现实的方式，连续仿真模型通常被用来评价候选解决方案（Azadivar & Wang， 2000）。Hamamoto， Yih，和 Salvendy （1999）研究了制药行业的实际问题，他们应用染色体评价法评价了一个周期为四个月的生产模型。蚁群算法已经被用来解决设施规划问题，Solimanpur，Vrat，and Shankar （2005）针对单列设施布置开发了一系列的蚁群算法。Baykasoglu等（2006）也提出了一种蚁群算法用于解决预算有跌宕的动态规划问题。混合的万用启发式算法也被考虑用来解决设施布置问题。Mahdi， Amet and Portm
44、an （1998）提出了处理最小物流成本的混合计算方法。他们应用退火算法来解决布置几何方面的问题，用遗传算法来制定物料处理系统，在用精确算法（Hitchcocks method）使得总的物料处理费用最小化。Mir and Imam （2001）提出了一个用于处理设施面积不相等问题的混合公式。开始由模拟退火算法给出初步的解决方案，设施的最佳位置再由一个多阶段的优化过程分析搜索技术得到。Lee and Lee （2002）针对固定形状不等面积的设施布局问题，提出了一个混合遗传算法。禁忌搜索和模拟退火首先用来寻找整体的解决方案，在寻找整体解决方案的中间过程中引见了遗传算法。Balakrishnan，
45、 Cheng， Conway，等 （2003） 开发了一种混合遗传算法来解决以前由Rosenblatt （1986）提出的动态布局问题。在蚁群算法中初始种群产生有两种方法，一种是随机抽样的方法，另一种是Urban程序法（Urban， 1993）。McKendall and Shang （2006）提出和比较了三种用于动态设施布局问题的混合蚁群算法。他们将蚁群算法和三种本地搜索方式集合：（1）随机向下成对交换程序；（2）模拟退火算法；（3）look-ahead/look-back 程序。7、结论和研究方向这篇文章中我们对近年来相关设施规划的研究做了一个全面的调查。虽然我们以分析大量的参考文献为基
46、础，但还是不能做到面面俱到。从这个分析中可以看出，有大量的与设施布局相关的文献在一些主要的研究期刊上发表，和设施布置问题依然是一个开放的研究课题。首先，从最近的资料来看，被研究的制造系统的特点越来越复杂和（或）接近现实情况。典型的例子是综合考虑了P/D转换点，过道，复杂几何约束，多个楼层等因素的规划设计问题。这的确是一个重要问题，因为许多文章中包括假定的约束条件，它不适用于现实中的很多制造系统。这是个传统的趋势（Benjaafar 等， 2002），可是，仍然需要不断的研究。在设计一个规划是考虑第三个维度是最近才有的，当然需要更多的研究，例如选择和优化零部件在垂直方向上运输与平面的联系。静态方
47、法的不现实，似乎被研究人员充分的认识了，因为静态方法考虑的数据是用来表征系统未来的经营特征的。动态的方法有时可能成为一个潜在的选择；同时，他们常常依靠于对未来经营情况的了解。模糊方法可以提供一些有意思的可能性，包括不确定性。然而正如Benjaafar 等 （2002）指出的那样，改进设计方法和提出合理的建议需要不断的研究做为支持，体现在下面三个方面：（1）健全布局；（2）布局灵敏度分析；（3）评估方案时随机模型的应用。在解决设施布局问题的方法方面，很明显，为了应付较大规模的问题，考虑到现实条件的限制，启发式算法越来越多的被使用。同时进化算法似乎也是最常用的方法之一。各种解决方法的复合，可以用来
48、解决复杂的问题，或者提供更加现实的解决方案。鉴于这样一个事实，为了解决一个问题而使用系统内很多专家的知识是有困难的，在综合考虑了专家给出的建议之后，设施仍然有可能需要优化，所以人工智能的方法现在很少出现。我们注意到，大部分已经发表的文献中，都将确定设施的位置作为焦点问题。然而在实践中通常需要将这个问题和其他问题综合考虑，例如制造类型的选择，运输资源的选择，单元设计，容器的选择等。这些问题往往不是独立的（例如，选择输送机和选择自动导引小车不会是相同的约束）。因此需要继续研究以解决不同的问题，包括在车间设计是用同时设计代替分时区设计。这样的合并在开始的时候认为已经被解决了，现在看来它是有希望的，值得去开发改进的。这将会导致更多的支持车间的整体研究，而不是只考虑设施布局问题。本文研究的这些文章的焦点是制造系统。然而，布局设计的问题在其他类型的系统中也有涉及，如港口，超市，机场等。他们可能得益于制造业的某个特别领域的进步。最后，让我们主要到，在全球商业软件市场上，辅助制造系统设计的工具软件是有限的。然而，尝试使解决方法更加通用化有可能是一个潜在的需求，以至于这些方法能嵌入到布局的程序中，用工具软件来支持制造系统的设计。用图形化工具的组合方法，以使这些工具更有效和更有吸引力，有一些作者已经在开始考虑仿真系统的可能界面了。第 19 页 共 19 页