基于遗传算法的制造单元继承性生成方法

张炳根，龙伟



基于遗传算法的制造单元继承性生成方法

张炳根，龙伟

（四川大学 制造科学与工程学院，四川 成都 610065）

为实现多品种变批量生产模式下的制造单元优化重构，将车间重布局成本纳入优化目标，建立了以物流成本和重布局成本为优化目标的制造单元需求模型；为了降低重布局成本，提出一种具有继承性的制造单元生成方法，利用改进遗传算法中的染色体编码方式、初始种群生成方法、遗传算子操作等方法，最大程度上保存了原有制造单元中的资源组织结构，实现具有继承性的制造单元优化重构过程；最后通过一个实例验证了所提方法的有效性。

制造单元；重布局；遗传算法；继承性

当前全球在“德国工业4.0”、“中国制造2025”、“美国工业互联网”等新兴理念强烈冲击影响下，设备自动化、生产智能化、需求个性化已成为新兴工业发展的代表性特征[1]。为了适应多样化及个性化的市场需求，以往的大规模生产模式纷纷向多品种变批量定制生产模式转变，单元制造系统作为最先进的生产制造方式应运而生，基于单元制生产方式的设备布局所具有的敏捷性、柔性等优点为实现精益生产模式奠定了良好的基础[2]。

单元制造是以成组技术为基础的一种生产模式，它根据成组技术将具有工艺相似性的零件进行分组形成零件族，通过相应的制造设备集合对其进行加工，从而提高了生产制造的柔性[3]。在多品种变批量的生产模式下，待加工产品种类繁多且每个种类的批量都有可能发生改变，同时每种产品的加工路径都不唯一[4]，当生产任务发生改变时，就需要对制造单元进行重新构建，以满足新的生产任务要求。

针对制造单元构建问题，国内外学者研究出了各种制造单元生成方法，主要有聚类分析法[5-6]、智能优化算法[7-9]、数学规划算法[9]等。例如，文献[11]以多工艺路线为基础，通过将遗传算法用于单元构建技术，提出以单元内和单元间的物流量总和为最小优化目标的制造单元生成方法。文献[12]通过分析车间单元布局的可用性，在考虑多阶段单元构建问题情况下将原有制造单元的可用性纳入优化目标，利用改进粒子群算法生成制造单元构建方案。

但是，现有的单元构建方法并未考虑制造单元之间所具有的联系性[13]，新的单元构建方法中资源组织的配置形式相对原有制造单元不存在继承性，而是将现有资源组织形式全部打乱重构，在多品种变批量生产模式下必将极大的增加设备移动等因素所产生的重布局费用。

为此本文在对现有制造单元中组织进行结构分析的基础上，通过增减现有单元中的设备、互换不同单元间的设备等形式降低原有制造单元内设备的变动，使新生成的制造单元能够在最大程度上保存原有方案中的单元结构，形成具有继承性的制造单元生产方法；最后建立具有继承性评价标准的单元构建目标函数，通过改进遗传算法求解，输出单元构建方案。

1 制造单元问题建模

目前的单元构建方法一般是以单元内和单元间的总物流成本作为方案的评价标准[14]。然而在多品种变批量生产模式下，仅考虑总物流成本难以符合实际生产需求，尤其在制造设备众多的重布局过程中，大型设备移动、多阶段单元构建、批量变动等实际因素，重布局费用所占比重将随之增大，为此本文对制造单元问题建模时不仅考虑总物流费用1，还将重布局费用2纳入优化目标，由此本文提出的单元构建目标函数为：

1.1 物流成本

多品种变批量生产模式下，考虑多工艺路线的单元间及单元内的总物流成本1为：

1.2 重布局成本

车间的重布局成本主要与制造设备的位置变动有关，新的制造单元与原有制造单元间的资源组织形式越相似，车间制造设备变动幅度将越小，说明单元构建方法所生成的方案具有的继承性越高，重布局成本将越低。为了表示制造设备的变动幅度和单元构建方案的继承性，定义设备变动系数和继承性系数：

重布局成本主要与制造单元组织结构的变动幅度，大小由继承性系数决定，由此本文构建重布局成本2为：

式中：为重布局成本与物流成本的比重，其由任务变更频率、资源调整幅度等因素决定，本文以物流成本为主要成本，根据单元构建需求取＝0.01；＝0时表示新的单元构建方案与原有的单元构建之间不具有继承性，此时重布局成本最大，＝1时表示新的单元构建方案具有最大的继承性，此时不产生重布局成本，由此将单元构建方案的继承性纳入方案的评价指标。

根据总成本目标函数进行约束分析，采用文献[10]中常规制造约束，一台设备只能在一个制造单元内；一个零件只能属于一个制造单元，当零件的某道工序需在其他制造单元内的设备上加工时则属于跨单元加工；一个零件只能采用一条工艺路线。参照文献[11]中的布局约束分析，为简化计算，定义单元内设备的物流距离和单元内设备的物流距离分别为：

2 基于改进遗传算法的继承性制造单元构建算法设计

在进行制造单元的算法设计时，为了减少原有单元中设备的变动，新的单元生成方法需在最大程度上利用原有方案中的资源组织形式，为此需提取原始制造单元的构建信息，并将其引入新制造单元的构建过程，以保证资源组织结构的继承性。改进的遗传算法通过染色体编码、初始种群选取方式输入原有单元构建方案的信息，同时利用适应度函数、交叉算子等遗传操作最大程度上保证信息的完整性即原有资源组织结构的完整性，从而实现新的单元构建方案对原有方案的继承。

2.1 染色体编码方式

在遗传算法中，通常用一个染色体基因信息代表遗传算法要求解的问题，依据本文所构建的单元构建目标函数，采用文献[10]中基于整数序列的染色体编码方式，如图1所示。

其中染色体的信息包含制造设备M所属单元C、零件P所属单元C及零件P选择的工艺路线R。

图1 染色体编码方式

2.2 初始种群生成方法

在传统的遗传算法中，初始种群通常是由算法随机生成的，由这样的初始种群进化后产生的最优个体，其所对应的制造单元构建方案可能是推倒重排式的构建方法，对原有单元的组织结构具有极大的破坏性，同时搜索效率低下；为了实现新制造单元构建方案对原始方案的继承，本文构建一组具有继承性的初始种群，其构建过程为：

（1）根据原有的单元构建方案，提取制造单元内设备零件工艺路线的对应关系，通过染色体编码的方式将其转化为初始解，如图2所示；

（2）将新的生产任务随机分配到制造单元C中，由此产生的编码插入初始解对应的子段，例如将新增加工任务零件P5随机分配到制造单元C2中，则新个体染色体编码方式如图3所示，同时删除其中违背约束关系的个体，生成具有继承性的初始种群。

图2 初始解染色体编码方式

2.3 适应度函数及遗传算子操作

遗传算法的适应度函数一般由所构建的目标函数转变而来，当构建的函数以最小值为优化目标时，可将适应度函数设置为所构建函数的倒数。本文根据模型构建过程中的最低总成本函数，将适应度函数设置为()＝1/，个体适应值越大则成本越低，说明个体适应度越好。目标函数中包含继承性系数表明了适应度函数对个体的继承性优劣有一定的评判能力。采用轮盘赌选择法确定被选中的个体；然后在染色体中设备、零件、工艺路线三个子段内分别通过二进制编码中的单点交叉方式组合出新的个体；针对新的个体通过改变染色体上的数值进行变异，染色体的基因可突变为其取值范围内的任何数值，以此防止遗传算法陷入局部收敛；最后根据所定的终止进化代数来结束算法。

2.4 算法步骤

步骤1：设定改进遗传算法中的各项参数，包括初始种群数量、交叉概率P、变异概率P、进化代数＝1及算法的终止进化代数等；

步骤2：根据模型分析过程中构建的最低总成本函数设置适应度函数，提取原有单元构建方案信息，根据上文所述初始种群生成方法产生具有继承性的初始种群；

步骤3：对种群中的各个体进行适应度计算；

步骤4：根据个体的适应度大小，利用轮盘赌选择法从父代种群中选取两个个体进行交叉、变异操作，得到子代个体；

步骤5：判断算法的进化代数。若＝，则进入步骤6；否则回到步骤3；

步骤6：算法结束，将适应度值最大的染色体作为新的单元构建方案。

3 实例分析

本文以某发动机生产车间为例，阐述生产任务变动后具有继承性的制造单元构建方法。某阶段该车间的生产任务发生变动，具体的零件批量变化、工艺路线信息如表1所示，新增大批量生产任务P9和P10如表2所示。

表1 零件加工批量及工艺信息

表2 新增生产任务

运用Matlab软件编写遗传算法运行程序。设定改进遗传算法中的各项参数：＝100，P＝0.65，P＝0.03，＝400，依据表3中原制造单元构建方案对染色体进行编码并生成具有继承性的初始种群，运行程序得到改进遗传算法收敛过程如图4所示，算法在140代附近进入收敛状态，对应的函数值为3262.11，染色体值为{1,1,3,2,3,1,2,3,2,2,1,3,3,2,1,1,2,3,1,3,2,2,1,1,3, 2,1,2,1,1,1,1}。

为了验证算法的优越性,利用基本遗传算法对本文所构建的目标函数进行求解，其收敛过程如图5所示，算法在250代附近进入收敛状态，对应的函数值为3478.67；通过对比图4和图5可知，本文的改进遗传算法通过继承性调整，其收敛速度是基本遗传算法的近一倍，同时优化结果更为理想。

表3 原制造单元构建方案

根据上文的最优染色体，对应的单元构建方案如表4所示。生产任务变化后，单元构建过程如下：将原有制造单元C1中的设备M9分配到新制造单元C2，原有制造单元C1中的M5和C3中的M6进行互换，形成新的制造单元C1和C3，并将新增生产任务P9和P10同时分配到新制造单元C2所对应的零件集合，方案在保证成本最小的同时，最大程度上继承了原有制造单元的组织结构。

图4 改进遗传算法收敛过程

图5 基本遗传算法收敛过程

表4 新制造单元构建方案

4 结束语

针对传统单元构建方法存在的不足，本文提出的具有继承性的制造单元生成方法，通过将继承性系数引入目标优化函数，实现算法对制造单元方案继承性优劣的判别，并且由具有继承性的单元构建方法得到的单元构建方案，能减小制造单元中设备的频繁变动，降低重布局时间，可在一定程度上提高车间的生产效率。

[1]苏诚，许朋刚，代志良. 智能仓储系统设计与开发应用[J]. 机械，2017，44（10）：65-71.

[2]Nima Safaei，Reza Tavakkoli-Moghaddam. Integrated multi-period cell formation and subcontracting production planning in dynamic cellular manufacturing systems [J]. International Journal of Production Economics，2009（20）：301-314.

[3]王晓晴，唐加福. 基于分散搜索的零部件跨单元生产的单元管理方法[J]. 机械工程学报，2009，45（10）：125-131.

[4]牛力. 资源布局可变条件下的开放车间柔性制造单元构建技术研究[J]. 科学技术与工程，2011，11（25）：6054-6059.

[5]King JR. Machine-component grouping in production flow analysis: an approach using a rank order clustering algorithm[J]. International Journal of Production Research，1980，18（2）：213-32.

[6]李杰，王云峰，朱昭贤，徐勇. 基于模糊技术的制造单元构建方法研究[J]. 计算机集成制造系统，2004，10（12）：1561-6.

[7]郑玉彬，韩峰，何宇，曲植. 基于遗传算法的可重构制造单元布局研究[J]. 机械设计与制造，2009（9）：193-4.

[8]Rezazadeh H，Mahini R，Zarei M. Solving a dynamic virtual cell formation problem by linear programming embedded particle swarm optimization algorithm[J]. Applied Soft Computing，2011，11（3）：3160-9.

[9]王国新，阎艳，宁汝新，王爱民. 模糊神经网络与启发式算法相结合的制造单元构建方法[J]. 计算机集成制造系统，2008，14（11）：2175-83.

[10]TSAICC，LEECY. Optimization of manufacturing cell formation with a multi-functional mathematical programming model [J]. International Journal of Advanced Manufacturing Technology，2006，30（3）：309-318.

[11]刘雪梅，朱丽君，李爱平，黄君政. 基于遗传算法的生产车间制造单元构建技术研究[J]. 制造技术与机床，2013（2）：57-61.

[12]陶俐言，聂清，王志锋，梁满棠. 面向变批量生产的制造单元构建方法[J]. 计算机集成制造系统，2014（10）：2411-2418.

[13]李京生. 面向多品种变批量生产的重构调度方法[D]. 北京：北京理工大学，2015.

[14]ADIL G K. The trade-off between intracell and intercell moves in group technology cell formation[J]. Journal of Manufacturing Systems，2000，19（5）：305-317.

Inherited Methodology of Manufacturing Cell Formation Based on Genetic Algorithm

ZHANG Binggen，LONG Wei

(School of Manufacturing Science and Engineering, Sichuan University, Chengdu 610065, China)

In order to achieve manufacturing cell optimized reconfiguration in the production mode of multi variety and variable batch, this article introduced the cost of shop layout to the optimization goal, and established the demand model of manufacturing cell with the cost of logistics and the cost of shop layout. In order to reduce the cost of reconfigure, a method of generating unit with inherited was proposed. By using the improved genetic algorithm, such as chromosome coding, initial population generation and genetic operator operation, the resource organization structure of the original manufacturing cell was maximum saved, and realized the succession of the new manufacturing cell to the original cell. Finally, the effectiveness of the proposed method is verified by a numerical example.

manufacturing cell；reconfigure；genetic algorithm；inheritance

TH165

A

10.3969/j.issn.1006-0316.2018.01.004

1006－0316 (2018) 01－0018－06

2017－05－15

张炳根（1989－），男，江西婺源人，硕士研究生，主要研究方向为现代控制工程与计算机应用；龙伟（1956－），男，重庆人，工学博士，教授，主要研究方向为机械制造及自动化。