基于改进遗传算法的混流手机壳产线动态平衡研究

颜家新YAN Jia-xin；黄丽HUANG Li

（①攀枝花学院智能制造学院，攀枝花 617000；②攀枝花学院经济与管理学院，攀枝花 617000）

0 引言

个性化的购买趋势使传统高度自动化的生产模式难以适应市场需求，促使制造企业选择多品种、小批量的柔性生产方式。然而，柔性化的生产模式会增加生产系统的组织、调度和最优控制的难度，如果不能制定合理的生产作业计划，则会导致生产效率低下，难以保证交货期[1]，将会严重影响企业效益。因此，混流制造系统调度问题的研究和探索十分必要。

混流装配线投产排序是通过满足某些约束条件来解决一些复杂组合优化问题，是柔性制造系统中排序的一种典型问题。投产排序的目的是通过根据不同产品订单的工艺路线或交货时间从而合理制定分配资源、优化性能指标为企业制定出最优的投产排序方案，从而为企业带来最低的生产成本和最高的经济效益。因此，设计出能够适应市场内外环境变化、持续保持动态平衡的装配线，已成为现代企业急不可待的需求之一。

学者杨武成[2]针对第一类混流装配线平衡问题，兼顾工作站数、工人数和工作站负荷均衡，引入了新变量和不对称约束来构建新的数学模型。提出了一种改进的鸡群算法求解，研究结果表明：在算例验证中，对比传统的模型，新模型多找出8 个算例的最优解，且寻优速度更快。

学者刘禹[3]针对现有生产平衡技术中研究较少的第二类生产线平衡问题，将工业工程方法与改进遗传算法相结合，提出一种用改进遗传算法来分析、解决生产线平衡问题的方法技术，并把这种方法应用到实际生产线平衡问题的改善上，取得了较好的效果。

学者张晓文[4]针对初始生产线平衡的串-并联生产系统，采用可靠度恢复因子描述设备维护前后的可靠度演变，建立了一种基于可靠度的以总成本最小为优化目标的串-并联生产系统机会维护模型，采用蒙特卡洛仿真的方法获得最优的预防性维护和机会维护的阈值，从而得到满意的维护计划。

在装配线的动态平衡问题中考虑串-并联生产系统的研究很少，而本文的研究又为装配线的动态平衡问题提供了考虑串-并联生产系统的新方向。本文针对混流装配线串-并联生产系统的多目标优化问题，建立了以降低生产节拍和工作站负荷为目标的优化模型，运用了双种群遗传算法的模型求解方法，实现了针对生产线生产节拍和工作站负荷的优化目标。

1 案例分析与改善

1.1 问题描述

成都J 有限公司手机壳装配线为研究对象，该公司的总装线为一条混流生产线，在该总装线上装配型号A、B、C 为三种结构相似的手机壳。公司每天两个班次，每个班次的有效工作时间为8H；手机壳的每日计划总产量为2500 件，其中，手机壳三种型号的计划产量为A:B:C=1000:1000:500。各工作站作业任务和串并联关系见表1，各工作站产品作业时间见图1。

表1 各工作站作业任务和串并联关系

其中，手机壳装配线初始平衡的有效工作时间T=2×8×3600=57600s；日需求Dq=2500 件；K=16 个工作站，每个工作站的作业时间见图，根据生产线平衡公式得出，T=25s/件；线平衡率P=58.11%；线平滑指数SI=1.52；根据以上数据装配线的初始平衡在一个基本满意状态。

1.2 数学建模

设定相关参数符号如下：

N：装配任务总数；

i：产品作业任务编号，I 总的产品装配作业任务数（i=1，2，…，I）；

Q：产品品种编号（Q=1，2，3）；

Wq：第q 种产品的需求比例；

K：工作站数；

CT0：装配线理论生产节拍；

Ak：第k 个工作站被占用时为1，未占用时为0；

Tiq：作业任务第q 种产品作业时间；

F：工作站中各工序为串联时为1，并联时则为0；

设定决策变量如下：

Xik作业任务分配到第个工作站时为1，否则为0。

模型假设：

①每个作业任务的加工紧前紧后关系已知；

②每个作业任务的加工标准工时已知；

③不同品种的相同装配任务均安排在同一个工作站；

④确定每个作业任务的装配时间，装配线上不同产品具有相同作业任务，但是装配时间可能不同；

⑤原有的旧装配线基本平衡，且各作业人员能胜任所分配的装配任务；

⑥混流装配线上装配的产品类型不同，但是装配的产品具有相同的工艺和结构。

式（1）是保证N 项装配任务都只被分配到其中的一个工作站k。

式（2）是表示作业任务必须满足装配任务顺序约束；

式（3）是表示K 个工作站的作业总时间均不能超过拟定的生产节拍CT0；

式（4）是表示在新的平衡中，i 装配任务被分配到工作站K 的决策变量是0/1 型。

设置综合评价函数：

在分析混流装配线中出现的实际问题后，建立出工作地的工作负荷均衡和工作地实际生产节拍最小化两个优化目标的数学模型。

①目标函数一：在满足理论生产节拍的基础上，且工作地数已知的情况下，要使实际生产节拍足够小。其数学模型如（5）所示。

②目标函数二：采用各工作地负荷均衡指数SI 来进行判断，即取每个工作地装配时间加权值的方差。在满足生产节拍的同时，各工作地负荷均衡指数SI 要尽量小。其数学模型如（6）所示。

综合评价函数：运用加权法对多目标优化问题中的多个目标按其重要程度赋以适当的权重系数，把复杂的多目标优化问题转变为单目标问题进行求解，这样不仅能够降低求解的难度还能保证生成解的质量。式（7）式表示最小综合评价值Z，其中a，b 为权重系数，满足a+b=1。

计算目标权重：

①优化目标重要程度的判断矩阵构建：

生产节拍最小化能够提高装配线的装配效率，它是保证产品能够按时交付的关键目标。因此，生产节拍比工作站平滑指数重要。根据这两个目标之间的重要程度可以构造出多目标的判断矩阵如表2 所示。

表2 多目标判断矩阵

②目标权重的计算：依据上述多目标的判断矩阵，可以计算得出两个优化目标的权重。运用MATLAB 的eig 函数计算判断矩阵的最大特征值和最大特征向量。

A=[1 4/3；3/4 1]；

[x，y]=eig（A）；%求得x 为特征向量矩阵，y 为特征值矩阵。

[mm]=find（y=max（max（y）））；%找到y 中对应最大的特征值所在列m。

w=x（:，m）/sum（x（:，m））%w 即为矩阵A 的权重。

计算结果：最大特征值为2，特征向量的分量值对应着每个优化目标的权重。w=[0.5714；0.4286]。

③一致性检验：判断矩阵由分析者凭个人知识及经验建立起来的，难免存在一些误差。为使判断结果与实际相吻合，需要对判断矩阵进行一致性的检验。但由于二阶矩阵完全一致故不需要一致性检验。

因此生产节拍、工作站平滑指数优化目标权重为：

a=0.5714，b=0.4286

1.3 算法设计

双种群遗传算法的特点是具有两个子种群。并且这两个子种群分别单独进化，他们只是在保留各种群最优染色体后，依着规定的规则相互之间进行交流。这种方式的优势在于：每个子种群的即可以单独进化去确保其各自种群的特性，而在子种群间互相交流则确保了可行解快速的收敛的同时，也扩大了搜索范围，增强了种群的多样性，也避免了陷入局部最优的困境。

双种群遗传算法流程如图2 所示，改进遗传算法解决混流生产线平衡问题时，设置以下参数：

图2 算法流程图

①种群数量N。参考文献[3]推荐的初始种群规模在20-160 之间。

②交叉概率C。即种群中染色体进行交叉的概率。

③变异概率M。即种群中染色体发生变异概率。文献[3]推荐的经验值为0.005-0.2。

④遗传代数G。

⑤综合评价函数Z。为式（7）中的值，目标函数值越小越符合条件。

⑥选择策略S。为了避免在遗传中对最优解的破坏，选择保优策略。选择策略为在每代遗传中保留10%的最优父代替换新一代中相应个数的最差染色体组成新种群。这样既保留了父代最优解，同时也保证了能够产生足够多的子代进行交叉、变异，最大程度的保证了新一代染色体的优秀度。

⑦交换和保留策略E。找到种群1 中经过交叉、变异之后的最优染色体，并标记位置和存储综合评价指标Z；找到种群2 中进过交叉、变异之后的最优染色体，并标记位置和存储综合评价指标Z。将种群1 的最优染色体和种群2 的最优染色体进行交换。比较两种群最优染色体的Z值。将最小Z 值的染色体视作最好的染色体并保留下来。

1.4 算例分析

企业调整生产计划，改进现有的产品装配工艺，将原来的装配作业元素除尘优化，新加入装配作业元素自动除尘、复判，且手机壳三种型号的日均产量调整为A:B:C=500:1500:1000，三种产品总需求量为3000 片。改变后该生产线总共有21 个工序，16 个工作站。表3 为三种产品经过21 道工序所对应的加工时间。表4 为两个种群具体算法参数设置。

表3 各工序加工时间

表4 各种群算法参数

1.5 优化结果

适应度进化曲线如图3 所示。从曲线的走势来看收敛性良好，在运行到第26 代即找到了近似最优解。

图3 适应度进化曲线

最优排布如图4 所示。图中字段列表示工作站的编号。gs 列中数字表示该工作站包含几个工序。Ct 列代表计算出的该工作站的生产节拍。Job 代表生成的工作站里包含的工序，其中数字代表在表3 中工序的顺序。flag 代表该工作站的串并联关系。为0 时代表为并联，为1 时代表为串联。

图4 最优染色体

2 方案评价

各工作站作业时间如图5 所示。结果表明装配线平衡率提升了8.43%，各工作站生产负荷减少了0.9305。

图5 工作站作业时间

经过混流装配线平衡后的各工作站生产节拍比平衡前更加均衡，尤其对于每一个工作站的生产负荷来看分配更均衡。这样提高生产线的整体运行效率，在一定程度上降低了生产线运作成本，提高了J 公司的运作管理水平。

3 小结

以成都有限公司为案例，均衡分配工作站装配任务，重新规划布局。提高企业混流装配线生产的柔性、提高企业生产效率、缩短转产时间、降低企业生产成本，使企业在现今市场更具有竞争力。

然而，本文是以最小工作节拍和最小工作负荷为优化目标，针对不同优化目标的组合的生产线平衡问题还有待于进一步研究。本文没有考虑串并联生产系统对人的影响，针对串并联生产系统对人因的影响还有待于进一步研究。