【文档说明】计算机辅助设施布置课件.ppt，共(82)页，2.426 MB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-77364.html

以下为本文档部分文字说明：

计算机辅助设施布置布置规划工作的很大一部分内容是对已有布置设计的细小改变，例如确定新机器的放置位置、工厂的部分改造、物料搬运作业研究等。完成新生产线或新工厂的规划是很重要的工作，除非是因为战争和大规模的扩展，一般情况下布置规划人员很少有机会考虑这么大的问题。布置的定量分析图表法设

施布置技术计算机辅助设施布置基于部门的“密切程度”等级或者“物流强度”来确定部门间相对位置提出模型和算法，可以帮助布置分析人员开发或改进布置，同时提供目标判据，以简化对该过程中出现的不同布置方案的选择。Apple的工厂布置方法1、获取基本数据；2、分

析基本数据；3、设计生产工艺；4、规划物料流动模式；5、考虑通用的物料搬运规划；6、计算设备需求；7、规划各个工作站；8、选择特定的物料搬运设备；9、协调相关作业组别（Coordinategroupsofrelatedoperations）；10、设计作业单位相互关系图；

11、确定存储需求；12、规划服务和辅助作业单位；13、确定空间需求；14、给各个作业单位分配面积；15、考虑建筑类型16、构造总体布置方案；17、与相关人员一起评价、调查和检查布置方案；18、获得批准；19、正式批准布置方案20、实施布置不管是从设计过程还是内容说，

没有两个布置设计项目是完全相同的。在完成一个初始布置方案前，一般会跳过上面的一些步骤，但是因为开发设计时很多事情是不可预见的，所以以后会重新回到前面的步骤，进行检查或者重做。计算机辅助设施布置－研究对象设施位

置问题——厂址选择设施布置问题——厂区规划设施位置问题位置问题——厂址选择：新建一家工厂时，如何在有限的数个可选地点选择一个最佳厂址，其目标往往是原材料和产品运输费、建设费用以及生产费用最小。求解方法：

运输问题解法重心法最优化解法（图论）等。设施布置问题最优算法（最优化理论）次优算法穷举法面向新建型系统布置程序面向改进型系统布置程序算法分类按照需要的数据类型从至表的定量物流数据相关表之类的定性数据同时接

受相关表和从至表按照目标函数分类使得流量与距离乘积的和最小—基于距离目标使得相邻值最大—基于相近程度11minmmijijijijzfcd11maxmmijijijzfx111110mmijijijmmijijijijfxZfijxx

归一化的相邻值如果部门和相邻，则，否则(,)(,)(,)(,)(1)mmijijijijijFijFmmijijijFijFijfxfxXfZff如果有等级，则可能为负值移动单位物料的单位距离成本算法分类按照布置方式划分离散型表现方式，每个部门

的面积四舍五入到最近的整格子数连续型表现方式，不采用格子结构设施布置问题－最优算法二次分配问题模型（QAP,QuadraticAssignmentproblem）如果新设施之间没有相关性，只考虑与现存设施的位置关系—线性分配；如果新设施之间存在互相联系时，称

为二次分派问题。二次分配问题是如何布置m个设备给n个地点，使得布置方案的物料搬运费最小。目标函数：一般以物料搬运费用最低。单行机床布局问题数学模型举例：设一生产线为单行布局，共有n台机床，设机床分别为ti，i＝1

，2，…n。ti布局位置坐标为xi，沿布局方向上的长度尺寸为li。在一个生产周期内，工件在机床ti与tj之间的往返搬运次数为fij，单位距离搬运费用为Cij，且机床ti和之tj间的最小间距为dij，如图所示。xjlixiljdij单行机床布局问题

数学模型目标函数：一般以物料搬运费用最低。||min111jininijijijxxfcZ约束条件为：机床互不干涉，即1）|xi－xj|≥dij＋（li＋lj）/22）xi≥0，i＝1，2，…n多行机床布局问题数学模型举例：设一生产线为多行布局，共有m台机床，可

以布置区域有n个地点。),...,2,1,...,2,1...(01),...,2,1...(1),...,2,1...(1min111111njmixmixnjxxxfcZijnjijmiijklij

mknlikjlminj；或第i个设施分配到第j个场址中，它们与在第l场址上的第k个新设施有互相联系Cjl：第j场址与l场址之间单位搬运费用fik：设施i与k之间的物流强度设施布置问题－次优算法穷举法面向新建型系统布置程序图论法CO

RELAP，计算机辅助相关布置规划（将SLP运用到计算机上实现，得到一个使各设施间接近度最大的布置方案）ALDEP，自动化布置设计（在给定系统边界内产生许多可行布置方案，并给出各方案的评价）面向改进型系统布置程序CR

AFT，计算机辅助设施相对定位技术（在原有布置方案上求得改进布置，得到一个以降低系统物流搬运成本的布置方案）COFAD，计算机辅助设施设计（是对CRAFT的改进，考虑了搬运设备及其成本评价，得到更全面的设计方案，针对不同的物流系统，COFAD有COFADII和COF

ADIII等）设施布置问题－穷举法次优算法－穷举法又称枚举法，适于在给定设施布置地点组的场合。步骤：列出所有布置方案，通过比较布置方案目标函数值的大小，找出其中的一个或几个最优布置方案。穷举法举例举例：等面积设备布置问

题。如图有A、B、C、D四个地点，分别用P1,P2,P3,P4，表示，在四个地点布置四台机床，分别用t1,t2,t3,t4表示。假设四台机床的占地面积相等，可以布置在任一地点上。ABCDABCD加工工艺从至表0123P41012P32101P23210P1P4P3P2P1从至地点对之间的物

料搬运距离07010100P47003020P31030050P210020500P1P4P3P2P1从至地点对之间的物料搬运量穷举法的计算过程列出所有24个布置方案：例如，排列t1,t2,t3,t4搬运成本为510t1t2t3

t4111432CCC穷举法的计算过程t2t1t4t3列出所有24个布置方案例如，排列t1,t2,t3,t4搬运成本为510通过比较布置方案目标函数值的大小，找出其中最优布置方案。搬运成本为370。t3t4t

1t2设施布置问题－面向新建型系统布置程序根据某种规则，逐一对所有设施的位置做出安排，最终得出较好的布置方案的算法。改进生成树算法图论法CORELAP程序—ComputerizedRelationshipLayoutPlanning设施布置问题

－改进生成树算法步骤适用于求解单行机床布局问题1）求得单位距离物料搬运费用矩阵F；2）从矩阵F中查找fij最大值，即计算fi*j*相邻布置，记为{ti，tj}3)继续计算最大值fp*q*=max{fi*k，fj*l}若p*=i*，则将机床tq*与机

床ti*相邻布置，记为{tq*，ti，tj}；否则，p*=j*，则将机床tq*与机床tj*相邻布置，记为{ti，tj，tq*}从矩阵F中消去p*行p*列；4)重复上述步骤，直至所有机床布置完毕。改进生成树算法举例举例：已知某一生产线由6台

机床组成，各机床间物料搬运量fij及单位搬运成本Cij分别如下：从至机床123456机床1040802162902400721224283807201441942112140211256224412103169

028912310各机床间物料搬运量fij单位搬运成本Cij从至机床123456机床104464524025233420533465505854235046533840改进生成树算法求解过程从至机床1

23456机床101603201262484502160014460488433201440701232741266070010596524848123105012464508427961240首先由搬运量fij及单位距离搬运成本Cij求出单位距离物

料搬运矩阵F，如下表：改进生成树算法求解过程步骤i*j*p*q*fi*j*/fp*q*布局消去行/列1）16450t1t62）1613320t3t1t613）3632144t2t3t1t634）2665124t2t3t1t6t565）5554105t2t3t1t6t5t45利用单位距离物料搬运

矩阵F，经过数次布置，得出机床排列次序，如下图：fp*q*=max{fi*k，fj*l}163优先生长至3，划去第一个点2划去第三个点5划去第六个点4生成树示意图图论法（构造型算法）图论法（构造型算法）1、邻接值不代表距离，也不代表除邻接部门间和其他部门间的关系2、不考虑部门的尺寸数据，邻

接部门间公共边界的长度也不予考虑3、弧不能相交，图的这种属性称为“平面性—planarity”4、相关图所赋数值权重对总评分影响很大图论法（例子）第一步，选择作业单位对中权重最大的，它们与其他部门有联系也不考虑在上例中，容易判断作业单位对3-4首先进入邻接图第二步，选择第三个要

进入的部门，按照与前两个部门权重的总和来选取图论法（例子）第三步，选择第四个进入的部门，仍然按照总权重的值来选取，将选取的部门作为一个结点加入前面形成的邻接图的面图论法（例子）第四步，选择部门5要

插入哪一个面中，可供选择的有1-2-3，1-2-4，1-3-4和2-3-4将部门5插入1-2-4和2-3-4都得到同样的最大权重9，故两者均可选图论法（例子）第五步，确定了邻接图后，最后一步是构建一个对应的块状布置图，可能

需要对原来的部门有较大的调整，以满足邻接图的要求（实际中可能不能做这么大的调整，如形状）设施布置问题－CORELAP程序CORELAP程序实际上就是计算机化的SLP。步骤：1）基本要素分析；2）相互关系分析；3)计

算综合接近程度TCRij；4)作业单位排序；5)位置布置，计算各位置分数，将作业单位布置在位置分数最高的位置上。这种算法的出发点是部门之间的关系表，布置的目标是实现部门之间最大的密切度。CORELAP—计算综合接近程度TCR首先将关系图中的每一个关系代码，按照下表所示的

对应关系数值化，再对每个部门所有关系值求和，即得到关系总和TCR关系码AEIOUX数值654321生成了布置矢量后，开始向布置图中放置。放置原则是保证进入布置图的部门与前面进入的相邻部门的关系值的和NCR(Neigh

borClosenessRating)最大。CORELAP—作业单位排序选择TCR最大的部门作为最先进入布置的部门。若最大的TCR值有多个部门，即出现“结”，则选择面积最大的部门解“结”；若依然解不开，则随机选取。第二个部门选择与第一个部门具有最高级别关系(A级)的部门，依次

选择E级、I级…，如果在同一关系级别中出现多个部门(“结”)，选择这些部门中TCR最大的部门先布置(解“结”)。在布置中，部门的形状尽可能设计成正方形。在上图中部门1有3种放置方法。放置在位置1a，则与3、4相邻，NCR1a=C

R13+CR14、NCR1b=CR14、NCR1c＝CR13，所以应该选择位置1a进入布置图。对布置图的评估方法为：任意两部门间的关系值×该两部门间的最短直线距离的总和。根据该和值可以比较不同方案的优劣，得分越小越优。CORELAP—例题：已知部门关系图TCR表根据各部门与其他部

门关系总和及相互关系确定布置顺序部门2的总和最高，所以首先布置该部门；其他部门中，部门1与2具有A级关系，所以随后布置部门1；部门4、部门5与部门2同属I级关系．且TCR值相等，但部门4的面积大，所以先4后5；

最后布置与部门2具有O级关系的3部门。这样，布置顺序矢量为2-1-4-5-3。根据各部门面积确定最终布置CORELAP布置过程—面积已知评估布置方案其中2个单元间的距离为到达公共边最少需要的直线距离不同方案的比较，总得分越小的方案越优。BLOCPLAN（构造或者改进型算法）可以用相

关表或者从至表作为“流动”的输入数据评价布置“成本”可以按照基于距离目标或者基于相邻性的目标“带数”是由程序确定，只能为2或者3，而“带宽”可变（带内建筑的面积和除以建筑物的长度）每个部门限定一个“带”中，部门形状为矩形采用连续式布置方式BLOCPLAN（构造或者

改进型算法）例子：AA序号部门名称面积ft2方格数物流量ABCDEFGH1A收货12000300451525105002B铣削800020000302515003C冲压6000150000510004D攻丝120003002000350005E装配80002000

000653506F盖板120003005002506507G发货1200030000000008H虚部门2000500000000虚部门：填补建筑物的不规则之处；设施内的障碍或者不能用的区域（如楼梯）

；代表厂房的额外空间；在最终布置中用于帮助通道位置的确定BLOCPLAN（构造或者改进型算法）初始方案，3个带，带宽由各部门面积和除以建筑物长度确定。基于距离的目标函数z=61061.70带宽BLOCPLAN（构造或者改进型算

法）最终方案：两两交换位置。基于距离的目标函数z=58133.34基于相邻性的目标函数z=235（将上图所有相邻部门单位对的fij值相加）带宽BLOCPLAN（构造或者改进型算法）如果输入数据要求是相关表将作

业单位对的fij和fji相加，形成合并物流量从至表按照5级（如果考虑X级则为6级）将物流量的绝对值转换为密切程度等级，得到相关表按照密切程度等级的默认数值，即A=10、E=5、I=2、O=1、U=0、X=-10，计算布置方案的相邻值BLOCPLAN（

构造或者改进型算法）转化过程如下表所示，由于最大物流量为90，将此值除以5得到18则73-90为A，55-72为E，37-54为I，19-36为O，0-18为U上下三角阵的数值相加绝对值转换为5级密切程度等级设施布置问题－面向改

进型系统布置程序CRAFTCRAFT，计算机辅助设施相对定位技术（在原有布置方案上求得改进布置，得到一个以降低系统物流搬运成本的布置方案）。步骤：1）给定物料搬运结果矩阵，给定初始布置方案，计算物料搬运费用；2）位置交换、费用比

较、选择优化方案；3)重复上述步骤，直至物料搬运费用不再减小。这种交换通常是以两两交换的方式进行，选择具有公共边或相等面积的部门进行交换，其他无公共边或面积不相等的部门不能交换ComputerizedRelativeAllocationofFacilities

TechinqueCRAFT举例1举例：等面积设备布置问题。如图有A、B、C、D四个地点，分别用P1,P2,P3,P4，表示，在四个地点布置四台机床，分别用t1,t2,t3,t4表示。假设四台机床的占地面积相等，可以布置在任一地点上。ABCDABCD加工工艺从至

表0123P41012P32101P23210P1P4P3P2P1从至地点对之间的物料搬运距离07010100P47003020P31030050P210020500P1P4P3P2P1从至地点对之间的物料搬运量距离的计算采用部门中心间的折线

距离CRAFT计算过程1成对地交换设备的布置地点，来改善初始布置方案。迭代次数ij布置方案搬运费用优选方案112t2t1t3t44303t3t2t1t44504t4t2t3t160023t1t3t2t4600

4t1t4t3t241034t1t2t4t34501分别与2、3、4交换位置CRAFT计算过程2迭代次数ij布置方案搬运费用优选方案21=(t1)2=(t4)t4t1t3t24203=(t3)t3t4t1t23704=(t2)t

2t4t3t151023t1t3t4t25104t1t2t3t451034t1t4t2t3440在上一次的优化结果上，继续重复整个过程t1-t4-t3-t2CRAFT计算过程3迭代次数ij布置方案搬运费用优选

方案312t4t3t2t14303t4t3t1t24104t2t4t1t346023t3t1t4t24604t3t2t1t445034t3t4t2t1450CRAFT举例2如图所示的初始布置方案，各数据见下表From／To12345190150

0200506530150040005050000From／To1234511.51.53321.521.51.531.522.51.5431.52.52531.51.52从至表距离表部门中心间的折线距离1-2的距离示例•From／To12345合计113522.500157.52007597

.5172.5303000304000100100500000搬运费用表=从至表相应元素×距离表相应元素总费用=460交换首先选择可以进行交换的部门分别是1—2，1—3，1—5，2—3，2—4，2—5，3—5，4—5。交换1—2，则布置图、距离表、搬运费用表变为From／To12

34511.51.511222.52.5322.51.54251-2互换的布置图From／To12345合计113522.500157.520075162.5237.53030003040005050500000•总的搬运费用变为475；费用增加15，故

取消该布置，继续下一个交换，1—3交换，直至找到最小搬运费用的一种布置，结束本轮交换。第一轮交换结束后，确定出首轮布置图。针对这一布置图、再次进行具有公共边及面积相等的部门的交换，直至搬运费用不再降低为止。CRAFT是应用较为广泛的一种设施规划方法，因此，得到了不断地完善、改进。CRAFT：

例子AA假设的初始方案如同所示，每个部门的中心位置也标注在图中，例如部门A和B的中心间折线距离为6格，而物流量为45，则成本为45×6总成本为2974单位（假设A和G的位置固定进行迭代）虚部门CRAF

T：例子AA交换部门E和F：CRAFT先将大的部门F最左列开始，将前面20个方格标为E，并将原来的E的部门标为F总成本为2953单位CRAFT：例子AA下一次迭代，B和C的交换，最终方案总成本为2833.50单位

设计人员必须打磨布置，一般不采用网格，而采用连续式表现方式，这样可以平滑部门边界并修改部门的面积和取向。打磨后一般不需要计算机算法评价CRAFT：例子AA最终打磨的布置方案其他的构建型计算机化布置方法—ALD

EP(AutomatedLayoutDesignProcedure)其布置基础是关系图;第一个布置部门的选择方法是随机选取的;随后选择方法是根据与第一个部门的关系进行排队，直到排到设定的最低关系密切度TCR(ThresholdClosenessRating)；TCR是指一个预先设定的关

系代码，对于相同的关系，则随机选择进入。放置方法是将选定布置顺序的各部门，按照其单位面积数，以设定的宽度，从布置图的左上角向下，蛇行婉蜒，直至布置完所有的部门ALDEP的评估由于初始布置部门是随机选择的，评估非常重要。评估是寻求相邻部门的关系总和最

大的布置为最后布置方案。首先需要将关系代码按照下表所示的对应关系数值化、然后计算所有相邻部门的关系值，并求和。关系码AEIOUX数值6416410-1024例题：ALDEP的应用设TCR＝I，“扫描”宽度为1。随机选取第一个部门，比如说部门3。寻求

与部门3具有A关系的，没有；E关系的，没有；I关系的，没有；结束寻找。再随机选择第二个部门，比如说选到4，则寻求与部门4具有A关系的，没有；E关系的，没有；I关系的，有部门2、部门5，随机选取；若选到2，则在未分配部门中，寻求与己布置部门具有A关系的部门，这里选到部门1。最后获得布置顺

序矢量为34215。生成34215布置图的过程如图所示对该布置图按照相邻部门原则进行评估，如表所示。多次循环进行（随机选择起始点，再次进行整个过程），选择总分值最大的一个方案。相邻部门关系分值相邻部门关系分值

1--2A644--1U01--4U04--2I41--5U04--3U02--1A644--5I42--3O15--1U02--4I45--4I43--2O1总计1463--4U0其他的改善型计算机

化布置方法—MultiPLE(Muti-floorPlantLayoutEvaluation)是类似于Craft的一种改善型软件，输入数据为从至表，目标函数为基于距离的目标函数，距离计算采用中心点直线距离；部门间的交换采用2部门交换。

在每次迭代中选择布置成本下降最大的方案；与Craft的区别在于MultiPLE的交换可以不局限于两相邻部门间。这一点的实现主要是通过空间填充曲线SFC(SpaceFillingCurve)来实现的。SFC是指填充一定空间的一条折线对于图中的64个单元，该曲线对每个单元只访问一次，

恰能游历整个64个单元。这样在布置顺序矢量一定后，各部门就根据自己的面积，沿着SFC进行放置，直至整个布置例：6个部门的面积分别为16、8、4、16、8、12个单位面积，布置矢量(布置顺序)为1—2—3—4—5—6。则根据SFC的布置

如图所示。•对于一个问题，任意生成一个初始布置顺序矢量，并根据SFC生成初始布置；•任意部门的交换，生成新的布置矢量，根据SFC生成布置，并计算各部门中心间的直线距离；•循环往复，寻找到最低物流费用的布置方案。M

IP（MixedIntegerProgramming）一般情况下，基于数学规划的模型是一种构造型模型，也可以用于改进布置采用连续式的表现方式，而且所有部门均为矩形对于矩形的部门，需要中心和部门的长宽，即可确定其位置和形状（中心的

坐标，左上角和右下角的坐标）采用基于距离的目标函数可以看做是“二维背包问题”MIP首先需要的参数：决策变量xyliiuliiuiBxByAiLiLiWiWiM：厂房长度（方向）：厂房宽度（方向）：部门的面积：部门的长度的下限：部门的长度

的上限：部门的宽度的下限：部门的宽度的上限：很大的正数1010iiiiiixxijijyyijijixiyxixxixyiyyiyzijzzijz：部门中心的坐标：部门中心的坐标

：部门左边（西边）的坐标：部门右边（东边）的坐标：部门底边（南边）的坐标：部门上边（北边）的坐标，部门严格限定在部门的东边；否则，部门严格限定在部门的北边；否则jijixxijyyijxy当且仅当时，部门严格限定在部门的东边；或者，当且仅当

时，部门严格限定在部门的北边。两个部门只有在轴方向分开，或者沿轴分开才能保证两个部门不交叠MIPmin..0,00.50.5,0.50.5,(1ijijijijijluiiiiluiiiiiiiiiiixiiyiiiii

ijizfcstLxxLforalliWyyWforallixxyyAforallixxByyBforallixxyyforalliandjijxxMz

),(1),1,,0,,,0,10,xijyjiijxxyxijjiijjiiiiiiixyijijforalliandjijyyMzforalliandjijzzzzforalliandjijxxyyforallizzorforalliandjij

基于距离的目标函数（非线性）每个部门的长度和宽度不超过制定边界每个部门所需的面积保证每个部门各边的正确定义，位于厂房总坐标内每个部门的中心的坐标1xijjizxx时，保证

与上一个约束目的相同，但是在y方向在x方向或y方向保证两个部门不交叠非负条件0、1变量LOGIC给定从至表作为物流量的输入数据成本由基于距离的目标函数来衡量厂房为矩形时，由LOGIC得到的部门也为矩形，布置为连续表现方式首先是一种构造型算法，也可以作为改进型算法执行一系列的

横割或竖割，每次的切割都有适当的部门被分配到割线的东西或者南北采用树形割集，并假设每次切割和部门分配都是随机的需要计算割线的精确坐标可以替代BLOCPLAN，因为所有的BLOCPLAN布局方案都是LOGIC布局方案

方案的改进采用两两交换，或者模拟退火算法LOGIC：例子AA—形成方案假设第一次为竖割，部门分配如图所示，因为D、F和G的面积已知，因此可以精确计算分割线的x坐标LOGIC：例子AA—形成方案接下来，将上述每一部分厂房再

看成一个完整的厂房，重复切割过程，直到每一块厂房只有一个部门，并计算割线的坐标（上图中是y坐标）LOGIC：例子AA—形成方案LOGIC：例子AA—形成方案LOGIC：例子AA—形成方案切割树：u表示竖割；h表示横割LO

GIC：例子AA—改进交换D和E的位置，保持切割树不变，重新计算相关割的x或者y坐标LOGIC：例子AALOGIC可以用于非矩形厂房，但是需要采用搜索算法，精确计算割线的位置下次课内容1.物料搬运系统