基于DMPSO的单元集成设计方法

本资料包含pdf文件1个，下载需要1积分

成组技术是-种基于将-般工作组织起来，以改进生产系统效率的生产技术叫。单元制生产方式有许多优势，包括减少物流成本，缩小使用面积，改善库存等。其作为-种先进的生产方式，更好地适应了目前的市撤境，解决了生产规模与生产柔性之间的矛盾 引。单元形成和单元布局是设计单元收稿日期：2012-10-10； 修回日期：2012-12-10基金项目：上海市自然科学基金资助项目(1OzR14317O0)作者简介：郑永前(1965-)，河南商丘人，副教授，博士，主要研究方向为生产系统工程与管理，先进制造技术，企业信息化技术与应用。

工 业 工 程 与 管 理 第 4期生产系统的最重要步骤4]。在已有文献中，主要研究单个独立方向甚至是某个方向内的部分内容。独立研究布局的有：王定益[5]运用连续平面布置模型解决单元布局问题；高成冲[6 运用模糊理论与系统仿真解 决 系统布局 问题♀决集 成 问题 的有：wANG[ 提出了同时求解单元内设施布局和单元系统布局的方法，但不考虑设施和单元的距离约束；Shahram等[8]使用 QAP模型求解单元系统布局和单元设施布局；郑永前等g]集成了单元构造和单元间布局，并使用割树策略求解问题。上述集成问题不考虑空间约束，且集成模型涵盖的拈有限。

本文考虑设施和单元的距离约束、空间约束、设施的摆放方向，提出了对单元设计的两个阶段进行集成优化的方法，为方便比较，以最携物料搬运成本和占地面积为目标，建立 目标独立的多 目标优化模型，并利用动态多种群粒子群算法对模型求解。

2 单元设计问题建模本文假定：(1)单元采用 U型布局方式；(2)单元多行排列；(3)布局场地与设施均为矩形；(4)设施摆放方式有横纵两种。

现对单元形成和单元布局进行优化，使得设施占地面积和物料搬运成本两个目标最校为方便描述，引入以下符号：单元编号 C(c-1，2，，C)，零件编号 x(x-1，2，，X)，设施编号 i(i-l，2，，，)，(z ，Y )为设施 i的中心点坐标；设施 i的长和宽为 len ，wid 。

2.1 设施面积为提高单元的空间利用率，要求设施总面积最小，其数学模型描述为S- Y-max(xj，)-min(x )]·I-max(yjr)-min(y )]i，J- 1，2， ，m (1)式中，S表示整体面积，(z ，Y )表示设施 i的左下角坐标，( ，Yjt)表示设施 的右上角坐标。

2.2 物流成本本文将物料搬运距离设为物流成本，其数学模型可描述为M M P∑∑∑np ceil(V/Hp)(f 。- I1 Y - )i-1 J- 1 P- 1(2)式中， 为加工零件P时，该零件从设施 i到设施的转移次数； 为零件 P的需求量；H 为零件 P的搬运批量；ceil表示对数值进行向上取整；本文取欧氏距离作为设施间距。

2.3 约束与假设考虑到实际情况，假设 ：(1)设施的 I/0口设为该设施的中心点；(2)所在行相同的设施，其中心点处于同-水平线；(3)单元间布局采用多行布局，当在某-行增加-新单元且其长度大于设施规划长度，则 自动换行。

2.4 目标函数本文考虑的单元设计问题有两个 目标，属于多目标优化问题。求解多目标优化问题即为求问题的Pareto最优解集，但 已有的相关研究主要采取非Pareto解法，例如加权法等，其求解与搜索效率皆不佳。本文模型采用 Pareto解法。

数学模型可描述为M M PminZ-∑∑∑72p ceil(Vp/Hp)i-1 J- 1 p- 1(1五- lI Y -YJ) (3)minS-I-max(xjr)-min(x )]I-max(yj，)-min(y)] (4)s.t。

0.5l ≤ z ≤ h-0.5l i- 1，，j (5)0.5wi≤ Y ≤ 72-0.5w i- 1， ，j (6)R∑S -1，i-1，2，，N (7)r- 1N∑s ≤N，r-1，2，，R (8)[z -(Xc'bLdb)]·[( L )-z ]≥ 0，S - So' (9)Ey -(YdbWdb)]·[( W )-Yc'b]≥ 0，S ≠ S ， (10)l z -xj l≥ ( h )/2dh ，Y -YJ(11)l Y -YJ I≥ ( )/2dvo，Y ≠ YJ(12)式中，约束 5和约束 6保证每台设施在整个设施布置区域内都可选，且满足布局空间约束。约束条件(7)表示每-设施所在行数是唯-的；(8)表示单行设施数小于等于设施总数；(9)表示若设施 i， 同-行，则设施的拓扑形状在 X方向上不重叠l(10)表示若设施 i，J不同行，则设施的拓扑形状在 Y方向上不重叠。若设施 i和 在同-行，则满足约束条件(11)；若设施 i和 在相邻行，则满足约束条件(12)。其中，h ，Vi分别表示设备i的横向和纵向长- 1 1 - 第18卷 郑永前，等：基于DMPSO的单元集成设计方法度，当设备横向摆放时，h -z ， 产Wi，否则，h W ，73 Z ；dh 为单元内设备间的横向安全距离，dvo为单元内设备间的纵向安全距离；式(11)、式(12)保证设备 i和J保持-定的安全距离。

3 算法设计3.1 基本粒子群算法粒子群算法[u (PsO)属于进化算法的-种，和遗传算法相似，通过迭代寻找最优解，通过适应度来评价解的品质。在算法中，粒子通过追随当前搜索到的两个最优值来寻找全局最优；-个是粒子本身搜索到的最优解，称为个体极值(P )；另-个是整个种群搜索到的最优解，称为全局极值(G )。通过两个最优解，粒子根据下式更新 自己的速度和位置。

k 1叫· k c1·rand ·(P - z k)C2·rand·(G - z k) (15)五 k 1--X k k 1 (16)-∞ - (∞ -(-Oral )/T×t (17)式中，C ，C。为加速系数，rand为[0，1]之间的随机数， 为第i个粒子在第k次迭代中的位置，P 为第i个粒子历史最优， 为整个种群的历史最优。

为设定的约束系数，其中，Orna ，COIni 为设定常量，T是算法最大迭代数，t为已迭代的次数。

3.2 粒子更新在单目标粒子群算法中，主要研究算法的改进。

但在多目标情况下，还需要研究两个极值的选龋在评价 P 时，若-个解支配另-个解，则可确定较优解；若两个解互不支配，则需要-个新的评价方式，来确定哪个解较优，这是-个难点。另外 G -般为-组非劣解的解集，而不是单 目标中的唯-解，要搜索并选择合适的解是另-个难点。本文采腮于粒子个体密度值的外部档案维护策略，有效解决了上述两个问题，如下所示。

(1)P 的选龋若粒子 k的解a 支配P ，则Pest-a ；反之，保持不变。若两者互不支配，则计算两者的个体密度值，若ak个体密度值小于P 的个体密度值，则 P -a ；反之，保持不变。该策略选取个体密度值较小的解淘汰外部档案中的个体密度值较大的解。因为当新解密度值较小时，说明在其领域中选人外部档案的粒子数很少，为了保证解的多样性和均匀性，故选取个体密度值最小的解替代外部档案中的部分解。本文定义个体密度值为- 1 2 - Lk-1/min(√∑(ag- i)a) /-i-1/ r ----------- 、min(./ (a/-口；) )，l≠k；l，k-1，，NI， -i-l(18)其中，口 为非支配解，n为粒子维度，i为该解的第i维值，Np为外部档案内解的个数，a 、az为外部档案中的解。

(2)G 的选权立外部档案，设定档案大小，将每次迭代的G 放人档案中，并排序。若档案已满，将新加入值依次与档案值进行比较，当新值优于档案内某值时，将新值插入该值前面，并剔除末尾值。

(3)粒子的更新。以轮盘赌方式在外部档案中为每个粒子独立随机选取-个值，作为其 G 。每个粒子所获得的G 各不相同，这意味着粒子将沿着不同的方向飞行，保持粒子的多样性，提高算法的探索能力。

3.3 动态多种群粒子群优化算法(DMPSo)粒子群优化(PSO)算法是-种优秀的群体智能算法，已经广泛应用于求解各类复杂优化问题。目前针对 PSO有大量的改进算法，但其主要研究粒子的再生、替换等。而本文提出了-种新型的动态多种群粒子群优化算法。

普通的算法中，每个粒子都与系统中的其他粒子相连，此时粒子问信息的交互比较完善，导致粒子的收敛速度快，全局搜索能力较强，但容易陷入局部最优，出现早熟现象。根据式(18)计算得出各粒子的个体密度值，当其的最大值和最小值相差很大时，说明粒子的多样性不是很好，全局的搜索能力不强，需要增强粒子的全局搜索能力；反之，则需要增强局部搜索能力。

本文认为影响该算法收敛速度和精度的另-个主要因素是粒子的两个极值♂合上述思想，本文将所有粒子分成 N个种群，引人广义全局极值和狭义全局极值的概念，提出-种新的粒子更新方式。

各种群内部有各自的种群极值，定义为狭义全局极值(G )。而整个粒子群的极值，定义为广义全局极值(A )。每个粒子的速度更新方式有了改变k 1- ∞ ·73 k cl·rand ·(P -z k)c2·rand ·( - z k) C3·rand ·( n- .72 k)(2O)(21)第 18卷 郑永前，等 ：基于 DMPSO的单元集成设计方法表3 产品工艺路线 面积。

传统方法是将单元形成与单元布局分开求解，首先使用聚类等方法划分制造单元，再利用智能优化算法进行设备排序，以满足目标。在文献E4]、[9]中，都对模型和算法进行了改进。文献[4]集成了单元内布局与单元间布局，文献[9]集成了单元形成与单元间布局。

本文采用标准算法设定，最大迭代次数 Gen-800，种群规模 S z8-80，连续无进化代数 N-200，惯性系数权重 e瑚 -0.9，最小惯性系数 ‰ ：O.4，学习参数 c -cz-2。外部档案数量 NP5。布局车间面积为 25m×20m，设施安全距离为 1.2m，单元间距为 3.0m。

用上述四种方法对模型进行求解，各组实验取30个数据，结果如表 4所示。经过测试，该案例种群数 N4时所得解较优，故本文试验皆采用 4组种群进行运算。表中，Min表示运算结果中目标函数的最小值，Average表示 目标 函数 的平均值。

Dist/Area分别表示物料搬运成本以及整体布局表4 不同数学模型求解结果比较(四个单元)传统方法文献[5]文献[9]本文417640774048332。

表4中的传统方法，其特点为将单元设计问题划分成三步进行求解；文献[5]、[9]NIJ稍进-步，将问题中的两部分集成，分为两步求解。这三种模型的局限性在于各单元相互孤立研究，造成解空间损失。分析表中数据可知，传统的单元布局设计方式所得结果最差，而经过部分集成后的模型对结果有相应提高，特别是面积成本大幅下降，而本文集成模型所得结果优于以上三个模型。故利用并行工程思想的集成优化模型是有效且较优的。

表 5 集成模型不同算法求解结果比较(四个单元)从表 5所得到的对比结果可以看出，DMPSO算法运算速度尚可，但运算结果明显优于其他算法。

同时，针对不同规模大小的布局问题，分别使用传统模型和本文提出的集成模型求解，所得最优结果如表 6所示。通过分析可知，当问题规南小时，传统模型与本文模型差别不大；当规模逐渐扩大时，本文模型的优势也随之凸显。故该模型不仅适用于各规模问题，在处理大规模布局问题时，效果更佳。

表 6 不同规模问题求解结果比较0 2 0 6 7 1 0 83 6 4 3 3 2 2 2 / / / / 1 O 9 9 1 9 8 2 l 0 O O 4 4 4 4 工 业 工 程 与 管 理 第 4期5 结束语本文研究解决了单元构造和单元布局的集成问题，以最小物流成本和使用面积为目标，充分考虑了单元在形成初期直到布局完成各阶段的交互作用；考虑了单元布局对单元形成的要求，有利于资源的更好利用和效率的提升。本文提出的基于结构化编码的DMPSO算法有效解决了多目标制造单元构建过程的难题；设计的择优策略和粒子更新方法既发挥了PSO算法搜索快速、覆盖面大的特点，又使算法不快速收敛陷人局部最优，提高了求解质量。通过仿真实验，证明了集成优化模型的可行性和实用性；证明了本文提出的算法在多 目标集成布局问题中表现优越。