基于粗粒度并行遗传算法的车间制造单元构建问题的研究

周正一

摘要：对于具有多品种、多批次、小批量等特点的中小型离散制造业来说，为了追求高柔性、高质量、短交货期和低成本的目的，建立单元制造系统势在必行。本文针对单元制造系统中最为关键的单元构建问题进行研究，分析了利用传统遗传算法在解决单元构件问题时可能存在的缺陷，提出了一种新算法的单元构建算法，并结合实例证明了方法的可行性和有效性。

关键词：单元制造 单元构建  遗传算法 成组效率

1.引言

在利用遗传算法解决单元构建问题（Cell formation problem， CFP）时，一般将分组数直接作为一个优化的变量通过遗传算子进行优化，但这里面存在以下三个问题：（1）对于分组数多得染色体，其合法性呈下降趋势，这使得分组数多的染色体成为劣势群体，并面临较高的淘汰风险。（2）对于同一问题，当分组数不同时，目标函数的收敛性不同，对于不同的问题，最优分组数也不同。（3）由于上述两个问题的存在，使得在一个种群中，将分组数直接作为变量进行优化时，由于单元数少的染色体存活的概率较大，使得算法一般会陷入局部最优解，即出现局部收敛的现象。

因此，在利于遗传算法在进行单元构建时，三个问题需要被考虑进来：（1）找到所求问题中最合适的分组数;（2）保证分组数多的染色体不会因为合法性要求高而成为劣势群体。（3）不同的分组数染色体进行遗传操作时，既要在一定程度上进行交流又要保持一定的独立性。为此，本文引用粗粒度并行遗传算法，使同一分组数的染色体在同一子种群中，各子种群在独立进化的同时，保持一定程度的交流。

2.单元构建的基本概念和问题描述

2-1（a） 初始关联矩阵           2-1（b） 对角矩阵

图2-1 单元构建实例

CFP问题的求解可描述为：对关联矩阵进行行变换和列变化，使之尽可能成为一个对角块矩阵，在该对角矩阵中每一个“块”便为一个单元，图2-1（b）为图2-1（a）的一个变换矩阵，通过变换处理后将车间划分为3个单元。

CFP问题的优化目标为：最小化零件在单元间移动所带来的花费，并最大化单元内的设备利用率，即最小化对角块中元素0与对角块外元素1的数量。目标函数为Kumar和Chandrasekharan提出了Grouping efficac