基于分散搜索法的单元构建与布局
设计的并行研究
摘要：设计单元制造系统的两个决定性因素是单元成形和单元布局。在解决单元构建问题时，决定了机器组和和相应的零件族；在解决设备布局问题时，决定了设备在单元内的位置与单元之间的相对位置。实际生产中，这两个问题是互相影响的，并行的解决单元构建与单元布局能够设计出一个高效的单元制造系统。一些非常重要和实际的因素例如单元内的布局、单元间的布局、操作顺序、零件需求量、物流批量、单元数、单元大小和可选操作路径等都结合在了数学模型中。 分别用多目标分散搜索法、非支配遗传算法（NSGA-II）、?-约束法求解。有文献采用了这些方法解决这九个问题。对这个问题的参数进行敏感性分析，能够得到参数对于目标函数值的影响。结果表明，多目标分散搜索法比非支配遗传算法（NSGA-II）更易于操作，并且得到更优的目标值。
关键词：单元制造系统 单元构建 布局设计 多目标规划 分散搜索法 NSGA-II
1 背景介绍
单元制造是成组技术在制造领域中的一个重要应用。在单元制造系统中，相似的零部件被聚类为零件族。同样地，机器组成机器单元。零件族是在相应的机器单元内加工。单元制造系统具有流水线生产和加工车间生产优点，能够像流水线生产那样高效，也具备了加工车间的柔性。因此，单元制造模式是一个能够减少在制品数、缩短反应时间，减少加工成本、降低瑕疵率、缩短斜升时间和工件运输时间、简化操作和提高产品质量的比较令人满意的制造哲学[1, 2]。
Wemmerlove和Hyer [3]把单元制造系统的相关问题归结为以下四类：1、单元成形：把零件划分为零件族并将机器组成机器组；2、布局设计：包括单元内的布局设计与单元间的布局设计；3、成组时序安排：零件根据相应的生产计划进行生产；4资源的分配。Singh [4]定义了三个设计单元制造系统的问题：1—单元成形；2—单元内的布局；3—单元间的布局。Heragu [5] 和 Jajodia et al. [6]在设计单元制造系统中定义了三个相似的阶段，在第一阶段对零件和机器聚类，在后续的两个阶段最优化零件加工成本。
通过对上述学者的观点分类，可知单元成形和单元布局是能否成功设计单元制造系统的决定性因素。针对单元成形问题，零件划分为零件族和机器划分为机器组是就零件之间的可视相似性和操作顺序而言的。很多学者已经针对这个问题构建了不同的模型方法。Selim et al[7]针对这些方法做了相关总结，Papaioannou 和Wilson [8]也对解决单元成形的方法做了归纳，单元成形问题的解决结果通常表示为零件—机器分块矩阵，分块矩阵的每一个块代表一个制造单元。块外的元素叫做例外元素表明了单元间的物流，如图1所示。研究者在解决单元成形问题时，往往通过减少例外元素个数或者最大化单元内的相似系数。Miltnberg 和 Zhang [9]、Shafer 和 Regres[10]以及YinandYasuda[11]针对零件的相似系数做了大量工作，读者可以参考。
布局设计问题包括单元间的布局设计和单元内的布局设计。单元内的布局设计是指机器在制造单元内的位置，单元间的布局设计是单元的位置。布局设计的目标是减少物料的流动费用。布局的形式线型、并行和环形等。Hassan [12]针对单元制造系统的不同布局形式做了相关比较。
在单元制造系统的单元成形与布局设计之间存在一定的交互作用。Arvind 和Irani [13]
对设计单元制造系统的交互作用做了深入的研究。通过解决单元成形问题决定了零件族和机
器组。当机器单元发生改变，意味着需要把一个机器从一个单元移动到另一个单元，则单元内的布局也就发生改变。例如，假设单元内的布局方式是直线型的，当改变单元成形结果，直线型布局中的最优次序的机器位置就会不同。同样，为了减少单元间的物流成本，单元间的布局也需要重新规划。此外，每个单元的大小受单元内的机器种类以及数量的影响。另一方面，为了减少原材料总的处理成本，机器有时会需要移动到其它的单元内。当出现物料的反向流动、机器不匹配、机器重复时这种交互作用变的更明显。在单元内布局与单元间布局同样地也存在交互作用。当单元之间有物料流动时，单元内的布局发生改变，单元间的布局也会发生改变。单元间的重新布局是为了减少单元间的物流成本。同样地，单元间的布局也会影响单元内的布局。
2.相关文献
国内外的学者针对单元制造系统做了大量的研究工作，主要集中在单元成形和单元布局这两个问题上。Vakharia 和 Wemmerlov [14]研究了单元制造系统的三个问题：零件族、机器组和直线型布局。他们使用四阶段分析法来解决这个问题。基于操作次序的相似性系数也被应用在方法中。目标函数是最小化单元的闲置率与成本。Akturk 和Balkose[15]使用多目标数学模型解决单元成形和单元布局问题，并使用遗传算法求解模型。模型中优化的六个目标是最小化基于设计的相异性、加工属性和加工次序、单元负荷、机器负荷、机器购置成本、跨单元流动等。模型中机器数目与单元数目是决策变量。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], Xu[25], 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 Part–machinematrixforaproblemwith10partsand10machines
AttributesabcVakharia and Wemmerlov [14]√√Logendran [34]Alfa et al. [19]Arvindh and Irani [13]√Dahel [17√√Akturk [22]√Harhalakis et al. [23]√√Liao et al. [20]√√√Gupta et al. [33]Akturk and Balkose [15]√Heragu and Kakuturi [18]√√√Bazargan-Lari et al. [24]√√Sarker and Xu [25]√√Akturk and Turkcan [30]√√Urban et al. [26]√Lee and Chiang [27]√Lee and Chiang [28]√Chiang and Lee [37]√Wu et al. [35]√√Chan et al. [16]√√Mahdavi and Mahadevan [39]Ming and Ponnambalam [38]Ahi et al. [31Paydar et al. [40]√√Dixit and Mishra [29]√√Paydar et al. [36]√√Krishnan et al. [32]多种加工路径分类a批量b需求量c操作次序d加工时间e单一/重复机器f机器购置费用g机器能力hReferenced√√√√√√√√√√√√√√√√√√√√√√√√ijklmnope√√√√√√√√fg√h√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√i√√j√√k√√√√√√√√√√√lmno√p√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√单元大小机器/单元利用率单元数/机器数限制机器/单元的形状/大小布局限制加工成本/时间反向物流交叉作业限制
表1 CMS设计分类的文献总结
Table 1 Summary of the literature on CMS design attributes
3 问题规划
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。 综合单元成形和单元布局的数学模型的目标函数如下：
MinNC??????irmZirC?1i?1r?1m?1CnRIMVic?Xmc2 (1)
MinNv?????(ZirVicXmc??irmZirVicXmc) (2)
c?1i?1r?1m?1CnRM