第ｌ５卷第１期 工业工程 Ｖｏ１．１５ Ｎｏ．１ ２０１２年２月 Ｉｎｄｕｓｔｒｉａｌ Ｅｎｇｉｎｅｅｒｉｎｇ Ｊｏｕｒｎａｌ Ｆｅｂｒｕａｒｙ ２０１２ 基于改进粒子群算法的制造单元设施布局问题研究 郑永前，丁奎学 （同济大学机械工程学院，上海２０１８０４） 摘要：为避免单元系统布局和单元内设施布局分开孤立研究所导致的问题解空间损失，利用并行工程的思想对单元 布局的两个环节集成考虑，对单元系统布局、单元内设施布置、设施摆放方向进行同时描述，并建立多目标集成优化 模型。针对模型的复杂性，设计了改进粒子群算法，算法吸收了遗传算法中的交叉操作算子，具有跳出局部最优解 的能力。最后通过求解单元设施布置实例，验证模型和算法的有效性。 关键词：制造单元；设施布局；粒子群算法；多目标优化 中图分类号：ＴＨ１６５ 文献标志码：Ａ 文章编号：１００７－７３７５（２０１２）０１．０１２５．０６ Ｌａｙｏｕｔ Ｄｅｓｉｇｎ ｉｎ Ｃｅｌｌｕｌａｒ Ｍａｎｕｆａｃｔｕｒｉｎｇ Ｂａｓｅｄ ｏｎ Ｉｍｐｒｏｖｅｄ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ Ｚｈａｎｇ Ｙｏｎｇ—ｑｉａｎ，Ｄｉｎｇ Ｋｕｉ－ｘｕｅ （Ｓｃｈｏｏｌ ｏｆ Ｍｅｃｈａｎｉｃａｌ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｔｏｎｇｊｉ Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ ２０１８０４，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｒａｄｉｔｉｏｎａｌｌｙ，ｔｈｅ ｉｎｔｒａ—ｃｅｌｌ ａｎｄ ｉｎｔｅｒ—ｃｅｌｌ ｌａｙｏｕｔ ｐｒｏｂｌｅｍｓ ｉｎ ｌａｙｏｕｔ ｄｅｓｉｇｎ ｏｆ ｃｅｌｌｕｌａｒ ｍａｎｕｆａｃ— ｔｕｒｉｎｇ ｓｙｓｔｅｍｓ ａｒｅ ｓｏｌｖｅｄ ｓｅｐａｒａｔｅｌｙ，ｗｈｉｃｈ ｍａｙ ｒｅｓｕｌｔ ｉｎ ａ ｌｏｃａｌ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ．Ｉｎ ｏｒｄｅｒ ｔｏ ａｖｏｉｄ ｔｈｅ ｌｏ－ ｃａｌ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ，ｔｈｅｓｅ ｔｗｏ ｐｒｏｂｌｅｍｓ ａｒｅ ｓｏｌｖｅｄ ｃｏｎｃｕｒｒｅｎｔｌｙ ｉｎ ｔｈｉｓ ｐａｐｅｒ．Ｔｈｉｓ ｐｒｏｂｌｅｍ ｉｓ ｆｏｒｍｕｌａｔｅｄ ａｓ ａｎ ｉｎｔｅｇｅｒ ｐｒｏｇｒａｍｍｉｎｇ ｗｉｔｈ ｍｕｌｔｉｐｌｅ ｏｂｊｅｃｔｉｖｅｓ．Ｉｎ ｔｈｅ ｍｏｄｅｌ，ｔｈｅ ｏｒｉｅｎｔａｔｉｏｎ ｏｆ ｔｈｅ ｆａｃｉｌｉｔｉｅｓ，ｔｈｅ ｉｎ－ ｔｒａ－ｃｅｌｌ ａｎｄ ｉｎｔｅｒ—ｃｅｌｌ ｌａｙｏｕｔ ａｒｅ ｄｅｓｃｒｉｂｅｄ ｓｉｍｕｌｔａｎｅｏｕｓｌｙ．Ｄｕｅ ｔｏ ｔｈｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｔｈｅ ｍｏｄｅｌ，ａｎ ｉｍ－ ｐｒｏｖｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ（ＰＳＯ）ａｌｇｏｒｉｔｈｍ ｉｓ ｐｒｏｐｏｓｅｄ．Ｔｏ ｉｍｐｒｏｖｅ ｉｔｓ ｐｅｒｆｏｒｍａｎｃｅ，ｔｈｅ ＰＳＯ ａｌ— ｇｏｒｉｔｈｍ ｉｓ ｍｏｄｉｉｆｅｄ ｂｙ ａｄｏｐｔｉｎｇ ｔｈｅ ｃｒｏｓｓｏｖｅｒ ｏｐｅｒａｔｏｒ ｕｓｅｄ ｉｎ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ．Ａ ｓｉｍｕｌａｔｉｏｎ ｅｘｐｅｒｉｍｅｎｔ ｖｅｒｉｉｆｅｓ ｔｈｅ ｖａｌｉｄｉｔｙ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈｏｄ． Ｋｅｙ ｗｏｒｄｓ：ｃｅｌｌｕｌａｒ ｍａｎｕｆａｃｔｕｒｉｎｇ；ｆａｃｉｌｉｔｙ ｌａｙｏｕｔ；ｐａｒｔｉｃｌｅ ｓｗａｒｌｎ ｏｐｔｉｍｉｚａｔｉｏｎ（ＰＳＯ）；ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ ｏｐｔｉｍｉｚａｔｉｏｎ 单元生产方式是适应于目前多品种、少批量的 成，解决的是单元内设备布置问题；Ｗａｎｇｌ６ 假定单 市场需求环境所产生的先进生产方式，它融合了 元内和单元间布局为ｕ形，考虑解决单元内设施布 Ｊｏｂ—ｓｈｏｐ高柔性与Ｆｌｏｗ－ｓｈｏｐ高生产率的特点，解决 局和单元系统布局的方法；Ｓｈａｈｒａｍ等 ７ｊ假定各设 了传统生产方式生产率与生产柔性的矛盾 Ｊ。为构 施面积相等且各单元面积相等，对于设备和单元面 造单元生产系统，需研究以下几方面：１）单元构建； 积相差较大的实际问题，Ｓｈａｈｒａｍ所提的方法已不再 ２）单元内设备布局；３）单元系统布局。大量学者 适用。 对单元构建问题进行了研究：Ｙｉｎ等＿２ 考虑了多因素 本文利用并行工程的思想，研究了单元制造系 单元构建问题；Ｋａｅｂｅｒｎｉｃｋ等 考虑了单元数量的 统中的单元内设施布局和单元系统布局问题，提出 约束；王爱民等 考虑了加工设备的生产能力和任 了对单元设施布局的两个阶段进行集成优化的方 务交货期的约束。然而，人们对单元设施布局方面 法，建立多目标优化模型，并利用改进的粒子群算法 的研究较少。Ａｔｔａｈｉｒｕ等 假定单元系统布局已完 对模型进行求解。 收稿日期：２０１Ｉ一０３．１５ 基金项目：上海市自然科学基金资助项目（１０ＺＲ１４３１７００） 作者简介：郑永前（１９６５一），男，河南省人，副教授，博士，主要研究方向为生产系统工程与管理、先进制造技术、企业信息化技术 与应用． 工业工程 第１５卷 １ 制造单元设施布局问题 关信息和要求确定一个折中解（ｃｏｍｐｒｏｍｉｓｅ），也称 妥协解。为了保证两个优化目标统一的量纲，本文 设施布局是指在一定的生产环境下，制造系统 采用归一化因子 加］。 设计人员根据生产目标确定系统中设施的布置形式 定义归一化因子叩， ： 和位置 引。假定制造单元和设施均为矩形块状结 Ｍ Ｍ ．ｐ 构，其长和宽已知；各单元内的设施统一采用线性布 叼＝１／∑∑∑ ｃＩ １ Ｊ １ Ｐ １ ｅｉｌ（ｖ／ｔｉ）ｔｉ， （５） 局，且设施有横向和纵向两种摆放方式，单元间采用 多行布局。 ＝１／∑Ｓｉ， （６） Ｉ＝ｌ Ｍ Ｍ Ｐ 本文要解决的问题可描述为：生产单元构建阶段 已完成，现对单元内设施布局和单元系统布局进行优 ａｒｉｎ ｚ＝ ∑∑∑ｎＬ＝１ ＝Ｉ Ｐ＝Ｉ ￣ｃｅｉｌ（ ／ ）ｄ ＋卢 ｓ。 化，使得总物料搬运成本最小，车间面积利用率最高。 （７） ２ 问题建模 式中，Ｏｔ， 分别为搬运距离和布局面积的权重， ＋／３＝１。 为了描述方便，引入以下基本符号：Ｐ（Ｐ＝１，２， ２．４约束分析 …，Ｐ）为零件编号；ｉ，．『（ｉ， ＝１，２，…， ）为设施编 ２。４．１单元内设施布局约束 号；（ ，Ｙ ）为设施ｉ的中心点坐标； 、 分别为设 单元内设施布局模型引入以下变量：ｈ 、 分别 施 的长度和宽度；ｃ（ｃ＝１，２，…，ｃ）为单元编号。 表示设备ｉ的横向和纵向长度，当设备横向摆放时， ２．１物料搬运距离计算 ｈ ：ｆ ， ＝ ｉ；否则，ｈ ＝ ， ＝ｆ ，ｄ 为单元内相邻 离散型制造企业多采用托盘、容器等物料装载 设备间的安全距离，如图１所示。 工具，为了更符合实际应用情况，物料搬运距离可描 ｙ 述为 Ｍ 村Ｐ ∑∑∑ｎ￣ｅｅｉｌ（ ／ ）・ｄ 。 （１） 式中，ｎ 为加工零件Ｐ时，该零件从设施 到设 施 的转移次数； 为零件ｐ的需求量； 为零件Ｐ 的搬运批量；ｃｅｉｌ（）表示对数值进行向上取整，ｄ 为 ｘ 设施 √之间的距离。工厂中物料一般是沿着通道 图１单元内布局参数示意图 流动的，本文取折线距离作为设施间距。 Ｆｉｇ．１ Ｐａｒａｍｅｔｅｒｓ ｏｆ ｉｎｔｒａ－ｃｅｌｌ ｌａｙｏｕｔ ｄ ＝Ｉ 一 ，Ｉ＋ｌＹ 一），，Ｉ。 （２） ｌ — ，Ｉ≥（ｈ ＋ ｆ）／２＋ｄ ， （８） ２．２设施面积利用率计算 Ｙ ＝乃。 （９） 设施布置应考虑紧凑性原则，即应提高设施的 其中，式（８）保证设备ｉ和 保持一定的安全距 面积利用率，设施面积利用率可描述为 离，式（９）保证同一单元内的设备布置在同一行中。 ｍａｘ∑Ｓｉ＝１ ／Ｓ。 （３） ２．４．２卑无 局约慕 根据物流顺畅的要求，各制造单元间要保持一 式中，Ｓｉ表示设施ｉ的矩形包络面积，Ｓ表示整 定间距，本文将单元间距ｄ加入单元包络矩形，形成 体布局的矩形包络面积。由于各设施的矩形包络面 单元拓扑结构，如图２所示。 积为定值，所以该优化目标可等价于ｍｉｎＳ。 Ｓ＝［ｍａｘ（ｘ￣）一ｒａｉｎ（ ∞）］・［ｍａｘ（）， ）一 ｍｉｎ（Ｙ ）］， ｉ，Ｊ＝１，２，…，ｍ。 （４） 其中， 、 分别为设施ｉ包络矩形的左下角的 、 坐标值， 分别为设施 包络矩形的右上角的 、Ｙ坐标值。 ２．３目标函数 本文要解决的单元设备布置问题有两个目标， ｘ 属于多目标优化问题。求解多目标优化问题就是求 图２制造单元拓扑结构 出问题的Ｐａｒｅｔｏ最优解集，然后再由决策者根据相 Ｆｉｇ．２ Ｔｈｅ ｅｘｔｅｎｔｅｄ ｓｔｒｕｃｔｕｒｅ ｏｆ ｍａｎｕｆａｃｔｕｒｉｎｇ ｃｅｌｌ 第１期 郑永前，丁奎学：基于改进粒子群算法的制造单元设施布局问题研究 定义决策变量 ，。 ｆ１，单元ｃ在第ｒ行 一问题解的一个集合开始。但与ＧＡ相比，ＰＳＯ只有最 优粒子提供信息给其他粒子，信息的流动方向是单 向的，整个搜索过程为跟随当前最优解的过程，所有 粒子很有可能更快地收敛于最优解，但也相对容易 陷入局部最优解。文献［１０］利用遗传算法对单元布 １０，其他 （１ｏ） （１１） 生产单元应满足约束条件： ｒ＝ｌ ∑Ｓ ＝１，ｃ＝１，２，…ｃ； Ｃ 局问题求解，文献［１ １］求解单向环形设备布局问题。 本文在文献［１０］、［１１］的基础上，吸收遗传算法中 ∑Ｓ ≤Ｃ，ｒ＝１，２，…Ｒ； ［ ｃｂ一（ ．ｂ＋ ．ｂ）］・［（ 出＋ ｃｂ）一 。，ｂ］Ｉ＞０， Ｓ ，＝Ｓ ，，； （１２） ［Ｙ ｂ一（Ｙ ｜ｈ＋ ｜ｈ）］・［（Ｙ ｂ＋ ｂ）一Ｙ ．ｂ］≥０， Ｓ ，≠Ｓ ， ； （１３） ｂ＋ ≤ｍａｘ ； （１４） Ｙ ｂ＋ ≤ｍａｘ Ｙ。 （１５） 式中，约束条件（１０）表示各生产单元所在的行 是唯一的；式（１１）表示每一行单元数小于等于单元 总数；式（１２）表示若单元Ｃ和单元ｃ 在同一行，则单 元的拓扑形状在 方向上不重叠；式（１３）表示若单 元Ｃ和单元ｃ 不在同一行，则单元的拓扑形状在Ｙ方 向上不重叠，式（１４）、（１５）表示单元ｃ必须满足布局 空间约束，不能超出所要求的布局空间。 ３ 问题求解与改进粒子群算法设计 ３．１基本粒子群算法 粒子群算法兼有模拟进化算法和群智能的特 点，与其他进化算法相类似，ＰＳＯ算法也是通过个体 间的协作与竞争，实现复杂空间中最优解的搜索。 在每一次迭代中，粒子通过跟踪两个极值来更新自 己：第一个极值是粒子本身找到的历史最优解，称为 个体极值点（ ）；另一个极值是整个种群目前找到 的最好解，称为全局极值点（ｇ ）。在找到这两个最 好解后，粒子根据式（１６）～（１８）来更新自己的速度 和位置。 ＝ｎ， ＋ｚ１ｒ１（Ｐｂ。。ｔ— ）＋１２ｒ２（ｇｂ ｔ一 ）， （１６） ＝ ＋ ＋１。 （１７） 其中，Ｚ ，Ｚ 为学习参数，ｒ。，ｒ 为［０，１］区间上的 随机数， 为第 个粒子在第ｋ次迭代中的位置，Ｐ 为第 个粒子自身的历史最优位置，ｇ 为所有粒子 的历史最优位置，∞为设定的约束系数，定义６０为 ＝ 一（ ａｘ一 ｉ ）ｋ／Ｔ， （１８） 式中， ∞ ｉ 为已知常量， 是迭代的总次数， ｋ为已迭代次数。 ３．２杂交粒子群算法 ＰＳＯ与ＧＡ都具有隐含并行性，搜索过程都是从 的交叉操作，对粒子群算法进行改进。 粒子群中的粒子被赋予一个杂交概率Ｐ，该概 率由用户给出，不依粒子的适应度改变，在迭代中依 据杂交的概率选取指定数量的粒子，将选定的粒子 随机地两两杂交，产生相同数目的子代取代父代群 体，让ａ和ｂ表示被选择的２个粒子，计算公式为 ｋ ＝ ： ＋（１－Ａ） ， （１９） ＝ ＋（１－Ａ） ：， （２０） ｋ ＝ ： ＋（１一 ） ， （２１） ｋ“＝ ：“＋（１－Ａ） ：。 （２２） 以上各式中， 为０—１之间的随机数。 ３．３粒子的结构化编码／解码 单元设施布局问题求解有２个难点：１）单元设 施布置问题，属于离散空间的非数值优化问题，而 ＰＳＯ属于连续空间域的优化算法；２）一般的编码方 法只用于解决一个方面的问题，而对单元设施布局 问题要求设计的编码方式能同时描述单元系统布 局、单元内设施布置、设施摆放方向。本文设计了一 种粒子的多维实数编码方法，实现从粒子到设施布 局形式的映射，使ＰＳＯ成功应用到离散的设备布局 问题求解中。 本文采用结构化编码方法，如表１所示，粒子编 码被分成３部分。 表１粒子位置编码示例 Ｔａｂ．１ Ｅｘａｍｐｌｅ ｏｆ ｔｈｅ ｅｎｃｏｄｉｎｇ ｏｆ ａ ｐａｒｔｉｃｌｅ 各部分编码／解码解释如下。 １）单元位置编码。该部分为长度为Ｃ的正实 数编码串，每一个编码位对应一个生产单元，解码时 对编码位上的实数大小进行比较，该实数的排列序 工业工程 第１５卷 号即为对应的设备编号。本文采用自动换行策略， 若一行中各单元横向长度和单元间距离之和超出设 备布局范围，则该行的最后一个单元在下一行中进 行布置。 ２）设备位置编码。该部分是长度为 的正实 数编码串，解码时对属于同一单元的设备所对应的 实数编码进行排序，实数的排列顺序即为该单元中 设备的编号的排列顺序。 ３）设备摆放方向编码。该部分是长度为 的 正整数编码，若该整数为奇数，这单元横向放置；若 为偶数，则单元纵向放置。 该示例有７台设备（ ， ＝１，２，…，７），现已通过 单元构建得到单元划分结果为：Ｃ ：｛１，４，５｝，ｃ ＝ ｛３，６｝，Ｃ ＝｛２，７｝。单元位置编码为（１Ｏ．５，３．２， １１．６），解码后的单元排列次序为２—１—３；设备位置 编码为（２．１，１．３，１３．６，０．３，８．２，３．５，１．６），解码后 的设备排列顺序为６—３ ｌ５—１—４Ｉ７—２；设备摆放方 向编码为（２，７，３，４，１５，１９，１０），解码后为纵一横一 横一纵一横一横一纵。 ３．４问题求解和改进ＰＳＯ算法流程设计 采用改进ＰＳＯ求解单元设施布置问题，算法流 程设计如下。 步骤１ 确定粒子种群和数量，初始化粒子位置 和速度，令ｇ 。 未优化的次数ｎ＝０。 步骤２ 判断算法是否达到最大迭代次数，若 是，则停止迭代，输出结果；否则，转步骤３。 步骤３ 判断ｇｂｅｓｔ是否已经连续Ⅳ代没有被优 化，若是，则停止迭代，输出结果；否则，转步骤４。 步骤４按式（１６）一（１８）对粒子的速度和位置 进行更新。 步骤５比较粒子的适应值和自身最优值Ｐ 。 如果当前值比Ｐｂｅｓｔ更优，则置Ｐ 为当前值。 步骤６ 比较粒子的适应值与种群最优值ｇ 。 如果当前值比ｇ 。 更优，则重置ｇ 。 步骤７ 选取各子群中的非最优粒子，按式 （１９）～（２２）进行交叉操作，更新各子群，转步骤２。 ４实验与仿真分析 某车间接到一批生产任务，需要加工工件的种 类、批量、工艺路径如表２所示，各设备的面积如表３ 所示。公司考虑到对现有的车间布局不能满足生产 要求，决定对车间设备重组，并进行重新布局（车间 面积为２０ ｍ ｘ １８ ｍ）。 表２零件生产工艺路径 Ｔａｂ．２ Ｔｈｅ ｐｒｏｃｅｓｓ ｐａｔｈｓ ｏｆｔｈｅ ｐａｒｔｓ 善需求量 工路艺径 表３设施面积 Ｔａｂ．３ Ｔｈｅ ａｒｅａ ｏｆ ｔｈｅ ｆａｃｉｌｉｔｉｅｓ ｍ 编号 面积（长Ｘ宽） 编号 面积（长ｘ宽） ｌ ２．８×１．８ ９ ３．２×２．４ ２ ３．６×１．６ １０ ２．０×１．６ ３ ３．０×１．６ １１ ３．６×２．０ ４ ３．０×１．８ １２ ３．０×２．２ ５ ４．８×２．４ １３ ２．４×２．０ ６ ３．２×２．８ １４ ２．２×１．８ ７ ２．６×１．６ ｌ５ ４．２×２．２ ８ ２．８×１．８ 现已知制造单元的划分结果：Ｃ ＝｛ｍ ，ｍ ，ｍ ， ｍ９，ｍ１３｝，ｃ２＝｛ｍ３，ｍ４，ｍ７，ｍ８，ｉｎ１５｝，ｃ３＝｛ｍ６， ｍ 。，ｍ ｍ。 ，ｍ ｝。同一单元内，相邻设施间距离 为１．２ ｍ，相邻单元的间距为３．０ｍ。 文献［６］中假定单元构建已完成，以总物流费用 最小为目标，用模拟退火算法对单元内设施布局和 单元系统布局问题集成求解，不考虑车间面积利用 率问题。 本文算法设定粒子最大迭代次数ｇｅｎ＝１ ０００， 粒子数量ｐｓｏｓｉｚｅ＝４０，ｇ 连续没有进化的代数Ｎ＝ ２００，学习参数ｆ ＝Ｚ ＝２，最大惯性系数权重Ｗ ＝ ０．９，最小惯性系数Ｗ ｉ ＝０．４，设施位置编码数值范 围为［０，ｌ０］，单元位置编码数值范围为［０，１］，设备 摆放方向编码数值范围为［０，１００］，目标函数中物料 搬运距离和布局面积所占权重分别为０．７、０．３。改 进粒子群算法将所有粒子随机地划分为４个种群， 杂交概率Ｐ＝０．４， 取０—１之间的随机数。 分别用文献［６］中的方法、基本粒子群算法和改 进粒子群算法求解本文实例，３种算法各运行３Ｏ次 并取最优值，得到单元系统布局和单元内设施布局 结果，以及单元内各设施的摆放方向（１表示设施横 向摆放，０表示设施纵向摆放），结果如表４所示。 第１期 郑永前，丁奎学：基于改进粒子群算法的制造单元设施布局问题研究 １２９ 可以看出，文献［６］的总搬运距离最短，但占地 Ｗａｎｇ Ａｉ－ｍｉｎ，Ｄｉｎｇ Ｇｕｏ－ｚｈｉ，Ｎｉｎｇ Ｒｕ—ｘｉｎ．Ｒａｐｉｄ ｄｅｓｉｎｇ 面积也是最大的，由本文模型得到的物料搬运距离 ｔｅｃｈｎｏｌｏｇｙ ｆｏｒ ｍａｎｕｆａｃｔｒｕｉｎｇ ｃｅｌｌｓ［Ｊ］．Ｔｒａｎｓａｃｔｉｏｎｓ ｏｆ Ｂｅｉ— 略大，但占地面积减少很多；在给定的搬运距离和布 ｊｉｎｇ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，２００６，２６（１０）：８５０－８５４． 局面积的权重下，改进粒子群算法得到的结果是最 ［５］Ａｔｔａｈｉｒｕ Ｓ Ａ，Ｍｉｎｇｙｕａｎ Ｃ，Ｓｕｎｄｅｒｅｓｈ Ｓ．Ｉｎｔｅｇｒａｔｉｎｇ ｔｈｅ ｇｒｏｕｐｉｎｇ ａｎｄ ｌａｙｏｕｔ ｐｒｏｂｌｅｍｓ ｉｎ ｃｅｌｌｕｌｒａ ｍａｎｕｆａｃｔｕｒｉｎｇ ｓｙｓ。 优的。 ｔｅｍｓ［Ｊ］．Ｃｏｍｐｕｔｅｒｓ ａｎｄ Ｉｎｄｕｓｔｉｒｌａ Ｅｎｇｉｎｅｅｒｉｎｇ，１９９２，２３ ５结束语 （４）：５５－５８． ［６］Ｗａｎｇ Ｔａｉ—ｙｕｅ，Ｌｉｎ Ｈｅｒ－ｃｈａｎｇ，Ｗｕ Ｋｕｄｉ—ｂｉｎ．Ａｎ ｉｍｐｒｏｖｅｄ 本文研究解决了制造单元的设施布局问题，对 ｓｉｍｕｌａｔｅｄ ａｎｎｅａｌｉｎｇ ｆｏｒ ｆａｃｉｌｉｔｙ ｌａｙｏｕｔ ｐｒｏｂｌｅｍｓ ｉｎ ｃｅｌｌｕｌａｒ 单元系统布局和单元内设施布局集成考虑并进行多 ｍａｎｕｆａｃｔｕｒｉｎｇ ｓｙｓｔｅｍｓ［Ｊ］．Ｃｏｍｐｕｔｅｒｓ ａｎｄ Ｉｎｄｕｓｔｉｒａｌ Ｅｎｇｉ－ 目标优化。单元布局问题属于ＮＰ完全问题，文中提 ｎｅｅｒｉｎｇ，１９９８，３４（２）：３０９－３１９． 出的基于结构化编码的改进ＰＳＯ算法能进行有效的 ［７］Ｓｈａｈｒａｍ Ａ，Ｎａｐｓｉａｈ Ｉ．Ａｎ ｉｍｐｒｏｖｅｄ ｌａｇｏｒｉｔｈｍ ｆｏｒ ｌａｙｏｕｔ ｄｅ。 求解。吸收了交叉算子的改进ＰＳＯ算法既具有快速 ｓｉｎｇ ｉｎ ｃｅｌｌｕｌｒａ ｍａｎｕｆａｃｔｕｒｉｎｇ ｓｙｓｔｅｍｓ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｍａｎｕ— 搜索、鲁棒性好的特点，又具有使算法跳出局部最优 ｆａｃｔｕｒｉｎｇ Ｓｙｓｔｅｍｓ，２００９，２８（４）：１３２—１３９． 解的能力。通过仿真实验可以看出，模型在兼顾设 ［８］Ｒｕｓｓｅｌｌ Ｄ，Ｋａｉ—ｙｉｎ Ｇ．Ｔｈｅ ｆａｃｉｌｉｔｙ ｌａｙｏｕｔ ｐｒｏｂｌｅｍ：Ｒｅｃｅｎｔ 施布局的面积利用率方面更具优势。 ｎａｄ ｅｍｅｒｇｉｎｇ ｔｒｅｎｄｓ ａｎｄ ｐｅｒｓｐｅｃｔｉｖｅｓ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｍａｎｕ・ 本文所提出的单元布局方法适用于解决所生产 ｆａｃｔｕｒｉｎｇ Ｓｙｓｔｅｍｓ，１９９６，１５（５）：３５１—３６３． ［９］锁小红，刘战强．制造系统设备布局的建模理论与求解方 产品的工艺路径已确定且产品的需求量比较稳定的 法［Ｊ］．计算机集成制造系统，２００７，１３（１０）：１９４１—１９５１． 单元布局问题，对于多工艺生产路径和动态产品需 Ｓｕｏ Ｘｉａｏ—ｈｏｎｇ，Ｌｉｕ Ｚｈａｎ—ｑｉａｎｇ．Ｍｏｄｅｌｉｎｇ ａｎｄ ｓｏｌｕｔｉｏｎ ｆｏｒ 求的单元布局方法是今后研究的重点。 ｆａｃｉｌｉｔｙ ｌａｙｏｕｔ ｏｆ ｍａｎｕｆａｃｔｕｒｉｎｇ ｓｙｓｔｅｍｓ［Ｊ］．Ｃｏｍｐｕｔｅｒ Ｉｎｔｅ— 参考文献： ｒｇａｔｅｄ Ｍａｎｕｆａｃｔｕｒｉｎｇ Ｓｙｓｔｅｍｓ，２００７，１３（１０）：１９４１—１９５１． ［１０］王定益，王丽亚．一种单元制生产方式设备布局问题的 ［１］Ａｈ ｋｉｏｏｎ Ｓ，Ｂｕｌｇａｋ Ａ Ａ，Ｂｅｋｔａｓ Ｔ．Ｉｎｔｅｇｒａｔｅｄ ｃｅｌｌｕｌａｒ ｍａｎ— 研究方法［Ｊ］．工业工程与管理，２００６，１６（１）：１０—１３． ｕｆａｃｔｕｒｉｎｇ ｓｙｓｔｅｍｓ ｄｅｓｉｇｎ ｗｉｔｈ ｐｒｏｄｕｃｔｉｏｎ ｐｌｎａｎｉｎｇ ａｎｄ ｄｙ— Ｗａｎｇ Ｄｉｎｇ－ｙｉ，Ｗａｎｇ Ｌｉ－ｙａ．Ｔｈｅ ｆａｃｉｌｉｔｙ ｌａｙｏｕｔ ｓｔｕｄｙ ｂａｓｅｄ ｎａｍｉｃ ｓｙｓｔｅｍ ｒｅｃｏｎｆｉｇｕｒａｔｉｏｎ［Ｊ］．Ｅｕｒｏｐｅａｎ Ｊｏｕｒｎａｌ ｏｆ Ｏｐｅｒ－ ｏｎ ｃｅｌｌｕｌｒａ ｍａｎｕｆａｃｔｕｒｉｎｇ［Ｊ］．Ｉｎｄｕｓｔｉｒｌａ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ ａｔｉｏｎａｌ Ｒｅｓｅａｒｃｈ，２００９，１９２（２）：４１４－４２８． Ｍａｎａｇｅｍｅｎｔ，２００６，１６（１）：１０—１３． ［２］Ｙｉｎ Ｙｏｎｇ，Ｙａｓｕｄａ Ｋ．Ｍａｎｕｆａｃｔｕｒｉｎｇ ｃｅＮｓ’ｄｅｓｉｎｇ ｉｎ ｃｏｎ— ［１１］曾议，竺长安．基于群智能算法的设备布局离散优化研 ｓｉｄｅｒａｔｉｏｎ ｏｆ ｖａｒｉｏｕｓ ｐｒｏｄｕｃｔｉｏｎ ｆａｃｔｏｒｓ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ 究［Ｊ］．计算机集成制造系统，２００７，１３（３）：５４１－５５２． Ｊｏｕｒｎａｌ ｏｆ Ｐｒｏｄｕｃｔｉｏｎ Ｒｅｓｅａｒｃｈ，２００２，４０（４）：８８５－９０６． Ｚｅｎｇ Ｙｉ，Ｚｈｕ Ｃｈａｎｇ－ａｎ．Ｄｉｓｃｒｅｔｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ ｏｆ ［３］Ｋａｅｂｅｒｎｉｃｋ Ｈ，Ｂａｚａｒｇａｎ—Ｌａｒｉ Ｍ．Ａｎ ｉｎｔｅｇｒａｔｅｄ ａｐｐｒｏａｃｈ ｔｏ ｍａｃｈｉｎｅ ｌａｙｏｕｔ ｂａｓｅｄ ｏｎ ｓｗａｒｌｎ ｉｎｔｅｌｌｉｇｅｎｃｅ ｌａｇｏｒｉｔｈｍ［Ｊ］． ｔｈｅ ｄｅｓｉｇｎ ｏｆ ｃｅｌｌｕｌｒａ ｍａｎｕｆａｃｔｕｒｉｎｇ［Ｊ］．ＣＩＲＰ Ａｎｎａｌｓ— Ｃｏｍｐｕｔｅｒ Ｉｎｔｅｇｒａｔｅｄ Ｍａｎｕｆａｃｔｕｒｉｎｇ Ｓｙｓｔｅｍｓ，２００７，１３（３）： Ｍａｎｕｆａｃｔｕｒｉｎｇ Ｔｅｃｈｎｏｌｏｇｙ，１９９６，４５（１）：４２１－４２５． ５４１－５５２． ［４］王爱民，丁国智，宁汝新．制造单元快速构建技术研究 ［１２］Ｋｅｎｎｅｄｙ Ｊ，Ｅｂｅｒｈａｒｔ Ｒ．Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚｔａｉｏｎ［Ｃ］． ［Ｊ］．北京理工大学学报，２００６，２６（１０）：８５０－８５４． Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｕｒａｌ １３０ Ｎｅｔｗｏｒｋｓ，Ａｕｓｔｒａｌｉａ：Ｐｅｒｔｈ，１９９５：１９４２—１９４８． 工业工程 第１５卷 ｒｉｔｈｍ ｆｏｒ ｆａｃｉｌｉｔｙ ｌａｙｏｕｔ ｐｒｏｂｌｅｍｓ ｕｎｄｅｒ ｖａｒｉａｂｌｅ ｄｅｍａｎｄ ｉｎ ［１３］靳雁霞，韩燮，周汉昌．改进的粒子群优化算法［Ｊ］．计 算机工程与设计，２００９，３０（１７）：４０７４—４０７６． Ｊｉｎ Ｙａｎ—ｘｉａ，Ｈａｎ Ｘｉｅ，Ｚｈｏｕ Ｈａｎ—ｃｈａｎｇ．Ｉｍｐｒｏｖｅｄ ｐａｒｔｉｃｌｅ ｃｅｌｌｕｌａｒ ｍａｎｕｆａｃｔｕｒｉｎｇ ｓｙｓｔｅｍｓ［Ｊ］．Ｃｏｍｐｕｔｅｒｓ ｉｎ Ｉｎｄｕｓ— ｔｒｙ，２００１，４６（２）：１８１—１８８． ［１５］Ｈｏ Ｙ Ｃ，Ｍｏｏｄｄｉｅ Ｃ Ｌ，Ａ ｈｙｂｒｉｄ ａｐｐｒｏａｃｈ ｆｏｒ ｃｏｎｃｕｒｒｅｎｔ ｓｗａｒｌ／１ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ．Ｃｏｍｐｕｔｅｒ ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ ｄｅｃｉｓｉｏｎ［Ｊ］．２００９，３０（１７）：４０７４．４０７６． ［１４］Ｗａｎｇ Ｔ Ｙ，Ｗｕ Ｋ Ｂ，Ｌｉｕ Ｙ Ｗ．Ａ ｓｉｍｕｌａｔｅｄ ａｎｎｅａｌｉｎｇ ｌａｇｏ— （上接第１２４页） ［１２］张沙清，陈新度，陈庆新，等．不确定环境下模具制造项 目群随机调度［Ｊ］．计算机集成制造统，２００９，１５（７）： １３８９．１３９６． Ｚｈａｎｇ Ｓｈａ－ｑｉｎｇ，Ｃｈｅｎ Ｘｉｎ—ｄｕ，Ｃｈｅｎ Ｑｉｎｇ—ｘｉｎ，ｅｔ ａ１．Ｓｔｏ－ ｃｈａｓｔｉｃ ｓｃｈｅｄｕｌｉｎｇ ｆｏｒ ｍｕｌｔｉｐｌｅ ｍｏｕｌｄ ａｎｄ ｄｉｅ ｍａｎｕｆａｃｔｕｒｉｎｇ ｐｒｏｊｅｃｔｓ ｕｎｄｅｒ ｕｎｃｅｒｔａｉｎｔｙ［Ｊ］．Ｃｏｍｐｕｔｅｒ Ｉｎｔｅｇｒａｔｅｄ Ｍａｎｕ— ｆａｃｔｕｒｉｎｇ Ｓｙｓｔｅｍｓ，２００９，１５（７）：１３８９－１３９６． ［１３］张沙清，陈新度，陈庆新，等．基于多步Ｑ学习的模具制 造项目群随机调度算法［Ｊ］．中国机械工程，２００９，２０ （１２）：１４３９－１４４５． Ｚｈａｎｇ Ｓｈａ—ｑｉｎｇ，Ｃｈｅｎ Ｘｉｎ—ｄｕ，Ｃｈｅｎ Ｑｉｎｇ－ｘｉｎ，ｅｔ ａ１．Ｓｔｏ— ｃｈａｓｔｉｃ ｓｃｈｅｄｕｌｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｍｕｌｔｉｐｌｅ ｍｏｕｌｄ ａｎｄ ｄｉｅ ｍａｎｕｆａｃｔｕｒｉｎｇ ｐｒｏｊｅｃｔｓ ｂａｓｅｄ ｏｎ ｍｕｌｔｉ—ｓｔｅｐ Ｑ ｌｅａｒｎｉｎｇ［Ｊ］． Ｃｈｉｎａ Ｍｅｃｈａｎｉｃａｌ Ｅｎｇｉｎｅｅｉｒｎｇ，２００９，２０（１２）：１４３９—１４５． ［１４］李英杰，陈庆新，陈新度，等．多属性虚拟企业部分并行 协商项目规划［Ｊ］．计算机集成制造系统，２００５，１１（６）： ｌａｙｏｕｔ ｄｅｓｉｇｎ ｏｆ ｃｅｌｌ ａｎｄ ｔｈｅｉｒ ｆｌｏｗ ｐａｔｈｓ ｉｎ ａ ｔｒｅｅ ｃｏｎｆｉｇｕｒａ— ｔｉｏｎ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｐｒｏｄｕｃｔｉｏｎ Ｒｅｓｅａｒｃｈ， ２０００，３８（４）：８９５－９２８． ８１Ｏ一８１７． Ｌｉ Ｙｉｎｇ－ｊｉｅ，Ｃｈｅｎ Ｑｉｎｇ—ｘｉｎ，Ｃｈｅｎ Ｘｉｎ－ｄｕ，ｅｔ ａ１．Ｐａｒｔｉｌａｌｙ ｐａｒａｌｌｅｌ ｍｕｌｔｉ－・ｉｓｓｕｅ ｎｅｇｏｔｉａｔｉｏｎ ｏｆｒ ｐｒｏｊｅｃｔ ｓｃｈｅｄｕｌｉｎｇ ｉｎ ｖｉｒ・ ｔｕａｌ ｅｎｔｅｒｐｒｉｓｅ［Ｊ］．Ｃｏｍｐｕｔｅｒ Ｉｎｔｅｇｒａｔｅｄ Ｍａｎｕｆａｃｔｕｒｉｎｇ Ｓｙｓ— ｔｅｒｎｓ，２００５，１１（６）：８１０－８１７，８５０． ［１５］Ｗｕ Ｌ Ｈ，Ｃｈｅｎ Ｘ，Ｃｈｅｎ Ｘ Ｄ．Ｔｈｅ ｒｅｓｅａｒｃｈ ｏｎ ｐｒｏａｃｔｉｖｅ— ｒｅａｃｔｉｖｅ ｓｃｈｅｄｕｌｉｎｇ ｆｒａｍｅｗｏｒｋ ｂａｓｅｄ ｏｎ ｒｅａｌ・－ｔｉｍｅ ｍａｎｕｆａｃ・・ ｔｕｒｉｎｇ ｉｎｆｏｒｍａｔｉｏｎ［Ｊ］．Ｍａｔｅｒｉａｌｓ Ｓｃｉｅｎｃｅ Ｆｏｒｕｍ，２００９（６２６— ６２７）：７８９－７９４． ［１６］袁健．几种新的混合遗传算法研究［Ｄ］．长沙：湖南大 学，２００７． Ｙｕａｎ Ｊｉａｎ．Ｔｈｅ Ｒｅｓｅａｒｃｈ ｏｆ Ｓｅｖｅｒａｌ Ｎｅｗ Ｋｉｎｄｓ ｏｆ Ｈｙｂｒｉｄ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ［Ｄ］．Ｃｈａｎｇｓｈａ：Ｈｕｎａｎ Ｕｎｉｖｅｒｓｉｔｙ， ２００７． ［１７］王凌．车间作业调度及其遗传算法［Ｍ］．北京：清华大学 出版社，２００３，１３８—１４４．
