设施规划与物流分析.讲课教案

1、设施规划与物流分析.计算机辅助设施布置计算机辅助设施布置授课内容授课内容l最优算法（最优化理论）最优算法（最优化理论）l次优算法次优算法v穷举法穷举法v面向新建型系统布置程序面向新建型系统布置程序v面向改进型系统布置程序面向改进型系统布置程序FD设施布置方法一览表设施布置方法一览表布置方法和技术布置方法和技术年代年代主要特点和使用条件主要特点和使用条件流程图、样片排列等经验判断方法流程图、样片排列等经验判断方法50年代年代直观、简便、易行直观、简便、易行关于设施间物料流动顺序和数量的各关于设施间物料流动顺序和数量的各种数学分析方法。如属于最优化及其种数学分析方法。如属于最优化及其搜索算法的二次

2、分派算法（搜索算法的二次分派算法（QAP，1957）及相应的计算机软件及相应的计算机软件CRAFT（1964）和和CORELAP（1967）50年代中年代中期到期到60年年代初、中代初、中期期适用于设施数目不太多的情况适用于设施数目不太多的情况系统布置规划方法（系统布置规划方法（SLP）60年代年代至今至今该方法属于系统仿真技术，要求把影响布置的该方法属于系统仿真技术，要求把影响布置的因素尽可能量化，在离散状态下组合寻优。适因素尽可能量化，在离散状态下组合寻优。适用于设施数目不超过用于设施数目不超过15个的情况。其突出特点个的情况。其突出特点是具有方法论意义是具有方法论意义人机交互式决策支持方

3、法人机交互式决策支持方法80年代年代至今至今按决策者意图靠计算机系统支持决策，按决策者意图靠计算机系统支持决策，能进行预测判断；借助于模糊集理论，能进行预测判断；借助于模糊集理论，采用图论方法等采用图论方法等设计数据集成和设计模型集成的理想设计数据集成和设计模型集成的理想实验环境方法（综合决策环境方法）实验环境方法（综合决策环境方法）90年代年代至今至今 (1911年年MCG-INES)是对纯粹计算机程序支持的改进方法是对纯粹计算机程序支持的改进方法布置的定量分析布置的定量分析l图表法图表法设施设施布置技术布置技术l计算机辅助计算机辅助设施设施布置布置图表法设施布置技术图表法设施布置技术l螺旋

4、法螺旋法l路程图法路程图法l关系图法（关系图法（SLP）计算机辅助设施布置研究对象计算机辅助设施布置研究对象l设施设施位置位置问题问题厂址选择厂址选择l设施设施布置布置问题问题厂区规划厂区规划设施设施位置位置问题问题l位置问题位置问题厂址选择：新建一家工厂时，厂址选择：新建一家工厂时，如何在有限的数个可选地点选择一个最佳如何在有限的数个可选地点选择一个最佳厂址，其目标往往是原材料和产品运输费、厂址，其目标往往是原材料和产品运输费、建设费用以及生产费用最小。建设费用以及生产费用最小。l求解方法：求解方法：v运输问题解法运输问题解法v重心法重心法v最优化解法（图论）等。最优化解法（图论）等。设施设

5、施布置布置问题问题l最优算法（最优化理论）最优算法（最优化理论）l次优算法次优算法v穷举法穷举法v面向新建型系统布置程序面向新建型系统布置程序v面向改进型系统布置程序面向改进型系统布置程序设施布置问题最优算法设施布置问题最优算法l二次分配问题模型（二次分配问题模型（QAP, Quadratic Assignment problem ）l二次分配问题是如何布置二次分配问题是如何布置m个设备给个设备给n个地个地点，使得布置方案的物料搬运费最小。点，使得布置方案的物料搬运费最小。l目标函数：一般以物料搬运费用最低。目标函数：一般以物料搬运费用最低。单行机床布局问题数学模型单行机床布局问题数学模型 举

6、例：举例：设一生产线为设一生产线为单行布局，共有单行布局，共有n台台机床，设机床分别为机床，设机床分别为t ti，i1，2，n。 t ti布局位置坐标为布局位置坐标为x xi ，沿布局方向上的长，沿布局方向上的长度尺寸为度尺寸为li 。在一个生产周期内，工件在。在一个生产周期内，工件在机床机床t ti与与t tj之间的往返搬运次数为之间的往返搬运次数为fij ，单位，单位距离搬运费用为距离搬运费用为C Cij ，且机床，且机床t ti和之和之t tj间的间的最小间距为最小间距为dij ，如图所示。如图所示。x xjli x xiljdij单行机床布局问题数学模型单行机床布局问题数学模型目标函数

7、：一般以物料搬运费用最低。目标函数：一般以物料搬运费用最低。|min111jininijijijxxfcZ 约束条件为：约束条件为：机床互不干涉机床互不干涉，即，即1）|x xi x xi| dij （ li li ）/22 2）x xi 0 ，i1，2，n多行机床布局问题数学模型多行机床布局问题数学模型l举例：举例：设一生产线为多设一生产线为多行布局，共有行布局，共有m台台机机床，可以布置区域有床，可以布置区域有n n个地点。个地点。),.,2 , 1,.,2 , 1.(01),.,2 , 1.(1),.,2 , 1.(1min111111njmixmixnjxxxfcZijnjijmiij

8、klijmknlikjlminj；或设施布置问题次优算法设施布置问题次优算法穷举法穷举法面向新建型系统布置程序面向新建型系统布置程序v CORELAP，计算机辅助相关布置规划（将计算机辅助相关布置规划（将SLP运用到计算机上运用到计算机上实现，得到一个使各设施间接近度最大的布置方案）实现，得到一个使各设施间接近度最大的布置方案）v ALDEP，自动化布置设计（在给定系统边界内产生许多可行布置自动化布置设计（在给定系统边界内产生许多可行布置方案，并给出各方案的评价）方案，并给出各方案的评价）面向改进型系统布置程序面向改进型系统布置程序v CRAFT，计算机辅助设施相对定位技术（在原有布置方案上求

9、得计算机辅助设施相对定位技术（在原有布置方案上求得改进布置，得到一个以降低系统物流搬运成本的布置方案）改进布置，得到一个以降低系统物流搬运成本的布置方案）v COFAD，计算机辅助设施设计（是对计算机辅助设施设计（是对CRAFT的改进，考虑了搬的改进，考虑了搬运设备及其成本评价，得到更全面的设计方案，针对不同的物流运设备及其成本评价，得到更全面的设计方案，针对不同的物流系统，系统，COFAD有有COFAD II和和COFAD III等）等）设施布置问题穷举法设施布置问题穷举法l次优算法次优算法穷举法穷举法l又称枚举法，适于在给定设施布置地点又称枚举法，适于在给定设施布置地点组的场合。组的场合。

10、l步骤：列出所有布置方案，通过比较布步骤：列出所有布置方案，通过比较布置方案目标函数值的大小，找出其中的置方案目标函数值的大小，找出其中的一个或几个最优布置方案。一个或几个最优布置方案。穷举法举例穷举法举例l举例：举例：等面积设备布置问题。如图有等面积设备布置问题。如图有A、B、C、D四个地点，分别用四个地点，分别用P1 , P2 , P3 , P4 ，表示，在四个地点布置四，表示，在四个地点布置四台机床，分别用台机床，分别用t t1 , t t2 , t t3 , t t4表示。假表示。假设四台机床的占地面积相等，可以设四台机床的占地面积相等，可以布置在任一地点上。布置在任一地点上。ABCD

11、ABCD加工工艺从至表加工工艺从至表0123P41012P32101P23210P1P4P3P2P1从至地点对之间的物料搬运距离地点对之间的物料搬运距离07010100P47003020P31030050P210020500P1P4P3P2P1从至地点对之间的物料搬运量地点对之间的物料搬运量穷举法的计算过程穷举法的计算过程l列出所有列出所有24个布置方案个布置方案l例如，排列例如，排列 t t1 , t t2 , t t3 , t t4搬运成本为搬运成本为510t t1t t2t t3t t4穷举法的计算过程穷举法的计算过程t t2t t1t t4t t3l列出所有列出所有24个布置方案个布置

12、方案l例如，排列例如，排列 t t1 , t t2 , t t3 , t t4搬运成本为搬运成本为510l通过比较布置方案目标函数值的大小，通过比较布置方案目标函数值的大小，找出其中最优布置方案。找出其中最优布置方案。l搬运成本为搬运成本为370。t t3t t4t t1t t2设施布置问题面向新建型系统布设施布置问题面向新建型系统布置程序置程序l根据某种规则，逐一对所有设施根据某种规则，逐一对所有设施的位置做出安排，最终得出较好的位置做出安排，最终得出较好的布置方案的算法。的布置方案的算法。v改进生成树算法改进生成树算法vCORELAPCORELAP程序程序设施布置问题改进生成树算法步骤设施

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

14、tj ；否则，；否则， p* * = = j* * ，则将，则将机床机床t q * *与机床与机床t tj * *相邻布置相邻布置 ，记为，记为 t ti ， t tj ， t q * * v从矩阵从矩阵F F中消去中消去p* *行行 p* *列；列；l4)4)重复上述步骤，直至所有机床布置完毕。重复上述步骤，直至所有机床布置完毕。改进生成树算法举例改进生成树算法举例l举例：举例：已知某一生产线由已知某一生产线由6台机床组成，台机床组成，各机床间物料搬运量各机床间物料搬运量fij及单位距离搬运成及单位距离搬运成本本Cij以及各机床间间隔矩阵以及各机床间间隔矩阵dij分别如下：分别如下：从至从至

15、机床机床123456机床机床1040802162902400721224283807201441942112140211256224412103169028912310各机各机床间床间物料物料搬运搬运量量fij单位距离搬运成本单位距离搬运成本Cij从至从至机床机床123456机床机床104464524025233420533465505854235046533840各机床间间隔矩阵各机床间间隔矩阵dij从至从至机床机床123456机床机床101112121011113110111411103152113026111120改进生成树算法求解过程改进生成树算法求解过程从至从至机床机床123456机

16、床机床101603201262484502160014460488433201440701232741266070010596524848123105012464508427961240首先由搬运量首先由搬运量fij及单位距离搬运成本及单位距离搬运成本Cij求出求出单位距离物料搬运矩阵单位距离物料搬运矩阵F，如下表：如下表：改进生成树算法求解过程改进生成树算法求解过程步骤步骤i * *j* *p* *q * *f fi * * j * * /fp * * q * *布局布局消去消去行行/列列1）16450t t1 t t62 ）1613320t t3 t t1 t t613 ）3632144t

17、 t2t t3 t t1 t t634 ）2665124t t2t t3 t t1 t t6t t565 ）5554105t t2t t3 t t1 t t6t t5t t45利用单位距离物料搬运矩阵利用单位距离物料搬运矩阵F，经过数次布经过数次布置，得出机床排列次序，如下图：置，得出机床排列次序，如下图： fp* * q * * =max=max f fi * *k ， f fj* *l 设施布置问题设施布置问题CORELAP程序程序lCORELAPCORELAP程序实际上就是计算机化的程序实际上就是计算机化的SLPSLP。步骤：步骤：l1 1）基本要素分析）基本要素分析；l2 2）相互关系

18、分析相互关系分析；l3) 3) 计算综合接近程度计算综合接近程度TCRTCRij ；l4) 4) 作业单位排序；作业单位排序；l5) 5) 位置布置，计算各位置分数，将作业单位置布置，计算各位置分数，将作业单位布置在位置分数最高的位置上位布置在位置分数最高的位置上。序号 作业单位名称 用途 建筑面积 备注 1 原材料库 储存钢材、铸锭 20*30 露天 2 铸造车间 铸造 12*24 3 热处理车间 热处理 12*12 4 机加工车间 车、铣、钻 12*36 5 精密车间 精镗、磨销 12*36 6 标准件、半成品库 储存外构件、半成品 12*24 7 组装车间 组装转向器 12*36 8 性

19、能试验室 转向器性能检验 12*12 9 成品库 成品储存 12*12 10 办公、服务楼 办公、食堂等 80*60 11 设备维修车间 机床维修 12*24 示例一：机械厂的作业单位建筑物汇总表举例：举例：某机械厂由某机械厂由11个作业单位组成，利用个作业单位组成，利用CORELAPCORELAP程序程序方法，对该厂进行平面布置。方法，对该厂进行平面布置。建立作业单位综合相互关系表（示例） 设备维修车间 作业单位名称 原材料库 铸造车间 热处理车间 机加工车间 精密车间 半成品库 组装车间 性能实验室 成品库 办公、服务楼 U U O U O E E I E O I I E I I A A

20、O U U U U U U I O U I O U O X U U U U U X U U O O O X U X U U X U U O U U U 作业单 位代号 1 （原材料库） 2 （铸造车间） 3 （热处理） 4 （机加工） 5（精密车间） 6 （标准件库） 7 （组装车间） 8 （试验室） 9 （成品库） 10（办公楼） 11（维修车间） 1 A/4 I/2 I/2 U/0 U U U U U U 2 A/4 U E/3 X/ （-1） U U X U X O 3 I/2 U I O/1 U U X U X O 4 I/2 E/3 I/2 E/3 I/2 U U U O O 5 U

21、/0 X O/1 E E U U U O O 6 U/0 U U I E A U U U U 7 U/0 U U U U A A O I O 8 U/0 X X U U U A E I U 9 U/0 U U U U U O E O U 10 U/0 X X O O U I I O O 11 U/0 O O O O U O U U O 综综合合接接近近程程度度 8 5 4 14 8 9 12 7 5 6 6 排排序序 5 9 4 1 4 3 2 6 10 7 8 1、计算综合接近程度： 将作业单位综合相互关系表变换成类似于从至表一样的 三角矩阵，然后量化关系等级。示例：机械厂综合接近程度排序表

22、CORELAP的计算过程的计算过程设施布置问题面向改进型系统设施布置问题面向改进型系统布置程序布置程序CRAFTlCRAFT，计算机辅助设施相对定位技术（在原计算机辅助设施相对定位技术（在原有布置方案上求得改进布置，得到一个以降低系有布置方案上求得改进布置，得到一个以降低系统物流搬运成本的布置方案）。统物流搬运成本的布置方案）。步骤：步骤：l1 1）给定物料搬运结果矩阵）给定物料搬运结果矩阵，给定初始布置方案，给定初始布置方案，计算物料搬运费用；计算物料搬运费用；l2 2）位置交换、费用比较、选择优化方案位置交换、费用比较、选择优化方案；l3)3)重复上述步骤，直至物料搬运费用不再减小。重复上

23、述步骤，直至物料搬运费用不再减小。CRAFT举例举例l举例：举例：等面积设备布置问题。如图有等面积设备布置问题。如图有A、B、C、D四个地点，分别用四个地点，分别用P1 , P2 , P3 , P4 ，表示，在四个地点布置四表示，在四个地点布置四台机床，分别用台机床，分别用t t1 , t t2 , t t3 , t t4表示。假表示。假设四台机床的占地面积相等，可以设四台机床的占地面积相等，可以布置在任一地点上。布置在任一地点上。ABCDABCD加工工艺从至表加工工艺从至表0123P41012P32101P23210P1P4P3P2P1从至地点对之间的物料搬运距离地点对之间的物料搬运距离07

24、010100P47003020P31030050P210020500P1P4P3P2P1从至地点对之间的物料搬运量地点对之间的物料搬运量CRAFT计算过程计算过程1l成对地交换设备的布置地点，来改善成对地交换设备的布置地点，来改善初始初始布置方案布置方案。迭代次迭代次数数ij布置方案布置方案搬运搬运费用费用优选方案优选方案112t t2 t t1 t t3 t t44303t t3 t t2 t t1 t t44504t t4 t t2 t t3 t t1 60023t t1 t t3 t t2 t t46004t t1 t t4 t t3 t t2 41034t t1 t t2 t t4 t

25、 t3 450 CRAFT计算过程计算过程2迭代次迭代次数数ij布置方案布置方案搬运搬运费用费用优选方优选方案案212t t4 t t1 t t3 t t2 4203t t3 t t4 t t1 t t23704t t2 t t4 t t3 t t1 51023t t1 t t3 t t4 t t2 5104t t1 t t2 t t3 t t4 51034t t1 t t4 t t2 t t3 440 CRAFT计算过程计算过程3迭代次迭代次数数ij布置方案布置方案搬运搬运费用费用优选方优选方案案312t t4t t3 t t2 t t14303t t4t t3t t1t t24104t t2 t t4 t t1 t t3 46023t t3 t t1 t t4 t t24604t t3 t t2 t t1 t t4450