论文 基于O-tree编码和模拟退火算法的物流驱动设施布置模型及算法研究.docVIP

基于O-tree编码和模拟退火算法的物流驱动设施布置模型及算法研究 摘要： 在采用计算智能算法的设施布置算法中，有效的布置表示是随机有哪些信誉好的足球投注网站算法能够有效的产生高质量布置解的关键，为此，借鉴VLSI物理设计中的相关思想，提出了一种有效的基于有序树（Ordered tree,O-tree）结构的设施布置编码表示法。在O-tree表示的基础上，根据布置、约束图和O-tree的相互关系，给出了获得以面积利用率为目标函数的基本布置解的确定性算法。在此基础上，进一步提出了以O-tree编码作为编码采用算法扰动O-tree以获得物流驱动的优化布置解的求解方法。最后，通过仿真试验验证了基于O-tree编码的设施布置表示及实现算法的有效性和可行性。 关键词：设施布置；O-tree；算法；物流 Simulated Annealing Algorithm Abstract: Among infrastructure layout algorithm adopting computational intelligence arithmetic, the valid layout representation is the key for random optimization approach to obtain the layout resolution. A representation of infrastructure layout is presented based on O-tree structure referring to some approach of IC layout design. A deterministic algorithm to obtain better area utilization ratio is also developed according to interrelation of the layout, its constraint graph and the corresponding O-tree. A Simulated Annealing Algorithm with O-tree as its gene coding is further proposed to find optimized logistics driven infrastructure layout solution by systematically perturbing the O-tree. Empirical results show the efficiency and feasibility of the infrastructure layout coding representation and corresponding algorithm. Key Words: Infrastructure layout; Ordered tree; Simulated Annealing Algorithm; Logistics 1引言 设施布置设计在设施规划设计中占有重要地位。它是指根据企业的经营目标和生产纲领，在已确认的空间场所内，按照从原材料的接收、零件和产品的制造、产品的包装、运输等全过程，力争将人员、设备和物料所需要的空间做最适当的分配和最有效的组合，以获得最大的经济效益[1]。通常设施布置包括工厂总体布置和车间布置。其中工厂总体布置设计主要解决工厂各个组成部分，尤其是物流相关因素，包括各种作业单位和运输通道等的相互位置关系；而车间布置设计则解决车间内各单元的相互位置关系。设施布置的好坏直接影响整个企业系统的物流、信息流、生产能力、生产率，生产成本以及生产安全。其布置过程就是在满足一定规则条件下在一个有限平面内寻找设施间最理想组合的过程，规则可以定义为一定的优化目标，比如有效利用空间和物料搬运费用最少等，因此可以将设施布置问题转化为一个组合优化问题。其实质是一个寻找最优解的过程，因此又可以转化成对合法构形空间的有哪些信誉好的足球投注网站问题。 通常，许多设施布置问题都可归结为NP困难的优化问题。随着工业技术的发展，设施布置问题的规模变得越来越大，问题空间维数随之剧增，传统优化算法面临计算量爆炸、易陷入局部极值等困难，不能有效地解 决问题。而近年来出现的许多计算智能优化算法，如神经网络、模糊逻辑、遗传算法、模拟退火算法等，则已展现出其解决此这类问题的巨大潜力。虽然这些优化算法的目标是寻求满意解或者次优解，但是由于算法效率高，收敛性能好，依然得到广泛的应用，成为设施布置研究中的热点课题。在设施布置算法中，布置的表示是对有效地产生和评估可行解的一个关键的因素。但目前业界的研究往往专注于使用计算智能算法来解决工厂布置问题，对布置表示