改进蚁群算法对混合ASP和ALB问题研究

杨 卓，金雪峰

（武汉船用电力推进装置研究所，武汉 430064）

改进蚁群算法对混合ASP和ALB问题研究

杨 卓，金雪峰

（武汉船用电力推进装置研究所，武汉 430064）

本文利用蚁群算法对混合装配序列规划和装配生产线平衡问题进行优化求解。通过装配联络图来获得表示装配线上作业任务先后顺序约束的装配作业任务优先关系图。针对混合问题的新的优化目标和约束条件，建立了一个混合优化问题数学模型，并利用自适应改进后的蚁群算法对数学问题进行求解。

蚁群算法 ASP ALB

0 引言

装配序列规划（ASP）是对装配过程中组装零部件先后顺序进行研究，装配生产线平衡（ALB）是对装配过程中各个站的工序的先后顺序进行优化，它们是装配最优化问题中的两个重要的 NP组合优化问题。过去的研究者们対这两个问题都有大量的研究，然后极少有研究者们综合地考虑这两个方面，事实上不同的装配序列会对生产线上的作业工序有极大的影响，单一研究ASP和ALB可能无法得到最优的装配方案。

ASP问题的所有优化目标，都是将整个装配体的装配视为一个连贯、无间断的过程，但是一旦当装配体放在装配生产线上去，就会被分配到各个不同的工作站上进行组装，因此原先的装配系列的优化结果很有可能因为外部条件改变不适用了，从而导致这样一个可能：装配序列优化所得到一个较好的装配序列方案，放在装配线上却出现了一个糟糕的作业分配结果，使各个工作站之间的作业时间极度不均衡，反而降低了生产效率。本文使用改进蚁群算法对混合的ASP和ALB问题进行研究，规避单一研究的弊端，寻找装配体最优的装配方法。

1 混合问题优化目标

ASP问题的有三个的优化目标，即装配工具变换次数，装配方向变换次数和装配稳定性的问题，如果能尽可能地减少总工具变换次数或总方向变化次数，则可以有效减少总的装配时间。实际在生产线上生产时，零件是在工作站和工作站之间传递的，由于各个装配作业耗费的时间有长有短，如果某个工作站上装配时间过长，则它后面的工作站会陷入停滞状态。混合 ASP和 ALB问题需要调整装配序列并将它们合理分配到不同的工作站上，尽可能保证各个工作站的时间一致，从而减少停滞和等待时间。综合考虑装配序列的排序和工作站的分配，能得到最经济省时的装配方案。

2 构建装配联络图

研究装配序列时首先要保证装配方案是可行的，装配的可行性可以使用干涉矩阵进行判断，矩阵中的每个元素表示的是对应的零部件在装配时，其在±x，±y，±z方向上是否与其他零件有干涉关系。干涉矩阵F可以表示如下：

为了将装配零件序列的序列排序转化为装配作业的序列排序问题，需要使用邻接矩阵来表示零件间的连接关系，并用零件间的连接关系表示可能存在的所有装配作业。可以表示成如下的 n阶方程：

其中

现在假设一个装配体有1-9共九个零件，使用T1-T4共四种工具进行装配。使用邻接矩阵表示各个零件间的连接关系，然后将有连接关系的零件用有向线段连接起来，例如1→2表示的就是将2号零件装到1号零件上。经过干涉矩阵检验后，将不可能实现的连接关系去掉，将所用可能的装配序列保留下来制作成一个有向图，即是装配序列联络图。装配序列联络图中的每个点代表一个零件，每条有向边代表的是一个装配作业，不同的装配作业使用不同的工具。一个典型的装配体的装配序列联络图如图1所示:

装配序列联络图中包含了零件的装配顺序优先关系，同时也包含了零件与零件间装配过程的顺序关系。通过装配序列联络图，我们就可以将零件装配序列问题转化为作业序列问题。装配联络图完成之后，接下来建立数学模型并使用蚁群算法来搜索最优的装配作业分配到各个工作站上的方案。

3 混合问题建模

假设作业任务总数为 n，完成第i个作业任务的时间为it，工作站总数为m，第 j个工作站上工具变换次数为工作站的节拍为 c，那么我们的优化目标就是最小化工作站的数量，所以优化问题的目标是:

1）使装配线平衡率尽可能的大，装配线平衡率是反应装配线上各个工作站之间时间的均衡程度，是考核装配效率和装配成本的重要指标，各个工作站工时相差的越大，则平衡率越低。即

其中，LE为装配线的平衡率，错误！未找到引用源。是第k个工作站上的所有装配作业任务本身的装配时间，m是工作站的数量。

2）使装配线的平滑性指数尽可能的低，装配线平滑性指数反应的是各个工作站上作业时间分布的离散情况，这个值越大，则各个工作站之间的作业时间相差越大，那么停滞等待和超载负荷的时间也就越长。即

其中，SI为装配线的平衡性指数。

在完成优化目标的基础上，还要满足的一定约束条件则是：

1）所有作业任务都应该被分配到工作站中，不能有遗漏，即

其中，错误！未找到引用源。为分配的第k个工作站的作业任务的集合，E为装配线上任务的集合，错误！未找到引用源。，n为作业任务的数量。

2）每个作业任务只能分配到一个工作站上，不同的工作站上不会有相同的装配作业任务，即

3）装配作业任务的分配需要满足之前的装配作业优先关系图，若一个装配作业任务的紧前任务被安在某个工作站中，那么该作业任务肯定只能分配到这个工作站或其后的工作站中，即

其中，错误！未找到引用源。，W为装配作业任务优先关系矩阵。

4）每个工作站上的装配作业总时间不能超过工作站的生产节拍时间，即

其中，c为装配线的节拍，错误！未找到引用源。

为第k个工作站上的总装配时间。

4 使用蚁群算法寻找最优解

蚁群算法中，蚂蚁将装配作业任务分配到每一个工作站的过程，其实是可以想象为一群蚂蚁沿着装配任务优先图爬行的过程，每只蚂蚁图中每个节点上，选择下一条路径的概率，是依据当前可选路径上在信息素的残留余量和启发式信息，并且受到装配任务先后顺序关系和生产任务节拍时间的约束与限制，当蚂蚁在沿着装配作业任务优先图上完成一次爬行，并经过所有的节点，则是代表所有任务都被分配到了工作站中，从而求得了一个可行解。本文所使用的蚁群算法的求解流程如图4-1所示。这种解法可以有效的保证可行解的获得，其中，每只蚂蚁都是按照以下规则进行搜索：

1）开启一个新的工作站，定制节拍时间c； 2）在未分配的作业任务集合中，依据装配作业任务优先关系图，构建初始可分配任务集；3）若可分配作业任务集为非空集合，则从可分配任务集中，依据搜索算法的规则，挑选出一项新的作业任务分配至目前正在进行装配的工作站，并计算当前工作站上的装配作业任务总时间

若错误！未找到引用源。，且未分配任务不为空，则更新可分配任务集，同时进行局部信息素更新，重复步骤 2）和 3）。若错误！未找到引用源。，则转至步骤5）。若未分配任务为空集，则转至步骤 6）；5）中止任务到当前工作站上的分配，开启一个新的工作站作为当前工作站，重复步骤2）3）4）；6）所有任务已经分配完，终止算法。输出可行解的结果，并依据优化目标函数进行评价和信息素更新。

5实验验证

对Tseng和Chen的论文［1］中的装配实例进行求解，使用MATLAB编写算法，求得解装配线平衡率LE值越大，装配线平衡性指数SI越小，则求得的解越佳。

从对比图上可以看出节拍时间为28分钟，目标函数值最大，结果较好。现在取节拍时间为28分钟，求取最优装配方案，收敛曲线如图4所示。

在Tseng和Chen的论文［1］中，他们使用混合遗传算法求得的最优方案与本文结果略有不同的，原论文中的装配最优方案的装配线平衡率LE=89.6%，总装配时间为 75.4分钟。虽然原论文中的装配线平衡性的目标函数与本文不同，不妨用本文的装配线平衡性的计算方式来计算这一方案中各个工作站间作业时间的平滑性，得SI=4.06。将两个装配方案的参数进行比较，如表1所示。

6 结论

使用改进后的蚁群算法对混合问题进行求解，证明了使用本文中提出的数学模型处理装配体在生产线上的装配问题是可行的，同时用实例验证，所得到的计算收敛速度较快，计算结果与原文中的结果相比较更好，验证了本文中提出的混合问题的数学模型和处理方法的有效性与实用性。

参考论文:

［1]H. E. Tseng. Hybrid evolutionary multi-objective algorithms for integrating assembly sequence planning and assembly line balancing［J］. International Journal of Production Research， November 1， 2008， 46（21）: 5951-5977.

［2]H. E. Tseng， C. E. Tang. A sequential consideration for assembly sequence planning and assembly line balancing using the connector concept［J］. International Journal of Production Research， January 1， 2006， 44（1）: 97-116.

［3]赵姗姗，李宗斌. 一种新的装配序列规划方法研究［N］. 西安交通大学学报， 2007， 41（5）: 580-584.

［4]于建明，蔡建国. 装配建模及装配顺序分层规划方法研究［J］. 机械科学与技术， 2000， 19（4）: 671-673.

［5]ZhouPing Yin. A connector based hierarchical approach to assembly sequence planning for mechanical assemblies［J］. Computer-Aided Design，2003， 35（1）: 37-56.

Research on Hybrid Assembly Sequence Planning and Assembly Line Balancing Question with Ant Colony Algorithm

Yang Zhuo， Jin Xuefeng
（Wuhan Institute of Marine Electric Propulsion， Wuhan 430064， China）

In this paper， the ant colony algorithm is used to solve the hybrid assembly sequence planning and assembly line balancing question through the assembly liaison graph to obtain the assembly task priority graph. In view of new optimization objectives and constraint conditions of the hybrid question， the mathematical model of a hybrid optimization question is established and the ant colony algorithm is improved to solve mathematical question.

colony algorithm； assembly sequence planning； assembly line balancing

O29

A

1003-4862（2016）07-0073-04

2016-03-15

杨卓（1988-），男，硕士。研究方向：仿真模型。