《设施规划第7章-设施布置问题求解及其计算机辅助设计和仿真课件.ppt》由会员分享，可在线阅读，更多相关《设施规划第7章-设施布置问题求解及其计算机辅助设计和仿真课件.ppt（105页珍藏版）》请在三一办公上搜索。
1、第1章 绪论第2章 设施选址第3章 设施布置规划第4章 物料搬运与仓储设备第5章 物料搬运系统设计第6章 仓库运作和规划第7章 设施布置问题建模、计算机辅助设计和仿真第8章 设施规划综合案例,设施布置问题求解及其计算机辅助设计和仿真,7.1 制造系统设施布局的建模分析7.2 计算机辅助设施规划7.3 设施布局数学建模7.4 应用禁忌搜索算法求解二次分配问题7.5 设施布置软件和仿真工具7.6 Flexsim仿真软件的应用案例,Chapter 7,7-1,制造系统设施布局的建模分析,5,7-1-1,模型分类,制造系统的布局设计方法可分为图论法和定量分析法两类。,图论法是基于对设施尺寸和生产工艺的
2、要求，进行材料流及活动关系分析，形成空间关系图；然后，根据实际可用的面积做出几种布局方案，进行评价择优。,定量分析法是指建立布局模型，并应用各种算法对其求解，最终得到一个较优的布局方案。,建模方法，主要有三类：,1)图与网络的方法主要有活动循环图法、关键路径法、Petri网、组合网络等。,3)综合方法在设备布局建模过程中，随着面向对象技术的发展与应用，研究者们尝试将其与其他建模方法相融合，如与Petri网结合形成面向对象的Petri网等，降低了Petri网建模和分析的难度，增加了建模的描述能力和功能实现能力。,2)数学分析方法此类方法通过建立数学模型对制造系统进行建模，主要有极大代数法、扰动分
3、析法、排队网络法。,平面布局问题中的有两类主要问题：,二次分配问题(Quadratic Assignment Problem,QAP)混合整数规划（Mix Integer Programming）,7-1-2,优化目标,5.考虑重新布局费用,7,7-1-2,优化目标,在建立设施规划模型时，应将物流运动看作矢量，考虑逆向与正向物流的交叉对物流效率、安全的影响，在将目标函数确定在物流成本最小化的同时，力求降低物流的交叉程度。,目前多数文献在建立模型时，目标函数有物流成本（以搬运矩计算）最小化，和布局面积最小化，或者两者的综合。,7-1-3,约束条件,5.资金约束（对于动态布局，布局费用有限制）,9
4、,7-2,计算机辅助设施规划,计算机辅助设施规划（CAFD）是指在设施规划的过程中充分利用计算机辅助设计相关技术及软件来完成布置建模、运行分析、动画展示及系统优化等工作，相关的选址分析计算、设施布置及参数选择、系统修改等过程都是利用计算机来完成的。,计算机作为辅助工具，在设施规划中起着十分重要的作用。,（2）确定和检测预想的系统设计运行效果。（3）进行敏感性分析，分析出哪个因素的变化对整个操作系统有较大的影响。（4）进行瓶颈分析。规划人员能够发现影响系统流程的瓶颈位置，并对此进行改进。,（1）在规划的条件下能够以一定的时间段进行仿真，使设计者能够观察到设计的系统在特殊条件下长时间的运行效果。,
5、（5）确定最大化因素。通过最大化因素的确定，规划人员能够确定产生最佳效果的因素相组合，以发挥其最大的功效。,（6）能够使一些非正态分布易于理解，不是所有行业中的现象都符合正态分布，软件可以以原始数据为基础，从而为一个特定的情况选择最合适的随机分布，以便能够为这个随机过程制定更为准确的环节。在系统运行之前进行仿真模拟来评价该系统，从而确保计划的可行性。,7-2,计算机辅助设施规划,11,7-2-1,ALDEP算法,ALDEP（Automated Layout Design Programs，自动化设计法）是一种由凑合法生成布置设计的算法。,ALDEP的工作原理十分简单，按照作业单位之间密切程度等
6、级的原理进行工作。ALDEP主要输入的是支持作业单位关系间密切程度等级。,ALDEP使用了一种纵向扫描的方法（vertical scan method），如图7-1所示。每一个作业单位视为一等宽条带，其长度由作业单位面积所决定。扫描长度即为场地平面的宽度，扫描宽度可由用户选择，或根据场地平面及安排对象的大小而定。,12,7-2-1,ALDEP算法,评价设施布置性能的方法是，对各相邻作业单位累加密切程度的赋值，然后得到一个数值再加以比较。,下述配置表明赋与数值的一种可能方式：,A=43=64 E=42=16 I=41=4 O=40=1 U=0 X=-45=-1024,这一过程按布置方案数重复，就
7、能比较其性能孰优孰劣。,13,7-2-2,CORELAP算法,CORELAP（Computerized Relationship Layout Planning，相互关系法）用长方形的作业单位构造布置。,根据对作业单位密切程度的权重赋值即A=6，E=5，I=4，O=3，U=2，X=1。这些数值用以计算各作业单位总密切程度等级TCR(Total Closeness Rating)，即,（7-1）,是作业单位i和j之间密切程度的赋值,TCR表示一个作业单位与另一个作业单位之间的彼此可接受性或喜爱性。,在CORELAP中，根据准备放上去的新作业单位和已在图上的将分享共同边界的相邻作业单位之间的权重等
8、级之和，来决定选择对象。,由于使用的是确定性方法，CORELAP只产生一个最终布置方案。,14,7-2-2,CORELAP算法,为设计不同的方案做出不同的独立评价，可改变以下条件：,15,7-2-3,CRAFT算法,CRAFT（Computerized Relative Allocation of Facilities Technique，位置配置法）是一种单阶段布局算法。,CRAFT是基于物流信息或者从至表中累加的作业单位物流强度的。因此CRAFT是一种定量布置方法。,CRAFT是一种改进程序，这意味着CRAFT接受一项初始布置设计并用顺序方式成对交换作业单位的位置，试图做出改进。在与其他设
9、计方案比较决定某一布置设计是较好的方案时，CRAFT用物品搬移或运输成本作为评价标准，此成本用移动距离的线性函数来表达。所以，一项较好的设计是搬移成本较低，一项优化设计可能是搬移成本最低的设计。,图7-2是包括4个作业单位A、B、C和D的布置设计。为了简化计算，假设物料运输只发生在4个作业单位的中心之间并沿着长方通道运行。,图7-2 应用CRAFT的初始布置设计,16,7-2-3,CRAFT算法,1）被搬运物料的种类(如粗糙的还是易碎的，轻巧的还是笨重的)。2）每一往返行程中单元载荷的数量。3）每一周期中往返行程的数量。4）物料搬运设备的类型(如普通设备还是专用设备等)。,在给定的布置下所有作
10、业单位之间的距离均可知，为了计算物料搬运或运输成本，另一主要数据来自：,CRAFT的解题过程是，用作业单位之间成对交换的方法来设法改进设计，视成对交换的结果是否有更好的布置设计出现。然而CRAFT的一项限制使这种交换只能在相邻的作业单位之间进行，根据这一简单理由CRAFT执行互换，互换时不考虑面积，布置方案决定后再为各作业单位加上面积。,17,7-2-3,CRAFT算法,在产生5个新的布置方案后，比较各方案的总成本。如果这些新方案的成本都较原方案高，显然就不予考虑。如对布置的改进可降低总成本就应进一步考虑。,假设作业单位A和D相互交换可得最佳改进，其交换结果如图7-3所示，值得注意的是这一交换
11、过程引起作业单位的形状非常不规则。,图7-3 CRAFT的布置设计经交换的结果,CRAFT是一个优化的算法，是各作业单位之间使总物料搬运最少或运输成本最小化的结果。这一算法与为解决二次分配问题(QAP)的陡速下降成对交换过程紧密联系，所以可以把CRAFT产生的布置设计提供给布置设计人员作为一个评价标杆(Bench Marking)，然而由于CRAFT算法简单，对于解决大型问题的作用非常有限。,18,7-2-4,MULTIPLE算法,MULTIPLE算法（Multi-floor Plant Layout Evaluation，多层楼房设施布置设计）是CRAFT的改进型，它已商业化并被称作为lay
12、Opt的布置设计软件包。在单层楼房设施布置的基础上。MULTIPLE已开发了多层楼房设施布置设计程序，像CRAFT一样，MLLTIPLE使用物流信息、目标函数和搜索程序。MUTIPLE用优化程序产生改进的布置方案，与CRAFT不同，它没有在非邻接作业单位之间不能交换的限制，所以允许任何作业单位位置作双向交换。,MULTIPLE算法的主要特征是采用空间填充曲线用以构造布置，以及用以表示作业单位布置的空间。,19,7-3,设施布局数学建模,研究布置问题的最主要目标是实现时间或成本的最小化。首先我们需要将布置问题建模，然后用合适的算法求解这一模型。为设施建模，最基本最简单的模型就是单行布置(Sing
13、le-row layout)和多行布置（multi-row layout）的模型。,为了开发能在合理时间内解决问题的模型，需要作些假设。,在许多应用中这些假设是可以接受的，因为所得的最终解决方案是可以修改的。,但在有些情况下为反映实际情况而修改解决方案可能引起目标函数剧烈的变化，以致模型中的假设可能有缺陷而不能接受。,20,7-3,设施布局数学建模,21,7-3-1,单行布置问题模型,在讨论单行布置问题的非线性模型ABSMODEL1时，先作如下假设：,设施形状是方形或长方形，均为已知。设施排列在一直线上。设施方位是已知的。,第1个假设：许多布置问题尽管设施既非标准的正方也非长方，但通常可近似视
14、为正方或长方，如图7-4所示。这种近似法大大简化了建模过程，同样也简化了解题过程。,图7-4 非正方、非长方设施形状的近似,第3个假设：在许多制造系统中，机器设备的方位是使装卸点面向通道以便于装卸零件，由于机器设备上装卸毛坯的位置是固定的，所以它的布置方位实际上是已知的。,22,7-3-2,ABSMODEL1模型,先介绍ABSMODEL1模型中各参数的符号：,为设施中心与垂直参考线(VRL)之间的距离。,图7-5 单列布置中各变量与决策变量的表示,23,7-3-2,ABSMODEL1模型,ABSMODEL1模型的目标函数为,（7-2）,约束条件s.t.为,（7-3）,ABSMODEL1模型可以
15、用公式表示成等长度和不等长度设施的布置问题。在此模型中非负的约束条件并非必需。在垂直维度中不考虑重叠约束，隐含假设所有设施中心的垂直坐标都是相同的。,24,7-3-2,ABSMODEL1模型,虽然建筑物尺寸在模型中考虑为无限大，在最优解中也不会远离、分散。假如建筑物水平方向尺寸已知，而用户需要将位于水平坐标内的约束包含在内，即加上如下约束,（7-4）,为设施i的中心和VRL之间的距离，即使当设施在左右极端位置上时，约束式(7-4)也会被满足，这可由图7-6加以验证。,图7-6 对不等设施长度问题一个可行的单行布置,25,7-3-2,ABSMODEL1模型,通常非线性规划(NLP)问题的优化解是
16、难于找到的。不像线性规划(LP)，一个NLP问题的可行域不需要一个凸集，即使是一个凸集，对一个NLP问题不需要在可行域上有一个极点。这样对一个一般的NLP问题而言，寻找一个优化解似乎是不可能的。,然而有一些NLP问题的特殊情况，寻找一个优化解相对容易一些。,在另外一些NLP问题中，一个凹形目标函数可以最大化，而其可行域由一个凸集约束所定义，或者相反一个凸形目标函数可以最小化，而其可行域由一个凹集约束所定义。,在一些无约束的NLP问题中，一个凹形目标函数可以最大化，或者一个凸形目标函数可以最小化,例7-1 一家修理电视和VCD的修理店准备扩大业务范围，修理其他电子消费产品，包括电脑及其周边设备、
17、微波炉、音响系统等，店中也准备出售相关附件及零配件。去年店主收到无数抱怨，原因有店内拥挤阻塞、零件及修理单错放、修理质量低劣等问题。店主凭借经验，认为只要在现有空间中重新布置设施，房间拥挤和质量问题就能改进。于是招募了4名IE专业的高年级学生组成团队用改进设施布置的办法来解决问题。,26,7-3-2,ABSMODEL1模型,（2）虽然修理技术员共享一些仪器设备，但其他仪器设备往往是某一个技术员用得较多。（3）生产中的使用面积为23m5m。（4）现有布置应如图7-7a所示。,学生团队在对该店进行观察和搜集数据后，归纳出以下几点情况：,（1）公司第一个技术员负责修理电视和VCD，第二个负责修理微波
18、炉，第三个修理音响 系统，第四个修理电脑。,图7-7 修理店现有布置及改进,改进后的布置如图7-7b所示。,27,7-3-2,ABSMODEL1模型,学生小组在一个工作日认真观察了每一对房间之间的交互作用、相互影响。这种相互作用和影响取决于一个技术员（如音响技术员），应用一些主要被其他技术员（如电脑技术员）使用设备的频繁程度。,学生小组根据用于每一房间的仪器设备决定房间的尺寸大小，并决定每一技术员需要的工作面积。按照每一房间的用途和编号，其尺寸列于图7-8中。,图7-8往复行程矩阵和五个房间的大小,28,7-3-2,ABSMODEL1模型,解：使设施长度平行于建筑物长度方向，因为往复行程矩阵是
19、对称的，即,如此矩阵不对称，要使其对称化。包含在人员走动中的成本与行程距离直接成正比。因为设施是每间房间，不需要房间之间留出间隙距离。,这一模型在非负约束等条件下，可得每一个房间中心相对于VRL的水平坐标值为：,X1=33,X2=48,X3=58,X4=73,X5=90,图7-7 修理店现有布置及改进,29,7-3-3,不等面积设施的多行布置模型,关于多行布置问题有仪表板布置问题，自动化制造系统中机器设备的布置问题，各种键盘设计和办公室布置设计等。已为明确地表达这些问题开发了各种模型如ABSMODEL1模型，ABSMODEL3模型，二次分配问题(QAP)，线性混合整数规划模型，以及在目标函数和
20、约束中有绝对项的非线性模型等。ABSMODEL2是假设面积为相等的设施的布置模型，对多数实际布置问题来说这种假设是不现实的，所以这里只介绍ABSMODEL3模型。,ABSMODEL3模型采用一种折衷的办法，即先在模型中给定一个假设的方位，进而不断测试解的结果，然后根据结果来修改原始方位，再来求解模型。这一过程不断重复，直到所获布置中的机器都有满意的方位为止。,ABSMODEL3模型也包括目标函数，以及约束中含有绝对项。在ABSMODEL3中，假设设施是方的或长方形，并且其方位事先已知。,30,7-3-4,ABSMODEL3模型,先介绍ABSMODEL3模型中各参数的符号：,31,7-3-4,A
21、BSMODEL3模型,图7-9不等面积多行布置决策变量和参数图示,32,7-3-4,ABSMODEL3模型,目标函数为：,（7-5）,约束条件为,（7-6）,（7-7）,（7-8）,33,7-3-4,ABSMODEL3模型,ABSMODEL3模型的优点是直观、方便、容易理解，并能用简单的启发式解题；,主要缺点是要求设施的外形只能是方形或长方形，还要假定已知设施的方位，要放松这一约束就要为增加复杂性而付出代价。,因为模型ABSMODEL3是非线性的，因而其解经常是次优的或远离优化。,对于真正在实际中应用的多行布置模型，除ABSMODEL3外还有和其相当的二次分配问题(QAP)。QAP从传统上说早
22、已用于研究和解决布置问题，从深度和广度来说更胜一筹。,34,7-3-5,二维布局分析,物料流动的方向相互垂直，或者刚好相反，就形成物流交叉。为了物流系统的效率、安全，进行设备布局时，一般希望尽可能减少物流交叉。在一个复杂的物流系统中，可能出现大量的物流交叉，不同的布局会带来不同的交叉程度。这里考虑模型的主要特点，是在保持物流交叉较小的前提下，最小化物流成本。,对于二维布局，这里人为规定横向和纵向两个物流方向，同时，规定向右和向下分别为顺流方向，向左和向上分别为逆流方向。,物流成本=系数*物流距离*物流重量，其中系数包括CX1、CX2与CY1、CY2，其意义分别如下：,CX1：横向顺流成本系数C
23、X2：横向逆流成本系数CY1：纵向顺流成本系数CY2：纵向逆流成本系数,通过系数CX1、CX2与CY1、CY2调整物流成本时，系数绝对值越大，相应物流成本值越高，数学模型目标函数最小化物流成本，则可排除因物流交叉导致的高成本方案，从而得到较低的物流交叉水平上的低物流成本方案。,由于逆向物流用负数表示，CX2和CY2也取负值，使成本为正值。,35,7-3-5,二维布局分析,数学模型求解和计算物流成本时，不同的系数设置可产生不同的设备布局结果。,1)不考虑物流交叉影响的取值CX1=1，CX2=-1；CY1=1，CY2=-1；2)提高纵向物流的成本，减少纵向物流 CX1=1，CX2=-1；CY1=3
24、，CY2=-3；3)提高逆向物流的成本，减少逆向物流 CX1=1，CX2=-4；CY1=1，CY2=-4；4)以上两种的综合 CX1=1，CX2=-3；CY1=2，CY2=-6；,例7-2 某车间有六台设备组成的生产线，设备编号为16，设备形状为矩形，布局方位已知，其长分别为50,150,80,30,40,30，宽分别为40,60,50,20,30,30，横向、纵向安全距离为10，主要生产两种产品A和B，A的生产工艺为1-2-3-4-5-6，B的生产工艺1-5-6，A、B产品的重量之比为2：5，顺流方向为从左到右，从上到下。,36,7-3-5,二维布局分析,表7-1 不同系数设置下的布局结果,
25、37,7-3-6,二次分配模型,（7-9）,38,7-3-6,二次分配模型,一维模型,图7-10 一维布局模型,设备在一维方向上排列，物流成本与搬运距离，搬运次数和重量的乘积成正比；设备的大小和形状相同，为矩形；搬运距离为设备中心点的距离；逆向物流的成本高于顺向物流的成本。,39,7-3-6,二次分配模型,参数：,决策变量：,40,7-3-6,二次分配模型,目标函数：,约束：,41,二维模型,7-3-6,二次分配模型,图7-11 布局问题的二次分配模型,42,7-3-6,二次分配模型,假设：设备在二维方向排列，物流成本与搬运离，搬运次数和重量的乘积成正比；物流搬运距离为设备间的曼哈顿距离；逆向
26、物流的成本高于顺向物流的成本。,参数：,43,7-3-6,二次分配模型,决策变量：,目标函数：,44,约束：,7-3-6,二次分配模型,45,7-3-7,混合整数规划模型,在条件方面，混合整数规划模型没有给定布局点，而是给定整个平面区域，要求布局于其间的设备物流成本低，且相互没有干涉；在结果方面，二次分配问题的解是设备与布局点的映射关系，是离散值，不考虑与面积相关的因素，混合整数规划的结果是设备的坐标，是连续值，即考虑各个设备的形状、面积使其没有干涉，目标函数也常常重视布局结果占用的面积大小，规划结果如图7-12所示：,图7-12 混合整数规划模型,46,7-3-7,混合整数规划模型,假设条件
27、：设备形状抽象为矩形，设备摆放方向已知；布局平面为矩形区域。,参数：,47,7-3-7,混合整数规划模型,决策变量：,目标函数：,48,约束：,7-3-7,混合整数规划模型,49,7-3-8,多行布局的混合整数规划模型,许多实际的布局问题，不仅对设备的大小和安全距离有要求，对其摆放位置也有所限制。在柔性制造系统中，车间平面被划分为若干子区域，然后在这些子区域上布置所有设备，设备间保持安全距离并不与边界干涉；车间的物流路线仍然按照曼哈顿距离计算。由于这些要求普遍存在于柔性系统的设施布局中，可以把它们归为多行布局的混合整数规划问题（Multi-row Mix Integer Programming
28、，MMIP），如图7-13所示。,图7-13 多行布局的混合整数规划模型,50,7-3-8,多行布局的混合整数规划模型,假设条件：设备形状抽象为矩形，设备摆放方向已知；布局平面为矩形，被划分为 若干行，各行长度相同；,参数：,51,7-3-8,多行布局的混合整数规划模型,决策变量：,目标函数：,52,7-3-8,多行布局的混合整数规划模型,约束：,53,7-4,应用禁忌搜索算法求解二次分配问题,本节集中讨论禁忌搜索算法实现过程中两个比较关键的问题：初始解的构造，和解的编码和生成方式。,54,7-4-1,生成初始解的启发式算法,构造启发式算法的基本思路是，将较大的物流量与较小的物流距离相乘，较小
29、的物流量与较大的物流距离相乘，这样使得乘积的总和最小。最理想的情况是，物流量按从大到小依次排列，物流距离按从小到大依次排列，但实际情况中这样的情形很少出现。不失一般性，取以下6*6数据为例说明：,55,7-4-1,生成初始解的启发式算法,表7-2 物流量矩阵 表7-3 距离矩阵,为了保证已被分配的设施或位置不被重复分配，本启发式算法分为选择和删除两步重复执行：1）遍历当前Flow/Dist表，选择表中的最大/最小值；2）删除该值所在的行和列的数据，以及此行数/列数对应的列/行的数据；重复1)、2)步骤，若当前表为空则停止。,56,7-4-1,生成初始解的启发式算法,由此步骤得到新的Flow序列
30、过程为：选取85（0，2），如表7-4所示，删除第0行和第2列的数据，以及第2行和第0列的数据，得到表7-5；选取77（4，5），如表7-5所示，删除第4、5行，第4、5列数据，得到表7-6；选取58（1，3），如表7-6所示。,表7-4 选择最大值85 表7-5选择最大值77 表7-6选择最大值58,57,7-4-1,生成初始解的启发式算法,由此得到设施序列0 2 4 5 1 3；同理得到三个距离值10，21，69，和位置序列2 5 0 1 3 4，将设施与位置一一对应，得到初始解，如表7-7所示。,表7-7 一个初始解,58,7-4-2,解的编码和生成步骤,QAP问题,QAP问题的解是设备
31、与位置之间的映射，同一个解可以有两种等价的表达方式：基于设备次序的表达法和基于位置次序的表达法。下表中左边的（4 2 5 3 6 0 1）与右边的（5 6 1 3 0 2 4）等价。统一编码标准后，用长度为n的编码，即可表达一个设备布局的解。,表 7-2 两种编码方式,59,7-4-2,解的编码和生成步骤,MMIP问题,QAP问题的解是离散的，而MMIP的解可以取连续值，理论上具有无穷多个解，因此简单地搜索解空间是不可行的，一类方法对该问题进行了简化，使得各台设备之间保持最小的安全距离，而不再进行细节的调整；而另一类方法，将设备之间的间距作为编码的组成部分，每一次迭代搜索，对这些间距进行分配和
32、调整。相比而言，前者过于简化的做法，可能对算法结果的优化程度有所影响；而后者不仅增加了编码的复杂程度，每一次迭代搜索均要对间距进行操作，对计算复杂程度影响较大。为了达到两个方面的平衡，将解的生成过程分为两大步骤：,60,7-4-2,解的编码和生成步骤,第一步是按照最小安全距离原则布局。在最小安全距离原则下，要表示一个分行布局，一个编码必须分两部分信息，设备的摆放顺序，和分行位置信息。,图7-14 多行布局模型,图7-14中，按照位置次序表达法，该解可以表示成（3 5 8 6 2 0 4 1 7 9|4 3 3）；每次通过移动而生成新的邻域解时，不仅要变更前n位设备的编号，也要重新计算各行的设备
33、数。,61,7-4-2,解的编码和生成步骤,第二步骤是微调。微调时涉及到适配值阈值（1），长度阈值和精度p三个值。,（3）以精度值p为基本单位，将剩余长度分割成片段，将这些片段分配到该行各个设备的间隔之间。,微调按照下述步骤进行：,（1）按照最小安全距离原则布局之后，计算适配值。在成本最小化模型中，如果适配值大于当前最优值的倍，则以当前适配值作为最终适配值，放弃微调，否则：,（2）计算该布局各行的剩余长度。如果剩余长度都不大于设定的长度阈值，则放弃微调，否则转入步骤（3）：,阈值，、精度p的大小，片段的分配方式，对微调运算发生的次数、计算的复杂度和结果的精度均有直接的影响。该方法的优点在于，减
34、少了精确求解的次数，仅仅在同时满足两个阈值的时候，才真正开始微调运算；微调运算的分配方式可以是随机分配，也可以是枚举；可以人为控制微调运算的精度。,62,7-4-3,二次分配问题的数值实验,为了使结论具有一定的可信度，本节实验数据均来自QAP问题的权威网站QAPLIB（http:/www.opt.math.tu-graz.ac.at/qaplib/），选取5个不同规模的问题进行实验，分析其性能与参数设置的关系。,实验参数包括问题规模、候选解规模、禁忌表长度、迭代次数、初始解生成方式、邻域解生成方式。,表 7-9 数值实验参数,63,7-4-3,二次分配问题的数值实验,算法性能与候选解规模的关系
35、,数值实验表明，在各个规模和各个禁忌表长度参数下，算法性能都与候选解规模呈现出比较明显的关系。,图7-15 不同R值对应的平均结果,64,7-4-3,二次分配问题的数值实验,表7-10 Tai20a的数值实验结果,65,7-4-3,二次分配问题的数值实验,算法性能与禁忌表长度的关系,在各个问题规模和不同的R值水平下，根据数值实验的结果可以确定，在多数情况下T=0.8的性能比T=0.2和T=0.5差，,如图7-16所示。T参数取值位于0.20.5之间可能得到较好的算法性能。,图7-16 不同T值对应的平均结果,66,7-4-3,二次分配问题的数值实验,表7-11 Tai12a 数值实验结果,67
36、,7-4-3,二次分配问题的数值实验,实验结论：通过上述数值实验，可以确定禁忌搜索的几个重要参数的取值区间：候选解规模参数R取值在R=0.50.8，问题规模较大时，用0.5效率较高；禁忌表长度参数取值T=0.20.5，初始解可以选用启发式算法，而邻域解生成方式则用互换式。,本问题及数据来自文献（Sai-On Cheung，Thomas Kin-Lun Tong，Chi-Ming Tam，2002）。该实例对某预制场进行布局规划，将11个设施布局到11个给定的地点上。已知条件为各个产品的重量，加工工艺流程，和各个布局点的坐标位置，数据见表7-12。该问题涉及的设施中有两扇门，以及一个垃圾场。对三
37、者的布局要求是，两扇门和垃圾场必须布局在外围，垃圾场和门不宜靠近。在禁忌搜索算法中，对不符合约束的布局结果予以剔除。,68,7-4-3,二次分配问题的数值实验,表7-12 设施编号和场地位置,69,7-4-3,二次分配问题的数值实验,主要工艺物料流包括：,a)水泥沙石混合物（重量=5）,b)加固（重量=4）,70,7-4-3,二次分配问题的数值实验,c)模料（重量=8）,d)成品（重量=8.5）,71,7-4-3,二次分配问题的数值实验,结合数值实验的结果，禁忌搜索设计参数如下：R=0.5，T=0.5，m=200，候选解规模为11*10*0.5*0.5=27，禁忌表长度为13，采用置换方式生成
38、邻域解。重复运行禁忌搜索十次，与Sai-On Cheung（2002）采用的遗传算法性能比较如表7-13所示：,表7-13 禁忌搜索算法与原有遗传算法比较,解决QAP问题方面，禁忌搜索与遗传算法相比具有较明显的优势。,72,7-5,设施布置软件和仿真工具,73,7-5-1,概述,工厂布置程序经过几十年的发展，出现了一批计算机辅助设施布置的软件和仿真工具，现在设施布置的软件大致有两类：第一类软件帮助企业进行设施的规划和布置设计，如FactoryProgram、FactoryCAD、FactoryPLAN、STORM、SPIRAL等。在这些软件中，FactoryProgram组软件在国际上应用比较
39、普遍。第二类软件包含了仿真和性能分析的功能，如PROMODEL、ARENA、EM-Plant、Witness、Flexsim等，这些软件可用于系统的模拟运行分析。,74,7-5-2,Factory Program工厂布置和物料搬运系统设计工具软件,Factory FLOW在Factory CAD布置图上用图形表示物流，并作分析。Factory PLAN在Factory CAD布置图上用图形表示作业单位关系，并作分析。,FactoryProgram是迄今为止被广泛认同的设施布置软件，这一组设施布置软件包括Factory CAD、FactoryFLOW、FactoryPLAN和Factory OP
40、T等四个模块，每一模块的主要功能如下：,Factory CAD一个强有力的规划和绘图工具，可以将AutoCAD客户化为工业设施的布 置、设计。其余三个模块都在Factory CAD环境中进行操作。,Factory OPT利用从Factory FLOW及 Factory PLAN所得数据，结合图论方法生成初 始AutoCAD布置图。,75,7-5-2,Factory CAD,客户化的AutoCAD软件即Factory CAD。Factory CAD允许固定尺寸的实物图形代表实际尺寸。图面上的工具栏用于普通指令，能产生详细的菜单。Factory CAD允许目标图形可以用二维(2D)或三维(3D)表
41、达。,FactoryFLOW,FactoryFLOW 新版本在其容器存储程序上面的改进大大简化了将容器运送到存储区域和卡车的程序。,FactoryFLOW 是一个间接工作分析工具，它使得工程师能够以材料流通距离、频率和成本为基础优化AutoCAD 或FactoryCAD 工厂布置。,FactoryFLOW提供的无数功能和工具可概括为“观看”和“操作”两大特征。,FactoryFLOW对物流信息有良好的表达，使用可视化表达，能方便用户对物流系统进行深入的理解。,间接工作分析性能的改进使得用户能够分析在材料处理方面所花费的时间和确定能够消除的无价值的多余工作。,Factory Program工厂布
42、置和物料搬运系统设计工具软件,76,7-5-3,Witness仿真软件,Witness软件的主要特点有：,1）采用面向对象的建模机制。2）交互式建模方法。3）提供了丰富的模型进行规则和灵活的仿真。4）可视化、直观的仿真显示和仿真结果输出。5）良好的开放性。,Witness软件使用与现实系统相同的事物组成相应的模型，通过运行一定的时间来模拟系统的行为。模型中的每个部件被称之为“元素(element)”。该仿真软件主要通过如下5类元素来构建现实系统的仿真模型：离散型元素、连续型元素、运输逻辑型元素、逻辑型元素、图形元素等。,离散型元素。离散型元素是为了表示所要研究的现实系统中可以看得见的、可以计量
43、个数的物体，一般用来构建制造系统和服务系统等。主要包括：零部件(part)、机器(machine)、输送链(conveyor)、缓冲区(buffer)、车辆(vehicle)、轨道(track)、劳动者(labor)、路径(path)、模块(module)。,77,7-5-3,Witness仿真软件,运输逻辑型元素。运输逻辑型元素用于建立物料运输系统。主要包括：运输网络(network)、单件运输小车(carriers)、路线集(section)、车辆站点(station)。,连续型元素。同离散型元素相对应，连续型元素用来表示加工或服务对象是流体的系统，比如化工、饮料等。主要包括：流体(flu
44、id)、管道(pipe)、处理器(processor)、容器(tank)。,图形元素。图形元素可以将模型的运行绩效指标在仿真窗口动态地表现出来。主要包括：时间序列图(time series)、饼状图(pie chart)、直方图(histogram)。,逻辑型元素。逻辑型元素是用来处理数据、定制报表、建立复杂逻辑结构的元素，通过这些元素可以提高模型的质量和实现对具有复杂结构系统的建模。主要包括：属性(attribute)、变量(variable)、分布(distribution)、函数(function)、文件(file)、零部件文件(part file)、班次(shift)。,78,7-5-
45、3,Witness仿真软件,一旦在模型中创建了元素，就必须说明零部件、流体、车辆和单件运输小车在它们之间是怎样流动以及劳动者是怎样分配的，这就要用到规则。Witness有几类不同的规则：,劳动者规则。劳动者规则可用来详细说明劳动者的类型和机器，以及输送链、管道、处理器、容器、路线集或者工作站为了完成一项任务而需要的劳动者的数量。,输入规则。输入规则（包括装载和填入规则）。控制输入元素的零部件或者流体的流量以及在系统中的流动过程。,输出规则。输出规则（包括连接、卸载、空闲、单件运输小车进入、车辆进入和缓冲区退场管理）控制从元素中输出的零部件、流体、车辆或者单件运输小车的流量，并控制着当前元素中的
46、零部件、流体、车辆和单件运输小车输出的目的地和数量等。,79,Witness建模步骤如下：,7-5-3,Witness仿真软件,80,7-5-4,Flexsim仿真软件,Flexsim简介,Flexsim是一款离散事件系统仿真环境。已成功地应用在多个领域，特别适合于生产制造，仓储配送，交通运输等物流系统领域。Flexsim启动后的界面如图7-17所示。,图7-17 Flexsim的主窗口界面,81,7-5-4,Flexsim仿真软件,Flexsim基本功能,Flexsim是用来对生产制造、物料处理、物流、交通、管理等离散事件系统进行仿真的环境。Flexsim采用面向对象技术，并具有3D显示功能
47、，建模快捷方便和显示能力强是Flexsim仿真软件的重要特点。该软件提供了原始数据拟合、输入建模、图形化的模型结构、虚拟现实显示、运行模型进行仿真实验、对结果进行优化、生成3D动画影像文件等功能，也提供了与其他工具软件的方便的接口。,图7-18是Flexsim的功能及其构成模块结构图。,82,7-5-4,Flexsim仿真软件,图7-18 Flexsim功能结构图,83,7-5-4,Flexsim仿真软件,Flexsim主要特点,1）基于面向对象技术建模2）突出的3D图形功能3）建模的扩展性强4）友好的开放性,Flexsim提供的建模基本对象,1）资源类（Fixed Resources）,Fi
48、xed Resource类对象一般是仿真模型中的主干对象，此类对象决定了模型的流程。Fixed Resource类对象包括：Source、Queue、Processor、Sink、Combiner、Separator、MultiProcessor、Conveyor、MergeSort、FlowNode、Rack和Reservoir等。,84,7-5-4,Flexsim仿真软件,Visual Object类对象包括：VisualTool和Recorder等。,2）执行类（Task Executer）,Task Executer对象可从Fixed Resource对象中获取并执行任务，如物料搬运或
49、生产操作等。一个Task Executer对象可以向其他Task Executor对象指派任务，或者管理模型中所有的Task Executers对象。Task Executers对象不参与模型中的流程指派。,Task Executer对象包括：Dispatcher、Operator、Transporter、Elevator、Robot、Crane和ASRSvehicle等。,3）网络类（Node）,NetworkNode对象一般用来设定Task Executor对象的行动路线。NetworkNode对象包括：NetworkNode和TrafficControl等。,4）图示类（Visual O
50、bject）,Visual Object类对象可用在仿真模型中显示各种信息、标识、图片或图表等。VisualTool和Recorder对象可用来提高仿真模型的直观感，同时可用来实时显示和搜集模型的输出数据。,85,7-5-5,Extend仿真软件,EXTEND系统仿真软件是一个面向对象的通用仿真平台。适合离散事件系统模拟，连续事件系统模拟、离散和连续混合事件系统模拟。,EXTEND特点,86,7-5-5,Extend仿真软件,EXTEND仿真的基本原理,EXTEND用各种“消息”来计划未来事件、推进模型中的实体、执行内部的逻辑代码、和执行计算。,EXTEND仿真的方法是面向对象建模方法，通过连
