周 娜，徐克林，朱 伟

ZHOU Na, XU Ke-lin, ZHU Wei

（同济大学 机械工程学院，上海 201804）

面向OEM企业设备多行布局问题的遗传算法

Genetic algorithm for multi-row layout oriented OEM enterprise

周 娜，徐克林，朱 伟

ZHOU Na, XU Ke-lin, ZHU Wei

（同济大学 机械工程学院，上海 201804）

以物流成本为优化目标建立设备多行布局数学模型，设计了相应的遗传算法优化流程并建立了算法模型，研究了适合设备多行布局的编码方式、遗传操作和适应度函数，通过Matlab编程对布局策略进行遗传运算，最后，通过具体的实例分析，验证了算法的收敛性、实用性和有效性。

物流成本；多行布局；遗传算法；Matlab

0 引言

解决设备多行布局问题多用连续优化方法，即设备在行内是连续的，在行间是离散的。连续优化方法研究较多的布局形式有：一是提前确定分行数，通常设分行数为两行；二是设备自动换行。由于在布局前无法确定一个车间设备可分行的数量，所以事先确定分行数是不合李的，甚至可能导致最后的布局结果是非法布局方案，而自动换行技术成功的避免了非法解的产生。因此，本文采用自动换行布局策略。

1 问题假设与建模

1.1 问题假设

为了简化计算，对多行设备做出如下简化与假设：

1）所有设备和车间形状均为矩形，忽略它们的细节形状；

2）设备按同一方位布置，同一行设备的中心点位于一条水平线上；

3）零件加工顺序同设备编号顺序一致；

4）零件的工序加工时间都是确定的；

5）所有设备沿X轴方向依次排列。

1.2 问题的建模

目前，关于车间布局优化的目标越来越多，在最早最小化物流费用的基础上，又提出了提高物料流和工艺流效率、空间利用率最大化等目标。不难看出，最小物流费用仍然是车间布局问题评价的主要标准。因此，在对车间多行布局进行研究时，车间物流费用最小化是研究者首要考虑的最重要原则。

假定某车间共有n台设备，m种产品，车间物流成本的数学建模为：

其中：Qkij为产品从设备i到j的当量物流量；dij为设备i到j必须保持的最小间距；∆lij为设备i到j的 X轴方向上间距；∆hij为设备i到j的 Y轴方向上间距； ∆ij为设备i到j的 X轴方向上净间距；xi,yi为设备i的坐标；(xa,ya)，(xb,yb) 为包络所有设备的最小矩形的左下角和右上角的坐标；L,H为车间的长和高；li,hi为设备i的长和高；l0为第一行设备中心线距离X轴的距离；h为两个相邻行的中心距。

图1 车间布局参量、决策变量和参考线

2 基于遗传算法的目标函数求解

由于车间多行布局问题属于非线性规划问题，而且约束条件较多，用一般的数学方法难以找到较多设备布局问题的最优解，在1976年，Sahni和Gonzalez[1]己经证明了设备布局问题属于NP完全问题。遗传算法（Genetic Algorithm,GA）在设备布局模型寻优过程中受到越来越多的关注，对该类问题的求解则具有较为显著的优势。遗传算法的优越性主要表现在搜索过程中不易陷入局部最优，即使在所定义的适应度函数不连续的情况下，也能以极大的概率找到最优解[2]。因此，本文采用遗传算法优化设备多行布局。

图2 遗传算法优化流程

2.1 染色体表达

自动换行布局策略的染色体只包含设备符号和净间距两个列表，如v=[{m1,m2,…,mn}，{∆1,∆2,…,∆n}]。mi为设备i的符号；∆i为设备i与相邻设备i-1的净间距。

2.2 罚函数和适应度

本文建立的罚函数包括两个方面：一是设备重叠；二是超出车间尺寸。由于净间距的存在，设备在X方向上不会重叠，又有最大间距分行，在Y方向上也不会产生重叠；因为设备采用自动分行技术，所以在X方向上设备不会超出车间，只需要约束设备在Y方向上不要超出车间尺寸即可：

根据代价极小化与利益极大化的对偶原则，适应度函数可以采取目标函数值的倒数的策略来实现：

其中，β为惩罚值，一般取较大的正数；Fk为第k个染色体代表的布局成本；λ为在Y方向上超过车间尺寸的罚函数。

2.3 选择操作

轮盘赌选择，是一种经典的GA选择方法[3]。依次计算种群中所有个体的适应度的总和，再计算每个个体的适应度值所占比例，以此作为选择的概率。适应度值越高的个体被选中的概率越大。因此，本文选用轮盘赌的选择方法。

2.4 交叉操作

通过比较多种交叉方法特点，并结合车间多行布局编码形式特点，本文对设备编码部分采用单点交叉方式，针对净间距编码部分采用算术交叉方式。

单点交叉是指在相互配对的两个个体中随机设置一个交叉点，交换个体在所设定的交叉点的部分基因。

交叉算术是指由两个个体的线性组合而产生的两个新的个体。假设车间两个父代个体的净间距序列：

则子代个体的净间距为：

α=1-0.9r

式中，r为进化代数。

2.5 变异操作

设备排序编码部分采用互换式变异操作方式；设备净间距部分，结合各种变异操作的特点和净间距序列染色体的特点，本文采用邻域搜索技术对机器位置进行细微的调整。变异操作过程如下：

假如选定的设备净间距为：∆1,∆2,…,∆i,…,∆n}，选择非零基因∆i进行变异，令φ是一个给定的整数（局部寻优次数），则可以得到2φ个净间距。

评估所有邻域染色体，保留适应度值最高的染色体。

3 应用研究

B车间主要负责面膜的灌装，采用半自动流水作业方式。车间长12m，宽12m。车间各工位的主要参数如表1所示。

因为，只有工位1和2、5和6、9和10在X轴和Y轴方向上均需要保持1m的最小间距，其余各工位物流间距为零。因此，只需计算工位1和2、5和6、9和10间的当量物流量和物流频率即可（如表2所示）。

表1 不同工位尺寸

表2 当量物流量/物流频率

由于当量物流量已充分考虑了不同工位间产品搬运的难易问题，所以设所有工位间搬运费用均为0.02 元/m。

GA初始参数的设置：pop_size=50，Maxgen=500，Pm=0.6，Pc=0.1，β=500。

在Matlab 7.8.0版本上30次运行后，其中24次得到问题的最有解，6次得到问题的次优解。问题最优解在148代开始收敛（如图3所示），设净间距保留两位有效数字，多行布局的最优解是：{{1 2 3 4 5 8 7 6 9 10}，{0.38 0.40 0.00 0.45 0.25 0.03 0.17 0.25 0.06 0.03}}，设备共分成3行，第一行：{1 2 3 4 5}，第二行：{8 7 6},第三行：{9 10}。

图3 基于目标函数的染色体收敛曲线

4 结论

本文研究了面向OEM企业车间多行布局的遗传算法，在染色体表达上采用自动换行技术，克服了提前设定分行数易产生非法解的缺点。在算法中，根据车间多行布局的特点，精心设计了染色体编码方式、遗传操作及其适应度函数。最后，通过实例分析，验证了算法的收敛性、实用性和有效性。本文模型及算法可以为车间进行多行布局提供指导。

[1] Sahni S,Gonzalez T.P-complete approximation Problem[J].Journal of Association for Computer Maehiniary.1976,23,(3):555-565.

[2] 陈希,王宁生.基于遗传算法的车间设备虚拟布局优化技术研究[J].东南大学学报(自然科学版).2004.9:34(5),627-631.

[3] 马少平,朱小燕.人工智能.北京:清华大学出版社,2004.

TH166

A

1009-0134(2010)11(下)-0052-02

10.3969/j.issn.1009-0134.2010.11(下).20

2010-08-20

国家自然科学基金资助项目 (71071115)

周娜（1979 -），女， 博士研究生，主要从事生产系统优化方面的研究工作。