设施规划第7章-设施布置问题求解及其计算机辅助设计和仿真课件.ppt

1、设设施布置施布置问题问题求解及其求解及其计计算机算机辅辅助助设计设计和仿和仿真真7.1 制造系统设施布局的建模分析7.2 计算机辅助设施规划7.3 设施布局数学建模7.4 应用禁忌搜索算法求解二次分配问题7.5 设施布置软件和仿真工具7.6 Flexsim仿真软件的应用案例Chapter 77-1制造系统设施布局的建模分析模型分类模型分类优化目标优化目标约束条件约束条件57-1-1模型分类p 制造系统的布局设计方法可分为图论法和定量分析法两类。图论法是基于对设施尺寸和生产工艺的要求，进行材料流及活动关系分析，形成空间关系图；然后，根据实际可用的面积做出几种布局方案，进行评价择优。定量分析法是指

2、建立布局模型，并应用各种算法对其求解，最终得到一个较优的布局方案。p 建模方法，主要有三类：1)图与网络的方法主要有活动循环图法、关键路径法、Petri网、组合网络等。3)综合方法在设备布局建模过程中，随着面向对象技术的发展与应用，研究者们尝试将其与其他建模方法相融合，如与Petri网结合形成面向对象的Petri网等，降低了Petri网建模和分析的难度，增加了建模的描述能力和功能实现能力。2)数学分析方法此类方法通过建立数学模型对制造系统进行建模，主要有极大代数法、扰动分析法、排队网络法。p 平面布局问题中的有两类主要问题：二次分配问题(Quadratic Assignment Problem

3、,QAP)混合整数规划（Mix Integer Programming）1.提出“搬运矩”的概念2.工作场地面积利用率最大化3.综合考虑传输费用和车间布局面积两个因素4.考虑逆向路程与正向路程对物流的影响不同7-1-2优化目标5.考虑重新布局费用76.考虑定性方面的要求（设备邻接关系、美观性）7.确保物流频率较高的设备相邻布局（局部优化）8.考虑布局后的传输费用及布局费用9.考虑系统的投资效益7-1-2优化目标 在建立设施规划模型时，应将物流运动看作矢量，考虑逆向与正向物流的交叉对物流效率、安全的影响，在将目标函数确定在物流成本最小化的同时，力求降低物流的交叉程度。目前多数文献在建立模型时，目

4、标函数有物流成本（以搬运矩计算）最小化，和布局面积最小化，或者两者的综合。7-1-3约束条件1.边界约束（车间长度和宽度）2.间距约束（设备之间保持一定距离）3.性能约束（不平衡性、稳定性、振动性）4.特定约束（布局安全性）5.资金约束（对于动态布局，布局费用有限制）97-2计算机辅助设施规划计算机辅助设施规划（CAFD）是指在设施规划的过程中充分利用计算机辅助设计相关技术及软件来完成布置建模、运行分析、动画展示及系统优化等工作，相关的选址分析计算、设施布置及参数选择、系统修改等过程都是利用计算机来完成的。p 计算机作为辅助工具，在设施规划中起着十分重要的作用。（2）确定和检测预想的系统设计运

5、行效果。（3）进行敏感性分析，分析出哪个因素的变化对整个操作系统有较大的影响。（4）进行瓶颈分析。规划人员能够发现影响系统流程的瓶颈位置，并对此进行改进。（1）在规划的条件下能够以一定的时间段进行仿真，使设计者能够观察到设计的系统在特殊条件下长时间的运行效果。（5）确定最大化因素。通过最大化因素的确定，规划人员能够确定产生最佳效果的因素相组合，以发挥其最大的功效。（6）能够使一些非正态分布易于理解，不是所有行业中的现象都符合正态分布，软件可以以原始数据为基础，从而为一个特定的情况选择最合适的随机分布，以便能够为这个随机过程制定更为准确的环节。在系统运行之前进行仿真模拟来评价该系统，从而确保计划

6、的可行性。7-2计算机辅助设施规划ALDEP算法算法CORELAP算法算法CRAFT算法算法MULTIPLE算法算法117-2-1ALDEP算法ALDEP（Automated Layout Design Programs，自动化设计法）是一种由凑合法生成布置设计的算法。ALDEP的工作原理十分简单，按照作业单位之间密切程度等级的原理进行工作。ALDEP主要输入的是支持作业单位关系间密切程度等级。ALDEP使用了一种纵向扫描的方法（vertical scan method），如图7-1所示。每一个作业单位视为一等宽条带，其长度由作业单位面积所决定。扫描长度即为场地平面的宽度，扫描宽度可由用户选择

7、，或根据场地平面及安排对象的大小而定。127-2-1ALDEP算法评价设施布置性能的方法是，对各相邻作业单位累加密切程度的赋值，然后得到一个数值再加以比较。下述配置表明赋与数值的一种可能方式：A=43=64 E=42=16 I=41=4 O=40=1 U=0 X=-45=-1024这一过程按布置方案数重复，就能比较其性能孰优孰劣。137-2-2CORELAP算法CORELAP（Computerized Relationship Layout Planning，相互关系法）用长方形的作业单位构造布置。根据对作业单位密切程度的权重赋值即A=6，E=5，I=4，O=3，U=2，X=1。这些数值用以计

8、算各作业单位总密切程度等级TCR(Total Closeness Rating)，即 mjijijrVTCR1（7-1）ijrV是作业单位i和j之间密切程度的赋值TCR表示一个作业单位与另一个作业单位之间的彼此可接受性或喜爱性。在CORELAP中，根据准备放上去的新作业单位和已在图上的将分享共同边界的相邻作业单位之间的权重等级之和，来决定选择对象。由于使用的是确定性方法，CORELAP只产生一个最终布置方案。147-2-2CORELAP算法为设计不同的方案做出不同的独立评价，可改变以下条件：对作业单位密切程度表作些改变1改变权重等级值2改变各作业单位面积的大小3改变布置的比例4改变长度和宽度比

9、值5综合改变上述数项6157-2-3CRAFT算法CRAFT（Computerized Relative Allocation of Facilities Technique，位置配置法）是一种单阶段布局算法。CRAFT是基于物流信息或者从至表中累加的作业单位物流强度的。因此CRAFT是一种定量布置方法。CRAFT是一种改进程序，这意味着CRAFT接受一项初始布置设计并用顺序方式成对交换作业单位的位置，试图做出改进。在与其他设计方案比较决定某一布置设计是较好的方案时，CRAFT用物品搬移或运输成本作为评价标准，此成本用移动距离的线性函数来表达。所以，一项较好的设计是搬移成本较低，一项优化设计可

10、能是搬移成本最低的设计。n 图7-2是包括4个作业单位A、B、C和D的布置设计。为了简化计算，假设物料运输只发生在4个作业单位的中心之间并沿着长方通道运行。图7-2 应用CRAFT的初始布置设计167-2-3CRAFT算法1）被搬运物料的种类(如粗糙的还是易碎的，轻巧的还是笨重的)。2）每一往返行程中单元载荷的数量。3）每一周期中往返行程的数量。4）物料搬运设备的类型(如普通设备还是专用设备等)。p 在给定的布置下所有作业单位之间的距离均可知，为了计算物料搬运或运输成本，另一主要数据来自：某一布置设计的总成本是两张从至表之间的距离和权重乘积之和。p 所有这些数据或信息都能合计为两个作业单位之间

11、的权重（或 ），现有两张ijW从至表中一个为两个作业单位i和j之间的距离，另一个为有关 的从至信息，ijWp CRAFT的解题过程是，用作业单位之间成对交换的方法来设法改进设计，视成对交换的结果是否有更好的布置设计出现。然而CRAFT的一项限制使这种交换只能在相邻的作业单位之间进行，根据这一简单理由CRAFT执行互换，互换时不考虑面积，布置方案决定后再为各作业单位加上面积。177-2-3CRAFT算法 在产生5个新的布置方案后，比较各方案的总成本。如果这些新方案的成本都较原方案高，显然就不予考虑。如对布置的改进可降低总成本就应进一步考虑。假设作业单位A和D相互交换可得最佳改进，其交换结果如图7

12、-3所示，值得注意的是这一交换过程引起作业单位的形状非常不规则。图7-3 CRAFT的布置设计经交换的结果p CRAFT是一个优化的算法，是各作业单位之间使总物料搬运最少或运输成本最小化的结果。这一算法与为解决二次分配问题(QAP)的陡速下降成对交换过程紧密联系，所以可以把CRAFT产生的布置设计提供给布置设计人员作为一个评价标杆(Bench Marking)，然而由于CRAFT算法简单，对于解决大型问题的作用非常有限。187-2-4MULTIPLE算法MULTIPLE算法（Multi-floor Plant Layout Evaluation，多层楼房设施布置设计）是CRAFT的改进型，它已

13、商业化并被称作为layOpt的布置设计软件包。在单层楼房设施布置的基础上。MULTIPLE已开发了多层楼房设施布置设计程序，像CRAFT一样，MLLTIPLE使用物流信息、目标函数和搜索程序。MUTIPLE用优化程序产生改进的布置方案，与CRAFT不同，它没有在非邻接作业单位之间不能交换的限制，所以允许任何作业单位位置作双向交换。MULTIPLE算法的主要特征是采用空间填充曲线用以构造布置，以及用以表示作业单位布置的空间。197-3设施布局数学建模研究布置问题的最主要目标是实现时间或成本的最小化。首先我们需要将布置问题建模，然后用合适的算法求解这一模型。为设施建模，最基本最简单的模型就是单行布

14、置(Single-row layout)和多行布置（multi-row layout）的模型。为了开发能在合理时间内解决问题的模型，需要作些假设。在许多应用中这些假设是可以接受的，因为所得的最终解决方案是可以修改的。但在有些情况下为反映实际情况而修改解决方案可能引起目标函数剧烈的变化，以致模型中的假设可能有缺陷而不能接受。207-3设施布局数学建模单行布置问题模型单行布置问题模型ABSMODEL1模型模型不等面积设施的多行布置模型不等面积设施的多行布置模型ABSMODEL3模型模型二维布局分析二维布局分析二次分配模型二次分配模型混合整数规划模型混合整数规划模型多行布局的混合整数规划模型多行布局

15、的混合整数规划模型217-3-1单行布置问题模型p 在讨论单行布置问题的非线性模型ABSMODEL1时，先作如下假设：设施形状是方形或长方形，均为已知。设施排列在一直线上。设施方位是已知的。第1个假设：许多布置问题尽管设施既非标准的正方也非长方，但通常可近似视为正方或长方，如图7-4所示。这种近似法大大简化了建模过程，同样也简化了解题过程。图7-4 非正方、非长方设施形状的近似 第3个假设：在许多制造系统中，机器设备的方位是使装卸点面向通道以便于装卸零件，由于机器设备上装卸毛坯的位置是固定的，所以它的布置方位实际上是已知的。227-3-2ABSMODEL1模型p 先介绍ABSMODEL1模型中

16、各参数的符号：为设施中心与垂直参考线(VRL)之间的距离。p 设决策变量为设施中心与垂直参考线(VRL)之间的距离。ix图7-5 单列布置中各变量与决策变量的表示237-3-2ABSMODEL1模型p ABSMODEL1模型的目标函数为111minmimijjiijijxxns（7-2）p 约束条件s.t.为ijjijidhhxx211,3,2,1mimij,1（7-3）ABSMODEL1模型可以用公式表示成等长度和不等长度设施的布置问题。在此模型中非负的约束条件并非必需。在垂直维度中不考虑重叠约束，隐含假设所有设施中心的垂直坐标都是相同的。247-3-2ABSMODEL1模型p 虽然建筑物尺

17、寸在模型中考虑为无限大，在最优解中也不会远离、分散。假如建筑物水平方向尺寸已知，而用户需要将位于水平坐标内的约束包含在内，即加上如下约束iihxhH2121mi,3,2,1（7-4）p 为设施i的中心和VRL之间的距离，即使当设施在左右极端位置上时，约束式(7-4)也会被满足，这可由图7-6加以验证。x图7-6 对不等设施长度问题一个可行的单行布置257-3-2ABSMODEL1模型p 通常非线性规划(NLP)问题的优化解是难于找到的。不像线性规划(LP)，一个NLP问题的可行域不需要一个凸集，即使是一个凸集，对一个NLP问题不需要在可行域上有一个极点。这样对一个一般的NLP问题而言，寻找一个

18、优化解似乎是不可能的。然而有一些NLP问题的特殊情况，寻找一个优化解相对容易一些。2.在另外一些NLP问题中，一个凹形目标函数可以最大化，而其可行域由一个凸集约束所定义，或者相反一个凸形目标函数可以最小化，而其可行域由一个凹集约束所定义。1.在一些无约束的NLP问题中，一个凹形目标函数可以最大化，或者一个凸形目标函数可以最小化p 例7-1 一家修理电视和VCD的修理店准备扩大业务范围，修理其他电子消费产品，包括电脑及其周边设备、微波炉、音响系统等，店中也准备出售相关附件及零配件。去年店主收到无数抱怨，原因有店内拥挤阻塞、零件及修理单错放、修理质量低劣等问题。店主凭借经验，认为只要在现有空间中重

19、新布置设施，房间拥挤和质量问题就能改进。于是招募了4名IE专业的高年级学生组成团队用改进设施布置的办法来解决问题。267-3-2ABSMODEL1模型（2）虽然修理技术员共享一些仪器设备，但其他仪器设备往往是某一个技术员用得较多。（3）生产中的使用面积为23m5m。（4）现有布置应如图7-7a所示。p 学生团队在对该店进行观察和搜集数据后，归纳出以下几点情况：（1）公司第一个技术员负责修理电视和VCD，第二个负责修理微波炉，第三个修理音响 系统，第四个修理电脑。图7-7 修理店现有布置及改进p 改进后的布置如图7-7b所示。277-3-2ABSMODEL1模型 学生小组在一个工作日认真观察了每

20、一对房间之间的交互作用、相互影响。这种相互作用和影响取决于一个技术员（如音响技术员），应用一些主要被其他技术员（如电脑技术员）使用设备的频繁程度。这种交互作用显示在图7-8所示的往复行程矩阵（ijn）中。学生小组根据用于每一房间的仪器设备决定房间的尺寸大小，并决定每一技术员需要的工作面积。按照每一房间的用途和编号，其尺寸列于图7-8中。30203106200104826412020812ijf房间编号放置设备名称面积（m*m）1电视/VCD6*32音响3*33微波炉3*34电脑6*35零部件4.6*3图7-8往复行程矩阵和五个房间的大小287-3-2ABSMODEL1模型p 解：使设施长度平行

21、于建筑物长度方向，因为往复行程矩阵是对称的，即jiijaa 如此矩阵不对称，要使其对称化。包含在人员走动中的成本与行程距离直接成正比。因为设施是每间房间，不需要房间之间留出间隙距离。这一模型在非负约束等条件下，可得每一个房间中心相对于VRL的水平坐标值为：X1=33,X2=48,X3=58,X4=73,X5=90图7-7 修理店现有布置及改进297-3-3不等面积设施的多行布置模型关于多行布置问题有仪表板布置问题，自动化制造系统中机器设备的布置问题，各种键盘设计和办公室布置设计等。已为明确地表达这些问题开发了各种模型如ABSMODEL1模型，ABSMODEL3模型，二次分配问题(QAP)，线性

22、混合整数规划模型，以及在目标函数和约束中有绝对项的非线性模型等。ABSMODEL2是假设面积为相等的设施的布置模型，对多数实际布置问题来说这种假设是不现实的，所以这里只介绍ABSMODEL3模型。ABSMODEL3模型采用一种折衷的办法，即先在模型中给定一个假设的方位，进而不断测试解的结果，然后根据结果来修改原始方位，再来求解模型。这一过程不断重复，直到所获布置中的机器都有满意的方位为止。ABSMODEL3模型也包括目标函数，以及约束中含有绝对项。在ABSMODEL3中，假设设施是方的或长方形，并且其方位事先已知。307-3-4ABSMODEL3模型p 先介绍ABSMODEL3模型中各参数的符

23、号：317-3-4ABSMODEL3模型图7-9不等面积多行布置决策变量和参数图示327-3-4ABSMODEL3模型p 目标函数为：111minmimijjijiijijyyxxns（7-5）p 约束条件为 ijjiijjidhhhMzxx211,3,2,1mimij,1（7-6）ijjiijjidvvvzMyy2111,3,2,1mimij,1（7-7）01ijijzzmij,11,3,2,1mi（7-8）337-3-4ABSMODEL3模型 ABSMODEL3模型的优点是直观、方便、容易理解，并能用简单的启发式解题；主要缺点是要求设施的外形只能是方形或长方形，还要假定已知设施的方位，要放

24、松这一约束就要为增加复杂性而付出代价。因为模型ABSMODEL3是非线性的，因而其解经常是次优的或远离优化。对于真正在实际中应用的多行布置模型，除ABSMODEL3外还有和其相当的二次分配问题(QAP)。QAP从传统上说早已用于研究和解决布置问题，从深度和广度来说更胜一筹。347-3-5二维布局分析物料流动的方向相互垂直，或者刚好相反，就形成物流交叉。为了物流系统的效率、安全，进行设备布局时，一般希望尽可能减少物流交叉。在一个复杂的物流系统中，可能出现大量的物流交叉，不同的布局会带来不同的交叉程度。这里考虑模型的主要特点，是在保持物流交叉较小的前提下，最小化物流成本。对于二维布局，这里人为规定

25、横向和纵向两个物流方向，同时，规定向右和向下分别为顺流方向，向左和向上分别为逆流方向。物流成本=系数*物流距离*物流重量，其中系数包括CX1、CX2与CY1、CY2，其意义分别如下：CX1：横向顺流成本系数CX2：横向逆流成本系数CY1：纵向顺流成本系数CY2：纵向逆流成本系数 通过系数CX1、CX2与CY1、CY2调整物流成本时，系数绝对值越大，相应物流成本值越高，数学模型目标函数最小化物流成本，则可排除因物流交叉导致的高成本方案，从而得到较低的物流交叉水平上的低物流成本方案。由于逆向物流用负数表示，CX2和CY2也取负值，使成本为正值。357-3-5二维布局分析p 数学模型求解和计算物流成

26、本时，不同的系数设置可产生不同的设备布局结果。1)不考虑物流交叉影响的取值CX1=1，CX2=-1；CY1=1，CY2=-1；2)提高纵向物流的成本，减少纵向物流 CX1=1，CX2=-1；CY1=3，CY2=-3；3)提高逆向物流的成本，减少逆向物流 CX1=1，CX2=-4；CY1=1，CY2=-4；4)以上两种的综合 CX1=1，CX2=-3；CY1=2，CY2=-6；p 例7-2 某车间有六台设备组成的生产线，设备编号为16，设备形状为矩形，布局方位已知，其长分别为50,150,80,30,40,30，宽分别为40,60,50,20,30,30，横向、纵向安全距离为10，主要生产两种产

27、品A和B，A的生产工艺为1-2-3-4-5-6，B的生产工艺1-5-6，A、B产品的重量之比为2：5，顺流方向为从左到右，从上到下。367-3-5二维布局分析表7-1 不同系数设置下的布局结果377-3-6二次分配模型二次分配问题（quadratic assignment problem，QAP）是一个典型的组合优化问题，它在选址规划、集成电路设计、图像处理、键盘布局和作业调度等众多领域有广泛的 nnijaA应用。给定两个矩阵和nnlkbB，QAP问题就是要寻找一个整数集n,2,1的置换 n,2,1，使式（7-9）的值最小：ninjjiijbaz11,（7-9）387-3-6二次分配模型u 一

28、维模型图7-10 一维布局模型 设备在一维方向上排列，物流成本与搬运距离，搬运次数和重量的乘积成正比；设备的大小和形状相同，为矩形；搬运距离为设备中心点的距离；逆向物流的成本高于顺向物流的成本。397-3-6二次分配模型p 参数：p 决策变量：407-3-6二次分配模型p 目标函数：p 约束：41u 二维模型7-3-6二次分配模型图7-11 布局问题的二次分配模型427-3-6二次分配模型假设：设备在二维方向排列，物流成本与搬运离，搬运次数和重量的乘积成正比；物流搬运距离为设备间的曼哈顿距离；逆向物流的成本高于顺向物流的成本。p 参数：437-3-6二次分配模型p 决策变量：p 目标函数：44

29、p 约束：7-3-6二次分配模型457-3-7混合整数规划模型 在条件方面，混合整数规划模型没有给定布局点，而是给定整个平面区域，要求布局于其间的设备物流成本低，且相互没有干涉；在结果方面，二次分配问题的解是设备与布局点的映射关系，是离散值，不考虑与面积相关的因素，混合整数规划的结果是设备的坐标，是连续值，即考虑各个设备的形状、面积使其没有干涉，目标函数也常常重视布局结果占用的面积大小，规划结果如图7-12所示：图7-12 混合整数规划模型467-3-7混合整数规划模型假设条件：设备形状抽象为矩形，设备摆放方向已知；布局平面为矩形区域。p 参数：477-3-7混合整数规划模型p 决策变量：p

30、目标函数：48p 约束：7-3-7混合整数规划模型497-3-8多行布局的混合整数规划模型 许多实际的布局问题，不仅对设备的大小和安全距离有要求，对其摆放位置也有所限制。在柔性制造系统中，车间平面被划分为若干子区域，然后在这些子区域上布置所有设备，设备间保持安全距离并不与边界干涉；车间的物流路线仍然按照曼哈顿距离计算。由于这些要求普遍存在于柔性系统的设施布局中，可以把它们归为多行布局的混合整数规划问题（Multi-row Mix Integer Programming，MMIP），如图7-13所示。图7-13 多行布局的混合整数规划模型507-3-8多行布局的混合整数规划模型假设条件：设备形状

31、抽象为矩形，设备摆放方向已知；布局平面为矩形，被划分为 若干行，各行长度相同；p 参数：517-3-8多行布局的混合整数规划模型p 决策变量：p 目标函数：527-3-8多行布局的混合整数规划模型p 约束：537-4应用禁忌搜索算法求解二次分配问题生成初始解的启发式算法生成初始解的启发式算法解的编码和生成步骤解的编码和生成步骤二次分配问题的数值实验二次分配问题的数值实验u 本节集中讨论禁忌搜索算法实现过程中两个比较关键的问题：初始解的构造，和解的编码和生成方式。547-4-1生成初始解的启发式算法p 构造启发式算法的基本思路是，将较大的物流量与较小的物流距离相乘，较小的物流量与较大的物流距离相

32、乘，这样使得乘积的总和最小。p 最理想的情况是，物流量按从大到小依次排列，物流距离按从小到大依次排列，但实际情况中这样的情形很少出现。不失一般性，取以下6*6数据为例说明：557-4-1生成初始解的启发式算法Flow012345Dist012345002785211500219582564110805821761044407579203482920841210307445306956407740395050表7-2 物流量矩阵 表7-3 距离矩阵 为了保证已被分配的设施或位置不被重复分配，本启发式算法分为选择和删除两步重复执行：1）遍历当前Flow/Dist表，选择表中的最大/最小值；2）删除

33、该值所在的行和列的数据，以及此行数/列数对应的列/行的数据；重复1)、2)步骤，若当前表为空则停止。567-4-1生成初始解的启发式算法 由此步骤得到新的Flow序列过程为：选取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所示。Flow012345Flow1345Flow1300278521151058217610581080582176307445302034829407730744550407750表7-4 选择最大值85 表

34、7-5选择最大值77 表7-6选择最大值58 577-4-1生成初始解的启发式算法 由此得到设施序列0 2 4 5 1 3；同理得到三个距离值10，21，69，和位置序列2 5 0 1 3 4，将设施与位置一一对应，得到初始解，如表7-7所示。位置012345设施450132表7-7 一个初始解587-4-2解的编码和生成步骤u QAP问题QAP问题的解是设备与位置之间的映射，同一个解可以有两种等价的表达方式：基于设备次序的表达法和基于位置次序的表达法。下表中左边的（4 2 5 3 6 0 1）与右边的（5 6 1 3 0 2 4）等价。统一编码标准后，用长度为n的编码，即可表达一个设备布局的

35、解。设备0123456 位置0123456位置4253601设备5613024表 7-2 两种编码方式597-4-2解的编码和生成步骤u MMIP问题 QAP问题的解是离散的，而MMIP的解可以取连续值，理论上具有无穷多个解，因此简单地搜索解空间是不可行的，一类方法对该问题进行了简化，使得各台设备之间保持最小的安全距离，而不再进行细节的调整；而另一类方法，将设备之间的间距作为编码的组成部分，每一次迭代搜索，对这些间距进行分配和调整。相比而言，前者过于简化的做法，可能对算法结果的优化程度有所影响；而后者不仅增加了编码的复杂程度，每一次迭代搜索均要对间距进行操作，对计算复杂程度影响较大。为了达到两

36、个方面的平衡，将解的生成过程分为两大步骤：607-4-2解的编码和生成步骤第一步是按照最小安全距离原则布局。在最小安全距离原则下，要表示一个分行布局，一个编码必须分两部分信息，设备的摆放顺序，和分行位置信息。图7-14 多行布局模型图7-14中，按照位置次序表达法，该解可以表示成（3 5 8 6 2 0 4 1 7 9|4 3 3）；每次通过移动而生成新的邻域解时，不仅要变更前n位设备的编号，也要重新计算各行的设备数。617-4-2解的编码和生成步骤第二步骤是微调。微调时涉及到适配值阈值（1），长度阈值和精度p三个值。（3）以精度值p为基本单位，将剩余长度分割成片段，将这些片段分配到该行各个设

37、备的间隔之间。微调按照下述步骤进行：（1）按照最小安全距离原则布局之后，计算适配值。在成本最小化模型中，如果适配值大于当前最优值的倍，则以当前适配值作为最终适配值，放弃微调，否则：（2）计算该布局各行的剩余长度。如果剩余长度都不大于设定的长度阈值，则放弃微调，否则转入步骤（3）：阈值，、精度p的大小，片段的分配方式，对微调运算发生的次数、计算的复杂度和结果的精度均有直接的影响。该方法的优点在于，减少了精确求解的次数，仅仅在同时满足两个阈值的时候，才真正开始微调运算；微调运算的分配方式可以是随机分配，也可以是枚举；可以人为控制微调运算的精度。627-4-3二次分配问题的数值实验为了使结论具有一定

38、的可信度，本节实验数据均来自QAP问题的权威网站QAPLIB（http:/www.opt.math.tu-graz.ac.at/qaplib/），选取5个不同规模的问题进行实验，分析其性能与参数设置的关系。p 实验参数包括问题规模、候选解规模、禁忌表长度、迭代次数、初始解生成方式、邻域解生成方式。参数参数水平数水平数取值取值问题规模n4（12，20，50，80）候选解规模参数R3（0.2，0.5，0.8）*邻域解数量禁忌表长度参数T3（0.2，0.5，0.8）*候选解数量迭代次数m5（25，50，100，200，400，800）邻域解生成方式3（互换式，嵌入式，并行式）初始解生成方式2（随机式

39、，启发式）表 7-9 数值实验参数637-4-3二次分配问题的数值实验u 算法性能与候选解规模的关系数值实验表明，在各个规模和各个禁忌表长度参数下，算法性能都与候选解规模呈现出比较明显的关系。图7-15 不同R值对应的平均结果647-4-3二次分配问题的数值实验禁忌表长度参数迭代次数mR=0.2R=0.5R=0.8T=0.22575403073746374112150741965729863737056100734773725045725067200726121718650719420400723312714171715272800718439712563712614T=0.525749646

40、73955474442050743737728904737794100731273720535725690200725431719137719879400719672714151719064800721792711231715428T=0.82575007373330073685950742492734243734665100733782726619727090200730303717248719374400722896717611718469800719920711760715331表7-10 Tai20a的数值实验结果657-4-3二次分配问题的数值实验u 算法性能与禁忌表长度的关系 在各

41、个问题规模和不同的R值水平下，根据数值实验的结果可以确定，在多数情况下T=0.8的性能比T=0.2和T=0.5差，如图7-16所示。T参数取值位于0.20.5之间可能得到较好的算法性能。图7-16 不同T值对应的平均结果667-4-3二次分配问题的数值实验候选解规模迭代次数mT=0.2T=0.5T=0.8R=0.22524723524884624601050242157242478244367100239661237324238132200237697236896235448400231536232596232966800228633230526232067R=0.52523814324314

42、823712750233886234058236985100232033232783234399200226593229364230301400228158226770230215800226697224883227284R=0.82524205123778223877250234246237452236957100229359230992233092200226101230453231735400225351227165229774800225044225980227870表7-11 Tai12 a a 数值实验结果677-4-3二次分配问题的数值实验p 实验结论：通过上述数值实验，可以确定

43、禁忌搜索的几个重要参数的取值区间：候选解规模参数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。该问题涉及的设施中有两扇门，以及一个垃圾场。对三者的布局要求是，两扇门和垃圾场必须布局在外围，垃圾场和门不宜靠近。在禁忌搜索

44、算法中，对不符合约束的布局结果予以剔除。687-4-3二次分配问题的数值实验编号编号设施设施场地编号场地编号X XY Y1主门115402边门213303分批车间322304钢材存放场425205模料存放场520106弯曲加工场612107水泥石沙堆置场740108固结场848209垃圾场9483510铸造场1022011吊装场113242表7-12 设施编号和场地位置697-4-3二次分配问题的数值实验u 主要工艺物料流包括：a)水泥沙石混合物（重量=5）b)加固（重量=4）707-4-3二次分配问题的数值实验c)模料（重量=8）d)成品（重量=8.5）717-4-3二次分配问题的数值实验p

45、 结合数值实验的结果，禁忌搜索设计参数如下：R=0.5，T=0.5，m=200，候选解规模为11*10*0.5*0.5=27，禁忌表长度为13，采用 置换方式生成邻域解。重复运行禁忌搜索十次，与Sai-On Cheung（2002）采用的遗传算法性能比较如表7-13所示：对照内容遗传算法禁忌搜索算法设置的迭代次数1673200初始解适配值122362172400找到的最优适配值9978892758找到的最优解11096851137425796110831124找到该适配值时的迭代次数673小于200表7-13 禁忌搜索算法与原有遗传算法比较 解决QAP问题方面，禁忌搜索与遗传算法相比具有较明显

46、的优势。727-5设施布置软件和仿真工具概述概述Factory Program工厂布置和物料搬运系统设计工具软件工厂布置和物料搬运系统设计工具软件Witness仿真软件仿真软件Flexsim仿真软件仿真软件Extend仿真软件仿真软件其他软件工具其他软件工具737-5-1概述p 工厂布置程序经过几十年的发展，出现了一批计算机辅助设施布置的软件和仿真工具，现在设施布置的软件大致有两类：第一类软件帮助企业进行设施的规划和布置设计，如FactoryProgram、FactoryCAD、FactoryPLAN、STORM、SPIRAL等。在这些软件中，FactoryProgram组软件在国际上应用比较

47、普遍。第二类软件包含了仿真和性能分析的功能，如PROMODEL、ARENA、EM-Plant、Witness、Flexsim等，这些软件可用于系统的模拟运行分析。747-5-2Factory Program工厂布置和物料搬运系统设计工具软件Factory FLOW在Factory CAD布置图上用图形表示物流，并作分析。Factory PLAN在Factory CAD布置图上用图形表示作业单位关系，并作分析。p FactoryProgram是迄今为止被广泛认同的设施布置软件，这一组设施布置软件包括Factory CAD、FactoryFLOW、FactoryPLAN和Factory OPT等四

48、个模块，每一模块的主要功能如下：Factory CAD一个强有力的规划和绘图工具，可以将AutoCAD客户化为工业设施的布 置、设计。其余三个模块都在Factory CAD环境中进行操作。Factory OPT利用从Factory FLOW及 Factory PLAN所得数据，结合图论方法生成初 始AutoCAD布置图。757-5-2u Factory CAD 客户化的AutoCAD软件即Factory CAD。Factory CAD允许固定尺寸的实物图形代表实际尺寸。图面上的工具栏用于普通指令，能产生详细的菜单。Factory CAD允许目标图形可以用二维(2D)或三维(3D)表达。u Fa

49、ctoryFLOW FactoryFLOW 新版本在其容器存储程序上面的改进大大简化了将容器运送到存储区域和卡车的程序。FactoryFLOW 是一个间接工作分析工具，它使得工程师能够以材料流通距离、频率和成本为基础优化AutoCAD 或FactoryCAD 工厂布置。FactoryFLOW提供的无数功能和工具可概括为“观看”和“操作”两大特征。FactoryFLOW对物流信息有良好的表达，使用可视化表达，能方便用户对物流系统进行深入的理解。间接工作分析性能的改进使得用户能够分析在材料处理方面所花费的时间和确定能够消除的无价值的多余工作。Factory Program工厂布置和物料搬运系统设计

50、工具软件767-5-3Witness仿真软件p Witness软件的主要特点有：1）采用面向对象的建模机制。2）交互式建模方法。3）提供了丰富的模型进行规则和灵活的仿真。4）可视化、直观的仿真显示和仿真结果输出。5）良好的开放性。Witness软件使用与现实系统相同的事物组成相应的模型，通过运行一定的时间来模拟系统的行为。模型中的每个部件被称之为“元素(element)”。该仿真软件主要通过如下5类元素来构建现实系统的仿真模型：离散型元素、连续型元素、运输逻辑型元素、逻辑型元素、图形元素等。离散型元素。离散型元素是为了表示所要研究的现实系统中可以看得见的、可以计量个数的物体，一般用来构建制造系