基于分散搜索算法的单元构建与布局设计的并行研究.doc

基于分散搜索法的单元构建与布局设计的并行研究摘要：设计单元制造系统的两个决定性因素是单元成形和单元布局。在解决单元构建问题时，决定了机器组和和相应的零件族；在解决设备布局问题时，决定了设备在单元内的位置与单元之间的相对位置。实际生产中，这两个问题是互相影响的，并行的解决单元构建与单元布局能够设计出一个高效的单元制造系统。一些非常重要和实际的因素例如单元内的布局、单元间的布局、操作顺序、零件需求量、物流批量、单元数、单元大小和可选操作路径等都结合在了数学模型中。 分别用多目标分散搜索法、非支配遗传算法（NSGA-II）、-约束法求解。有文献采用了这些方法解决这九个问题。对这个问题的参数进行敏感性分析，能够得到参数对于目标函数值的影响。结果表明，多目标分散搜索法比非支配遗传算法（NSGA-II）更易于操作，并且得到更优的目标值。关键词：单元制造系统 单元构建 布局设计 多目标规划 分散搜索法 NSGA-II1 背景介绍单元制造是成组技术在制造领域中的一个重要应用。在单元制造系统中，相似的零部件被聚类为零件族。同样地，机器组成机器单元。零件族是在相应的机器单元内加工。单元制造系统具有流水线生产和加工车间生产优点，能够像流水线生产那样高效，也具备了加工车间的柔性。因此，单元制造模式是一个能够减少在制品数、缩短反应时间，减少加工成本、降低瑕疵率、缩短斜升时间和工件运输时间、简化操作和提高产品质量的比较令人满意的制造哲学1, 2。Wemmerlove和Hyer 3把单元制造系统的相关问题归结为以下四类：1、单元成形：把零件划分为零件族并将机器组成机器组；2、布局设计：包括单元内的布局设计与单元间的布局设计；3、成组时序安排：零件根据相应的生产计划进行生产；4资源的分配。Singh 4定义了三个设计单元制造系统的问题：1单元成形；2单元内的布局；3单元间的布局。Heragu 5 和 Jajodia et al. 6在设计单元制造系统中定义了三个相似的阶段，在第一阶段对零件和机器聚类，在后续的两个阶段最优化零件加工成本。通过对上述学者的观点分类，可知单元成形和单元布局是能否成功设计单元制造系统的决定性因素。针对单元成形问题，零件划分为零件族和机器划分为机器组是就零件之间的可视相似性和操作顺序而言的。很多学者已经针对这个问题构建了不同的模型方法。Selim et al7针对这些方法做了相关总结，Papaioannou 和Wilson 8也对解决单元成形的方法做了归纳，单元成形问题的解决结果通常表示为零件机器分块矩阵，分块矩阵的每一个块代表一个制造单元。块外的元素叫做例外元素表明了单元间的物流，如图1所示。研究者在解决单元成形问题时，往往通过减少例外元素个数或者最大化单元内的相似系数。Miltnberg 和 Zhang 9、Shafer 和 Regres10以及YinandYasuda11针对零件的相似系数做了大量工作，读者可以参考。布局设计问题包括单元间的布局设计和单元内的布局设计。单元内的布局设计是指机器在制造单元内的位置，单元间的布局设计是单元的位置。布局设计的目标是减少物料的流动费用。布局的形式线型、并行和环形等。Hassan 12针对单元制造系统的不同布局形式做了相关比较。在单元制造系统的单元成形与布局设计之间存在一定的交互作用。Arvind 和Irani 13对设计单元制造系统的交互作用做了深入的研究。通过解决单元成形问题决定了零件族和机器组。当机器单元发生改变，意味着需要把一个机器从一个单元移动到另一个单元，则单元内的布局也就发生改变。例如，假设单元内的布局方式是直线型的，当改变单元成形结果，直线型布局中的最优次序的机器位置就会不同。同样，为了减少单元间的物流成本，单元间的布局也需要重新规划。此外，每个单元的大小受单元内的机器种类以及数量的影响。另一方面，为了减少原材料总的处理成本，机器有时会需要移动到其它的单元内。当出现物料的反向流动、机器不匹配、机器重复时这种交互作用变的更明显。在单元内布局与单元间布局同样地也存在交互作用。当单元之间有物料流动时，单元内的布局发生改变，单元间的布局也会发生改变。单元间的重新布局是为了减少单元间的物流成本。同样地，单元间的布局也会影响单元内的布局。2.相关文献国内外的学者针对单元制造系统做了大量的研究工作，主要集中在单元成形和单元布局这两个问题上。Vakharia 和 Wemmerlov 14研究了单元制造系统的三个问题：零件族、机器组和直线型布局。他们使用四阶段分析法来解决这个问题。基于操作次序的相似性系数也被应用在方法中。目标函数是最小化单元的闲置率与成本。Akturk 和Balkose15使用多目标数学模型解决单元成形和单元布局问题，并使用遗传算法求解模型。模型中优化的六个目标是最小化基于设计的相异性、加工属性和加工次序、单元负荷、机器负荷、机器购置成本、跨单元流动等。模型中机器数目与单元数目是决策变量。Chan et al. 16将遗传算法应用到二次规划中解决单元成形和单元布局问题。第一步，最小化单元矩阵块外的例外元素与矩阵块内的非1元素。第二步，最小化单元间与单元内的物料流动费用。Dahel 17将单元成形、单元布局、斜升时间、加工时间、零件需求、加工次序以及其他一些因素例如机器能力限制、单元大小限制都考虑在了模型内。作者用了约束松懈的方法来求解数学模型。其他的一些研究包括：Kakuturi 18, Alfa et al. 19,Liao et al. 20, Irani et al. 21, Akturk 22, Harhalakis et al.23等采用了顺序分支法、Bazargan-Lari et al. 24, Xu25, Urban et al. 26等采用了一个特例研究、Lee和Chiang 27,28, Dixi和Mishra 29用图论、Akturkand Turckan 30采用了合弄理论、Ahi et al. 31采用了MCDM技术以及Krishnan et al. 32的应用关系图最小化机器间物流的方法。一些学者还研究了布局类型在单元成形结果上的一些影响。Arvindh 和Irani 13建议使用交互作用法来解决两个问题：第一个问题是零件族、机器组和重复机器之间的联系；第二个问题是单元布局问题，包括单元内与单元外的布局。图1 10种零件与10种机器的零件-机器矩阵Fig.1 Partmachinematrixforaproblemwith10partsand10machines表1 CMS设计分类的文献总结Table 1 Summary of the literature on CMS design attributes3 问题规划3.1问题描述和假设本文综合了CMS中的单元成形和单元规划问题。模型的目标是最少化单元块外的例外元素，从而减少跨单元加工；最少化单元块内的无效元素，从而最大化单元利用率。图1指出了例外元素和无效元素。除此之外，模型还最小化了单元间与单元内的物流费用。零件族、机器组、单元内布局和单元间布局也可由这个问题求解可得。单元大小限制通过提前规定单元内的预备机器位置实现的。为了构造模型做出如下假设：1、被加工的零件种类是可知的。零件的加工顺序也是可知的，此外每个加工操作都必须完成。2、每种机器只用一个。3、每种零件的市场需求量可知，并且得到满足。4、材料是成批运输且批量大小可知。5、一个零件可能有多种加工路。当操作次序不重要，或者一种机器能够完成多种操作，每种零件就有多种加工路径。但是最终每种只能选择一种加工路径。6、单元内和单元间的物料流动用材料的单位处理费用表示。单元间的单位处理费用远远大于单元内的费用，因此减少单元间的物料流动非常必要。7、单元数目是模型的已知变量。8、假设机器的大小对距离没有影响。9、每个单元的可放置机器位置决定的单元的大小，总共的位置大于机器的数量。3.2数学模型的构造模型的相关数列集合包括：i零件编号，i=1, n。r零件加工路径编号,r=1,2,Ri。m, m机器编号, m=1,2,M。j操作编号, j=1, Jir。c, c单元编号, c 、c=1, C。p, p机器位置编号, p 、p=1, UC。模型的变量：Di零件i的需求量。Bi零件i的批量大小。C单元数。UC可放置机器位置的最大数目。Ri零件i的加工路径数目。Jir零件i在路径r下的操作数目。单元间的材料运输费用。单元内的材料运输费用。dAC(m,m)单元内机器m和m间的距离。dEC(c,c)单元c和单元c间的距离。irm=1，如果零件i在路径r下需要使用机器m加工；其它irm=0。Ne单元间的原料转移次数。Nv单元内的单位转移次数。IE单元间的转移总费用。IA单元内的转移总费用。决策变量：Zir=1，如果零件i选择加工路径r，其它Zir=0;Vic=1,如果零件i分配到单元c，其它Vic=0；Xmc=1，如果零件i分配到单元c，其它Xmc=0；Ympc=1，如果机器m分配到单元c的p位置，其它Ympc=0。综合单元成形和单元布局的数学模型的目标函数如下： (1) (2) （3） （4）约束条件为： ； （5） ； （6） ； （7） ,； （8）； （9） ，； （10） ，； （11），； （12） 第一个目标函数是为了最小化例外元素的总个数（机器零件矩阵块外的元素），由于在内，例外元素考虑了两次，因此引入系数1/2。第二个目标函数通过最小化每个单元块内的无用元素从而最大化单元的利用率。式中表示单元块的大小。例如图1中，第一个单元即左上角的单元块，因为有四种零件和三种机器，所以；二式中表示单元块内的有效元素，在图1的第一个单元内其大小是9。因此图1的第一个单元的值是3。第三个目标函数是最小化跨单元物料流动的总费用。式中表示用于加工零件i在路径r下的第j道工序所用的机器。零件需求量、批量大小、移动距离、单位费用都综合在了这个方程中。类似地，单元内的物料流动费用通过方程（4）优化。和的值通过机器的位置与单元间的位置决定。在这个模型中，单元内机器的布局与单元之间的布局都采用线性的布局方式。但是这个模型并不是严格要求线性布局方式，如果已知相应的距离矩阵，相应的布局方式也可以应用到上述模型中。需要说明的是，满足方程（1）减少单元间的移动次数，并不一定就满足方程（4）中的最优解要求，因为在这个模型中考虑的距离的影响。约束（5）限制每种零件只能选择一种加工路径。约束（6）限制每种零件只能分配到一个单元内。同样地，约束（7）限制每种机器只能分配到一个单元内。约束（8）保证每个机器只能分配到一个位置上，当机器总数等于预备位置总数时，两边取等号。约束（9）保证一种机器只能放置在一个单元内的一个位置上。约束（10）保证分配到一个单元内的机器按照先后顺序安排在每个位置上，即第一个机器分配到单元内的第一个位置上，第二个机器分配到单元内的第二个位置上，以此类推。这使得一个单元内的两个机器之间没有空留的位置。约束（11）表示两变量之间的关系。约束（12）表示变量的类型。3.3模型的线性化由于求解这个模型的计算时间很长，因此使用一些线性化方法将目标函数中的非线性项消去或者转变为线性的。这个模型可以通过增加辅助变量和约束实现线性化。在这一部分，模型中的四个非线性项分别通过下述方法线性化。1、方程（1）中的非线性项表示单元间物料流动的次数,可以通过增加以下一系列约束将其转换为:， （13）， （14） （15） （16）式中的和是边界变量。证明过程如下：如果，则在线性化过程中增加约束（13）和（14），则可能出现以下四种情形：（a）如果，则和都为零。根据目标函数与约束条件，则=0。（b）如果，则和也都为零。同上，=0。（c）如果和中的一个是1，另一个是0，根据约束（13）和（14）可得。因此。（d）同上。因此，。非线性项通过约束（15）和（16）线性化，并定义边界变量。存在如下四种可能的情形：(a)如果，则。根据约束（15）则。(b)如果，则。则。(c)如果变量和不全等于1，则，且。根据约束（16）。（d）同上。2、方程（2）中的非线性项可以通过定义边界变量和增加约束的方法转化为。相应的约束如下： （17） （18）与上述证明方法相似。3、方程（3）中计算物料在单元件流动费用的非线性项通过增加边界变量和以下约束使之线性化： （19） （20） 这一项包含三个边界变量，线性化过程类似于方程（2）。4、方程（4）中计算单元内流动费用的非线性项 通过增加边界变量和下述约束使之线性化： （21） (22)证明过程同上。综上所述，线性模型如下所示： （23） （24） （25） （26）S.T约束（5）（11）约束（13）（22） （27）4.模型求解方法所求解问题是综合单元成形和单元布局设计的多目标问题。因此可以采用多层目标分析法求解问题。在多目标优化中可求得Pareto最优解集而不是单一最优解。最后由决策者根据决策标准或者功能性等要求从Pareto最优解集中选出最佳方案。解集中能够支配决定其它解的解称为非控解。图2描述了非控解与可控解。分别使用目标分散搜索法、非支配遗传算法（NSGA-II）、-约束法求解单元成形与单元布局问题，并比较求解结果。图2 可控解与非控解Fig.3 Dominated and non-dominated solutions4.1 -约束法-约束法是一个比较通用的解法，这个方法由Haimes et al. 44 首次提出。Chankong 和Haimes 45 比较全面的讨论了这种算法。算法中一个目标函数继续作为目标函数，其余的目标函数作为约束。CMS的上述数学模型可表示为：S.T.式中和分别是目标函数中和的权重，S是这个问题的可行域。目标函数是例外元素和无效元素权重值之和。第二个目标函数（）是单元内与单元间物料流动费用之和，将第二个目标函数作为一个新的约束处理。通过对分配不同的值，就可获得Pareto最优解集。将作为目标函数，作为新约束，求得结果并与文献比较。4.2多目标分散搜索法多目标分散搜索法是由Glover 46提出的元启发式算法的一种。它的原理是基于综合决策规则和替代约束。近年来有很多学者应用这种算法解决CMS的设计问题，（Aramoon Bajestan et al. 48, Tavakkoli-moghaddam et al. 49, Tavakkoli-moghaddam et al. 50,Rahimi-Vahedad et al. 51和 Wang et al. 52)。这种算法通过现有解来产生最优解。最初解通过多元化生成方法随机产生，并通过算法一步一步迭代得到最优解。多个较优解构成了算法中非常重要的参考集。参考集中的解可以通过子集的重新组合过程产生新的解。产生的新解改进后又和其他较优解构成了新的参考解集。搜索较优解的过程不断更新参考解集。当满足终止条件时循环结束，这种算法的特点将在后文中详细描述。4.2.1最初解的多元化生成方法最初解的产生通过多元化生成方法获得。解的各部分含义如图3所示。由图可知，一个新的解有三部分组成，第一部分代表机器组以及单元内、单元间的分布。数字代表机器的编号，S-数字代表单元内未放置机器的位置。图3表示的解是9个机器、10个零件、3个单元的问题。在例子中，单元内的最多位置数是4 (UC=4)，单元布局的形式如图4所示。整个线性布局的长度是C*UC。解的第二部分表示零件具体分配到哪一个单元内，也就是零件族通过第二部分决定，因为有十个零件所以这一部分的长度就是10。各个零件加工路径的选择在第三部分表示，第三部分的长度是n。因此，每个解的长度可以表示成(C*UC+n+n)，每个解都有三部分组成，并且每个解都满足约束条件的要求。Marti et al. 47 的方法可以用来产生解的第一部分。假设并且s,h,r都是整数，满足定义P（h）如下：一个新解可以通过上式要求产生。例如：当输入命令14，h=4时：因此一个新解就是：第二部分与第三部分的具体值则随意产生，即将任一零件随意分配到其他单元，零件的加工路径也随意选择。图3 解的含义Fig.3 Solution representation图4 满足解的含义第一部分要求的系统布局形式Fig. 4 Layout of the system according to section 1 of the solution representation4.2.2改进方法 通过多样化方法产生的初始解需要通过一些方法进行改进。这种方法能够使不可行解变成可行解，并提高其相应的品质。只需恰当地定义解的含义和组合方式，那么通过所介绍算法产生的解都是可行解。针对一个提前指定单元数目的问题，局部搜索的最优解就是单元内最优布局形式。为了找到每个单元内机器的最优次序可以把这种问题看做旅行商问题。因此，可以运用2-opt 和3-opt来改进单元内的布局。另一种方法是通过交换单元内两个机器的位置。此外，一个零件可能分配到一个没有该零件所需要机器的单元内。This method is used to make infeasible solutions feasi-ble and enhance the quality of the s