模拟退火算法在动态设施布置中的应用研究

1、模拟退火算法在动态设施布置中的应用研究摘要制造业必须以运营效率和快速的反响适应产品的复杂化和需求。讨论了对消费部门间制造设施的布置和重组，以使物料搬运和重组本钱最小化，进而提出动态设施布置问题及资源的有效组合和配置，确保设施间的物流通畅和进步企业消费效率。关键词模拟退火启发式动态设施布置静态设施布置问题statifailitylayutprble，SFLP被认为是解决设施布置的有效方法。资源如机器、部门或者劳动力的有效组合和配置，可以确保设施间的物流通畅和进步企业消费效率。当设施间的物流量在布置范围内变化时，SFLP就成了动态。这就是由Rsenblatt首次提出的著名的动态设施布置问题dyna

2、ifailitylayutprble，DFLP。启发式算法成功开展之前，曾经用禁忌搜索技术、遗传算法等工具来求解大型组合优化问题。换言之，就是利用最速下降成对交换启发式steepest-desentpairiseexhangeheuristi从初始解开场产生邻域解。通常这类启发式的时间效率不高，并且只收敛于部分最优。为了克制这些缺陷，本文提出用模拟退火启发式解决DFLP最优问题，用固体退火的思想来承受邻域解，以免陷入部分最优。1DFLP的根本思想企业随着市场的变化而调整其设施布置，本文称其为柔性布置。DFLP就是以将来的可预测变化为根底的。预期的将来可以划分为很多区段，这些区段可以定义为周、月

3、甚至是年。研究动态设施布置问题时，设每一区段的流量数据是可预测和连续的，那么设施布置问题中的每个区段，可以用SFLPQAP进展解决。DFLP的布置规划是以可预测将来为根底的一系列布置，每个布置规划跟每个区段有关。在布置过程中，在原有根底上对设施的挪动而产生的本钱称为再布置本钱，设施的再布置可能导致产品的损失，还可能需要专业人员和专门的设备。因此，再布置本钱由劳动力本钱、设备本钱和产品损耗本钱组成；另外，对制造设施来说，在设施间还要对物料进展搬运以满足设施加工的需要，搬运物料所投入的本钱，称为物料搬运本钱。本钱的大小由设施间物料的流量以及设施间的间隔 决定，它是决定布置是否合理的最重要的衡量标准

4、，一般占总运作本钱的20%50%，占产品制造本钱的15%70%，这成为设施布置中需要考虑的重要指标。因此，布置规划的总本钱由所有区段的物料搬运本钱和与再布置本钱之和组成。布置规划的目的是使搬运本钱与再布置本钱之和到达最校在这过程中，须重复交换部门间的位置以满足上述要求，当物料搬运本钱大于再布置本钱时，可以把DFLP看作一系列的SFLPsQAPs来求解。附图所示是具有6个设施在3个区段的DFLP事例。在第一区段，设施1、2、3、4、5和6分别被安置在位置3、4、1、5、2和6，由于设施3和5在第2区段被分配到不同的位置即分别在位置2和1，那么其再布置本钱就是把设施3挪动到位置2所产生的本钱与把设

5、施5挪动到位置1所产生的本钱之和。另外，在布置中，由于在阶段2和在阶段3的布置是一样的，故在阶段3中没有再布置本钱。为了操作方便，可以对DFLP进展如下的假设：设施间的流量是动态而确定的deterinisti，设施的面积和位置的大小一致，布置类型为的即如附图为23的布置；部门之间的间隔 确定为一个单位。关于DFLP问题的求解，本文在Urban提出的最速下降成对交换启发式解法之上，提出用一种通用的模拟退火算法和最速下降成对交换相结合的启发式算法来求解DFLP的最优化问题。2模拟退火算法模拟退火SiulatedAnnealing，SA算法的思想最早是由N.etrplis等人在1953年借鉴统计力学

6、中物质退火方法而提出的。其思想观念来自固体的退火过程，加热固体至最高温使之溶化，冷却时，液体中原子的热运动渐渐减弱，随着温度的徐徐降低，原子运动渐趋有序，到达固体的最低能量状态或者基态。根据etrplis准那么，粒子在温度T时趋于平衡的概率为e，其中E为温度T时的内能，E为其改变量，k为Bltzann常数。1982年，Kinkpatrik等人首次用模拟退火算法解决组合优化问题，将内能E模拟为目的函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法。由初始解i和控制参数初值t开场，对当前解重复“产生新解-计算目的函数差-判断是否承受-承受或舍弃的迭代，并逐步衰减t值，算法终止时的

7、当前解即为所得近似最优解。下面给出模拟退火算法的根本步骤：1给定模型每一个参数变化范围，在这个范围内随机选择一个初始模型0，并计算相应的目的函数值E(0)。2对当前模型进展扰动产生一个新模型，计算相应的目的函数值E()，得到E=E-E0。3假设E0，那么新模型被承受；假设E0，那么新模型按概率P=exp-E/T进展承受，T为温度。当模型被承受时，置0=，E0=E。4在温度T下，重复一定次数的扰动和承受过程，即重复步骤2、3。5缓慢降低温度T。6重复步骤2、5，直至收敛条件满足为止。3DFLP中的模拟退火启发式解法转贴于论文联盟.ll.3.1参数设置1承受新布置的概率确定。用模拟退火算法来解决DFLP的最优化问题，首先要确定的是承受新布置的概率。承受概率如下：PT=expT