基于遗传算法的生产车间制造单元构建技术研究*

刘雪梅 朱丽君 李爱平 黄君政

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

在工厂的生产活动中，从生产时间看，从原材料进厂到产品出厂，物料真正处于加工检验的时间仅占生产周期的5%～10%，而90% ～95%的时间都处于搬运或停滞状态;而从生产费用看，物料搬运费用在生产经营活动总开销中的比例高达20% ～50%，而良好的设备布局设计可使这一费用至少降低10% ～30%［1］。基于目前多品种、小批量的市场需求，单元制生产方式作为最先进的生产制造方式应运而生，基于单元制生产方式的设备布局所具有的敏捷性、柔性等特征为实现精益生产模式奠定了良好的基础［2］。单元布局对制造系统的物料传输、生产效率和柔性也有重要影响［3］。

单元制造（Cellular Manufacturing，CM）是在成组技术基础上发展起来的一种生产模式，它根据成组技术将一系列零部件划分为零件族，通过相应的设备组对其进行生产加工，从而提高了生产制造的柔性［4］。单元构建（Cell Formation，CF）是单元制造成功实施的关键问题之一，单元构建问题（Cell Formation Problem，CFP）是一种NP完全问题。至目前为止，制造单元构建技术主要有聚类分析、图论方法、数学规划方法、启发式算法、智能技术等［5］。本文基于成组技术的原理，分析与制造单元相关的制造信息，运用改进的遗传算法划分制造单元。

1 单元构建问题及其数学模型

1．1 问题描述

单元构建是通过对所加工的零件进行工艺分析，将所加工零件和所需的加工设备进行分组，形成特定的零件族和与之对应的设备组，每一零件族和相应的设备组即构成了一个特定的制造单元［6］。如图1a所示，如果零件i由设备j加工，则矩阵元素（i，j）为1，否则为0（图中0未显示）;如图1b所示，零件1、2、6和设备1、3、6构成一个制造单元，而零件3、4、5和设备2、4、5构成另一个制造单元。

1．2 数学模型

1．2．1 考虑因素

在单元构建过程中，传统的单元构建方法一般是以单元间物流量最小为主要优化目标，并采用机器－零件关系矩阵［aij］作为基本数据表达方式［7］。而物流量在单元构建问题中包括单元间物流量和单元内物流量两部分，前者表现为机床－零件关联矩阵中例外元素的数量，后者表现为关联矩阵中对角块内“0”的个数。本文在考虑工艺路线的前提下，以单元间及单元内的物流量总和最小作为目标函数来求解制造单元的最优划分。

1．2．2 模型的数学表达式

决策变量:

式中:i为零件标识，i=1，2，…，n;j为机床标识，j=1，2，…，m;C为拟划分制造单元总数;M为机床总数;P为零件总数;mi为按照工艺路线完成零件i的加工所需的单元内的物流量;Ri为零件i的工艺路线总数;E=［eij］，为工艺路线选择后的零件－机床关系矩阵，eij=1表示在选择的工艺路线中，零件i需要在机床j上完成;α、β分别为单元间物流量和单元内物流量的权重系数，根据其对单元构建影响程度的不同，分别定为0.7 和 0.3［8］。

当tik=1时，零件i需要在单元k中加约束:

以上3个约束条件中，约束条件（2）表示每台机床只能分配至唯一的制造单元;约束条件（3）表示每个零件只能属于唯一的制造单元;约束条件（4）表示每个零件只能采用一条工艺路线。

2 算法求解

2．1 遗传算法

本文采用遗传算法求解制造单元构建问题。在算法中，将依据制造单元构建问题自身特点修改染色体编码方式及遗传算子，改进基本遗传算法。

2．2 遗传算法的运算流程

运用遗传算法求解制造单元构建问题主要有染色体编码、初始种群生成、适应度计算、选择、交叉、变异等操作步骤，如图2所示。

3 应用实例

3．1 实例描述

以某柴油发动机缸体柔性加工生产线为例，运用改进的遗传算法构建制造单元。给定12台设备和8类零件，且每个零件有2种或3种工艺规划方案，每台设备至少加工一个零件，每个零件的工艺路线中至少使用一台设备。制造单元的构建即是将12台设备划分为4个制造单元，将8类零件划分为4个零件族。

表1中给出了12台机床对8类零件进行加工，每类零件有多条工艺路径可供选择。不同工艺路径下零件－机床加工信息如表1所示。

表1 多工艺路线下的零件－机床关联信息

3．2 案例求解

（1）染色体编码

采用Joines［9］的遗传子表示法，用基于整数序列的表示法来编码染色体。根据所求解的特性，涉及染色体结构为由机床分配信息、零件分配信息及工艺路径选择信息组成。因此，每一条染色体是由M+P+RP组成，如图3所示。图中M为机床编号，P为零件编号，R为工艺路径选择编号。

（2）初始种群的生成

采用随机产生初始群体的方法构造初始群体。根据预先设定的种群规模、单元数、已知零件对应的加工工艺路线数，按照图3所示染色体表达形式产生每个个体。根据经验，设定初始种群数为50个，单元数为4。

（3）适应度计算

适应度函数表明个体或解的优劣性。由于目标函数是求最小值，所以适应度函数设置为目标函数的倒数，即

其中Zi为染色体i的组合优化目标函数。由函数关系可知，适应度值fit（Xi）与目标函数Zi成反比，目标函数值越小，个体的适应度越高，该个体就越容易被接受。

（4）选择

本文采用的选择算子是1975年由Holland提出的一种比例选择算子，即模拟轮盘赌的选择方法，它根据每个个体被遗传到下一代群体中的概率，使用模拟轮盘赌操作（即0到1之间的随机数）来确定哪些个体被选中。设种群大小为p，个体i的适应度为fit（Xi），则个体被选中的概率pi为

（5）交叉

根据单元构建问题的特殊性，本文将对二进制编码中的点式杂交进行修改，在机床、零件和工艺路线3个区域各随机产生3个点进行交叉运算［10］。父代1和父代2杂交后生成子代1和子代2，如图4所示。

（6）变异

按照变异概率随机从种群中选择每一条染色体进行变异运算。对于第一部分和第二部分，基因值从1至最大单元数进行选择;对于第三部分，则随机选择一条对应零件可行工艺路线进行替换。如图5所示。

（7）终止选择

本算法中的终止准则采用了预先规定一个最大的演化代数来终止算法。

3．3 分析评价

根据初始化信息和约束条件，运用MATLAB软件编写相应程序。针对问题的特殊性，对基本遗传算法进行了相关操作算子的修改，使其适用于单元构建问题。初始化时，随机产生规模为50的种群，最大进化代数为500，交叉率和变异率分别为0.7和0.01。目标函数收敛情况如图6所示。从图中可以看出，遗传算法在大约第280代收敛于最优解或近似最优解，其目标函数最优值为2.196 8，最优解下的单元构建方案如表2所示。

表2 最优解下的单元构建方案

成组效率［11］是一个衡量制造单元构建效果的综合评价指标，已被广泛采用。成组效率公式及其含义如下:

式中:GE为成组效率，GE≤1，GE越大，成组效率越高;ed为所有制造单元内的元素1之和;EE为例外元素总数;Mk为第k个制造单元内的设备数量;Nk为第k个制造单元内的零件数量;c为制造单元数量。

由公式（7）可知，本实例制造单元划分结果的成组效率GE=（6+6+6+6）/（3×2×4+0）=1，成组效率最高。

4 结语

单元制造技术是先进生产运作方式中的热点研究问题之一，而单元构建则是实施单元制造技术的前提。本文讨论了多工艺路线的单元构建问题，针对单元构建问题的特殊性，以单元间及单元内物流量之和最小为目标构建了数学模型，修改了基本遗传算法的编码方式及遗传操作算子，并利用该算法对一实例进行了单元划分。

［1］Francis R L，McGinnis L F，White J A．Facility Layout and Location［M］．London:Prentice Hall，1998．

［2］Nima Safaei，Reza Tavakkoli－ Moghaddam．Integrated multi－ periodcell formation and subcontracting production planning in dynamic cellular manufacturing systems［J］．International Journal of Production Economics，2009（20）:301－314．

［3］锁小红．基于制造系统功能的设施布局设计研究［D］．济南:山东大学，2008．

［4］王晓晴，唐加福．基于分散搜索的零部件跨单元生产的单元管理方法［J］．机械工程学报，2009，45（10）:125－131．

［5］王爱民，丁国智，宁汝新．制造单元快速构建技术研究［J］．北京理工大学学报，2006，26（10）:850－854．

［6］Jaydeep Balakrishnan，Chun Hung Cheng．Multi－ period planning and uncertainty issues in cellular manufacturing:A review and future directions［J］．European Journal of Operational Research，2007，177（1）:281－309．

［7］Kim C O，Baek J G，Baek J K．A two－phase heuristic algorithm for cell formation problems considering alternative part routes and machine sequences［J］．International Journal of Production Research，2004，42（18）:3911－3927．

［8］Asokan P，Prabhakaran G，Satheesh G Kumar．Machine－cell grouping in cellular manufacturing systems using non－traditional optimization techniques－ a comparative study［J］．Int．J．Adv．Manuf．Technol．，2001（18）:140－147．

［9］Joines J A，Cullbreth C T，King R E．Manufacturing cell design:An integer programming model employing genetic algorithms［D］．Raleigh:North Carolina State University，1996．

［10］Chan F T S，Lau K W，Chan L Y ，et al．Cell formation problem with consideration of both intracellular and intercellular movements［J］．International Journal of Production Research，2008，46（10）:2589－2620．

［11］Kumar C S，Chandrasekham K P．Grouping efficiency:a quantitative criterion for goodness of block diagonal forms of binary matrices in group technology［J］．International Journal of Production Research，1990，28（2）:233－243．