《基于分散搜索算法的单元构建与布局设计的并行研究》由会员分享，可在线阅读，更多相关《基于分散搜索算法的单元构建与布局设计的并行研究（11页珍藏版）》请在金锄头文库上搜索。
1、基于分散搜索法的单元构建与布局设计的并行研究摘要：设计单元制造系统的两个决定性因素是单元成形和单元布局。在解决单元构建问题时，决定了机器组和和相应的零件族；在解决设备布局问题时，决定了设备在单元内的位置与单元之间的相对位置。实际生产中，这两个问题是互相影响的，并行的解决单元构建与单元布局能够设计出一个高效的单元制造系统。一些非常重要和实际的因素例如单元内的布局、单元间的布局、操作顺序、零件需求量、物流批量、单元数、单元大小和可选操作路径等都结合在了数学模型中。 分别用多目标分散搜索法、非支配遗传算法（NSGA-II）、-约束法求解。有文献采用了这些方法解决这九个问题。对这个问题的参数进行敏感性
2、分析，能够得到参数对于目标函数值的影响。结果表明，多目标分散搜索法比非支配遗传算法（NSGA-II）更易于操作，并且得到更优的目标值。关键词：单元制造系统 单元构建 布局设计 多目标规划 分散搜索法 NSGA-II1 背景介绍单元制造是成组技术在制造领域中的一个重要应用。在单元制造系统中，相似的零部件被聚类为零件族。同样地，机器组成机器单元。零件族是在相应的机器单元内加工。单元制造系统具有流水线生产和加工车间生产优点，能够像流水线生产那样高效，也具备了加工车间的柔性。因此，单元制造模式是一个能够减少在制品数、缩短反应时间，减少加工成本、降低瑕疵率、缩短斜升时间和工件运输时间、简化操作和提高产品
3、质量的比较令人满意的制造哲学1, 2。Wemmerlove和Hyer 3把单元制造系统的相关问题归结为以下四类：1、单元成形：把零件划分为零件族并将机器组成机器组；2、布局设计：包括单元内的布局设计与单元间的布局设计；3、成组时序安排：零件根据相应的生产计划进行生产；4资源的分配。Singh 4定义了三个设计单元制造系统的问题：1单元成形；2单元内的布局；3单元间的布局。Heragu 5 和 Jajodia et al. 6在设计单元制造系统中定义了三个相似的阶段，在第一阶段对零件和机器聚类，在后续的两个阶段最优化零件加工成本。通过对上述学者的观点分类，可知单元成形和单元布局是能否成功设计单元
4、制造系统的决定性因素。针对单元成形问题，零件划分为零件族和机器划分为机器组是就零件之间的可视相似性和操作顺序而言的。很多学者已经针对这个问题构建了不同的模型方法。Selim et al7针对这些方法做了相关总结，Papaioannou 和Wilson 8也对解决单元成形的方法做了归纳，单元成形问题的解决结果通常表示为零件机器分块矩阵，分块矩阵的每一个块代表一个制造单元。块外的元素叫做例外元素表明了单元间的物流，如图1所示。研究者在解决单元成形问题时，往往通过减少例外元素个数或者最大化单元内的相似系数。Miltnberg 和 Zhang 9、Shafer 和 Regres10以及YinandYa
5、suda11针对零件的相似系数做了大量工作，读者可以参考。布局设计问题包括单元间的布局设计和单元内的布局设计。单元内的布局设计是指机器在制造单元内的位置，单元间的布局设计是单元的位置。布局设计的目标是减少物料的流动费用。布局的形式线型、并行和环形等。Hassan 12针对单元制造系统的不同布局形式做了相关比较。在单元制造系统的单元成形与布局设计之间存在一定的交互作用。Arvind 和Irani 13对设计单元制造系统的交互作用做了深入的研究。通过解决单元成形问题决定了零件族和机器组。当机器单元发生改变，意味着需要把一个机器从一个单元移动到另一个单元，则单元内的布局也就发生改变。例如，假设单元内
6、的布局方式是直线型的，当改变单元成形结果，直线型布局中的最优次序的机器位置就会不同。同样，为了减少单元间的物流成本，单元间的布局也需要重新规划。此外，每个单元的大小受单元内的机器种类以及数量的影响。另一方面，为了减少原材料总的处理成本，机器有时会需要移动到其它的单元内。当出现物料的反向流动、机器不匹配、机器重复时这种交互作用变的更明显。在单元内布局与单元间布局同样地也存在交互作用。当单元之间有物料流动时，单元内的布局发生改变，单元间的布局也会发生改变。单元间的重新布局是为了减少单元间的物流成本。同样地，单元间的布局也会影响单元内的布局。2.相关文献国内外的学者针对单元制造系统做了大量的研究工作
7、，主要集中在单元成形和单元布局这两个问题上。Vakharia 和 Wemmerlov 14研究了单元制造系统的三个问题：零件族、机器组和直线型布局。他们使用四阶段分析法来解决这个问题。基于操作次序的相似性系数也被应用在方法中。目标函数是最小化单元的闲置率与成本。Akturk 和Balkose15使用多目标数学模型解决单元成形和单元布局问题，并使用遗传算法求解模型。模型中优化的六个目标是最小化基于设计的相异性、加工属性和加工次序、单元负荷、机器负荷、机器购置成本、跨单元流动等。模型中机器数目与单元数目是决策变量。Chan et al. 16将遗传算法应用到二次规划中解决单元成形和单元布局问题。第
8、一步，最小化单元矩阵块外的例外元素与矩阵块内的非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等采用了
9、一个特例研究、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 Partmachinematrixforaproblemwit
10、h10partsand10machines表1 CMS设计分类的文献总结Table 1 Summary of the literature on CMS design attributes3 问题规划3.1问题描述和假设本文综合了CMS中的单元成形和单元规划问题。模型的目标是最少化单元块外的例外元素，从而减少跨单元加工；最少化单元块内的无效元素，从而最大化单元利用率。图1指出了例外元素和无效元素。除此之外，模型还最小化了单元间与单元内的物流费用。零件族、机器组、单元内布局和单元间布局也可由这个问题求解可得。单元大小限制通过提前规定单元内的预备机器位置实现的。为了构造模型做出如下假设：1、被加工
11、的零件种类是可知的。零件的加工顺序也是可知的，此外每个加工操作都必须完成。2、每种机器只用一个。3、每种零件的市场需求量可知，并且得到满足。4、材料是成批运输且批量大小可知。5、一个零件可能有多种加工路。当操作次序不重要，或者一种机器能够完成多种操作，每种零件就有多种加工路径。但是最终每种只能选择一种加工路径。6、单元内和单元间的物料流动用材料的单位处理费用表示。单元间的单位处理费用远远大于单元内的费用，因此减少单元间的物料流动非常必要。7、单元数目是模型的已知变量。8、假设机器的大小对距离没有影响。9、每个单元的可放置机器位置决定的单元的大小，总共的位置大于机器的数量。3.2数学模型的构造模
12、型的相关数列集合包括：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单元间的
13、原料转移次数。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） 第一个目标函数是为了最小化例外元素的总个数（机器零件矩阵块外的元素），由于在内，
14、例外元素考虑了两次，因此引入系数1/2。第二个目标函数通过最小化每个单元块内的无用元素从而最大化单元的利用率。式中表示单元块的大小。例如图1中，第一个单元即左上角的单元块，因为有四种零件和三种机器，所以；二式中表示单元块内的有效元素，在图1的第一个单元内其大小是9。因此图1的第一个单元的值是3。第三个目标函数是最小化跨单元物料流动的总费用。式中表示用于加工零件i在路径r下的第j道工序所用的机器。零件需求量、批量大小、移动距离、单位费用都综合在了这个方程中。类似地，单元内的物料流动费用通过方程（4）优化。和的值通过机器的位置与单元间的位置决定。在这个模型中，单元内机器的布局与单元之间的布局都采用线性的布局方式。但是这个模型并不是严格要求线性布局方式，如果已知相应的距离矩阵，相应的布局方式也可以应用到上述模型中。需要说明的是，满足方程（1）减少单元间的移动次数，并不一定就满足方程（4）中的最优解要求，因为在这个模型中考虑的距离的影响。约束（5）限制每种零件只能选择一种加工路径。约束（6）限制每种零件只能分配到一个单元内。同样地，约束（7）限制每种机器只能分配到一个单元内。约束（8）保证每个机器只能分配到一个位置上，当机器总数等于预备位置总数时，两边取等号。约束
