第2卷第1期 智能系统学报 Vol.2 Ng 1 2007年2月 CAAI Transactions on Intelligent Systems Fcb.2007 基于单亲遗传算法的动态设备布局仿真研究 李波，邱枫 (天津大学管理学院，天津300072) 摘要：针对柔性生产环境下的设备布局问题，提出了一种基于单亲遗传算法原理的启发式算法.发展了一种新颖 的适用于动态设备布局的遗传换位操作算子，并提出在单期布局编码子串上应用换位概率的策略，增加了种群的多 样性.Matlab编程实现算法，通过大量仿真模拟并与其他算法进行比较分析，证实了所提出方法的有效性.提出的算 法在问题规模不大时可以迅速而准确的获得优化解，在问题规模较大时也能在较短时间（与其他算法相比）获得满 意解，因此具有较好的综合性能. 关键词：动态设备布局问题；启发式算法；单亲遗传算法 中图分类号：TP391.9文献标识码：A文章编号：16734785(2007)01-0074-06 Simulation of the dynamic plant layout problem based on partheno genetic algorithm LI Bo,QIU Feng (School of Management,Tianjin University,Tianjin 300072,China) Abstract:A heuristic algorithm based on PGA was proposed to solve the plant layout problem in flexible manufacturing systems.A new positionswitch genetic operator for DPL P was developed.Positionswitch probability strategy on single-period-layout was used to increase individuals'diversity.The effectiveness of proposed method is demonstrated by simulation examples and comparison with other approaches.Pro- posed algorithm produces optimal solutions speedily and accurately and provides acceptable solution in a reasonable time.Its performance is very good while considering both solution quality and computational time. Key words:DPLP;heuristic approach;PGA 在当今以市场为驱动的经济环境下，制造企业 备布局问题进行优化求解」 力求适应市场的变化而在竞争中立于不败之地，柔 1动态设备布局问题 性生产系统(FMS)应运而生.生产车间的设备布局 问题是柔性生产系统（或柔性生产单元）在设计初期 动态设备布局问题，包括为每一期选择一个静 必须考虑的重要问题之一.柔性即是指灵活应对市 态设备布局方案和决定是否在下一期改变这个布 场，在拉动式生产方式下，企业面临的是最终用户不 局.图1是一个单期6台(23)设备布局的例子，用 断变化的需求，静态设备布局问题(static plant lay- 236145(数字代表设备编号)来表示. out problem,SPLP)假设物料流不变，不适用于动 对实际问题进行简化，进行以下假设 态变化的环境，动态设备布局问题(dynamic plant 1)设备占地面积相同；2)设备数小于等于位置 layout problem,DPLP)在SPLP的基础上，从多时 数（小于时可通过增加虚拟设备来解决）；3)设备间 期的角度出发，每个时期设备间的物料流量各不相 的单位物流运输成本相同（在此为了简化可设为 同，并考虑设备的移动成本，在总的规划时间内对设 1);4)设备的移动成本与布局方式无关（是某个常 量)，5)设备间运输距离，同行或同列的设备间运距 收稿日期：20060705. 为其中心的间距、非同行或非同列的设备间运距为 基金项目：国家自然科学基金资助项目(70572045) 设备中心之间的折线距离（例如图1中设备2到设 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net第 2 卷第 1 期 智 能 系 统 学 报 Vol. 2 №. 1 2007 年 2 月 CAA I Transactions on Intelligent Systems Feb. 2007 基于单亲遗传算法的动态设备布局仿真研究 李 波 ,邱 枫 (天津大学 管理学院 ,天津 300072) 摘 要 :针对柔性生产环境下的设备布局问题 ,提出了一种基于单亲遗传算法原理的启发式算法. 发展了一种新颖 的适用于动态设备布局的遗传换位操作算子 ,并提出在单期布局编码子串上应用换位概率的策略 ,增加了种群的多 样性. Matlab 编程实现算法 ,通过大量仿真模拟并与其他算法进行比较分析 ,证实了所提出方法的有效性. 提出的算 法在问题规模不大时可以迅速而准确的获得优化解 ,在问题规模较大时也能在较短时间 (与其他算法相比) 获得满 意解 ,因此具有较好的综合性能. 关键词 :动态设备布局问题 ;启发式算法 ;单亲遗传算法 中图分类号 : TP39119 文献标识码 :A 文章编号 :167324785 (2007) 0120074206 Simulation of the dynamic plant layout problem based on partheno genetic algorithm L I Bo , QIU Feng (School of Management ,Tianjin University ,Tianjin 300072 , China) Abstract :A heuristic algorit hm based on PGA was p roposed to solve the plant layout problem in flexible manufact uring systems. A new position2switch genetic operator for DPL P was developed. Position2switch probability strategy on single2period2layout was used to increase individuals’diversity. The effectiveness of proposed method is demonstrated by simulation examples and comparison wit h ot her approaches. Pro2 posed algorit hm produces optimal solutions speedily and accurately and provides acceptable solution in a reasonable time. Its performance is very good while considering bot h solution quality and comp utational time. Keywords :DPL P; heuristic approach ; PGA 收稿日期 :2006207205. 基金项目 :国家自然科学基金资助项目(70572045) . 在当今以市场为驱动的经济环境下 ,制造企业 力求适应市场的变化而在竞争中立于不败之地 ,柔 性生产系统(FMS) 应运而生. 生产车间的设备布局 问题是柔性生产系统(或柔性生产单元) 在设计初期 必须考虑的重要问题之一. 柔性即是指灵活应对市 场 ,在拉动式生产方式下 ,企业面临的是最终用户不 断变化的需求 ,静态设备布局问题 (static plant lay2 out problem , SPL P) 假设物料流不变 ,不适用于动 态变化的环境 ,动态设备布局问题 ( dynamic plant layout p roblem , DPL P) 在 SPL P 的基础上 ,从多时 期的角度出发 ,每个时期设备间的物料流量各不相 同 ,并考虑设备的移动成本 ,在总的规划时间内对设 备布局问题进行优化求解. 1 动态设备布局问题 动态设备布局问题 ,包括为每一期选择一个静 态设备布局方案和决定是否在下一期改变这个布 局. 图 1 是一个单期 6 台(2 ×3) 设备布局的例子 ,用 236145 (数字代表设备编号) 来表示. 对实际问题进行简化 ,进行以下假设 : 1) 设备占地面积相同 ;2) 设备数小于等于位置 数(小于时可通过增加虚拟设备来解决) ;3) 设备间 的单位物流运输成本相同 (在此为了简化可设为 1) ;4) 设备的移动成本与布局方式无关 (是某个常 量) ;5) 设备间运输距离 ,同行或同列的设备间运距 为其中心的间距、非同行或非同列的设备间运距为 设备中心之间的折线距离 (例如图 1 中设备 2 到设