基于相似度的总装作业集划分方法研究

陈 刚，顾 丹

(上海航天设备制造总厂，上海 200245)

航天产品的研制是一项组织严谨、策划完备、步调紧凑的工程活动，计划流程的编排贯穿整个研制过程。对于航天器总装，在粗粒度层面上，计划流程和AIT流程保持一致;在细粒度层面上，AIT流程中的某些节点内还包含着许多顺序无关的工作内容(以下称“作业”)，需进一步细化其计划流程。

一个现实的问题是：在指定的计划时间内，针对指定的作业集合，在哪个子时间段完成哪些作业(以下称“作业集划分”)才能够实现统筹最优?这是一个类似于背包问题的NP难问题［1］，理想的解决方案是建立优良的智能模型并实施复杂的迭代学习或迭代演化。

为了寻求简单的划分方法，本文给出一个基于经验的假设：在相同长度的子时间段内，作业的相似度越高，工作的连续性和继承性越好，工作效率越高。于是，作业集划分要求转变为寻找若干组相似度最高的作业集合。属性向量能够较好地体现事物的内在特性，用属性向量夹角的余弦定义相似度具有非常自然的表现力。然而，余弦法丢失了属性向量的长度信息，不能很好地体现对象间各属性程度上的差异。鉴于此，本文直接使用属性向量差的模来表征相似度，如式(2)所示：

式中：wx=［x1，x2，…，xk］，wy=［y1，y2，…，yk］，分别表示对象wx与wy在k维属性空间中的属性向量;分量 x1，x2，…，xk与 y1，y2，…，yk在向量空间的k个基上取值，是对对象中参与评价的各属性的度量。

由式(2)可知，u(wx，wy)越小，wx与 wy的相似度越高。

定义属性向量的必要前提是构建对应的属性空间，即定义属性空间的基。以“设备安装”为例，通过对“人、机、料、法、环”各环节进行分析，提取出11个基本属性作为设备安装作业属性空间的基，并结合生产实际对这些属性的赋值方法进行指定，见表1。

1 相似度定义

相似度的概念由来已久，广泛应用于聚类、文本过滤等领域［2-3］。近年来，随着智能推荐系统的盛行，相似度计算方法由学术界向产业界成功迁移，取得了较好的应用效果［4］。

目前，智能推荐系统多采用属性向量夹角的余弦［5］来定义两个对象之间的相似度，如式(1)所示：

2 作业量约束

考虑到负载均衡要求，必须对划分出的作业集

表1 设备安装作业属性赋值表

的工作量(作业量)做出约束。本文给各个作业集分配相同的作业量，因此以各子时间段内作业量的平均值作为作业量的约束值R，通过R可判断某一个子时间段内是否分配了超额的工作。

式中：n为待划分作业的数量;Ei为第i个作业的工作量;T为子时间段的数量。

工作量Ei由经验给出，对其绝对值没有要求，但应注意各作业工作量相对值的合理性。T由计划时间总量和子时间段长度决定，通常以半天(可以连续工作)为一个子时间段，则T=2d(d为上层计划安排的完成工作总天数)。

3 作业集划分

对于目标作业集合，在获取集合中每个作业的属性向量、作业量及作业量约束值后，即可实施作业集划分。

作业集划分分为两个阶段进行，如图1所示。

第一阶段是在满足作业量约束的前提下将各作业按相似度归属到各子时间段内。为了避免难度大的作业大量聚集，首先将难度最大的作业归属到不同的子时间段内，并以此作为该子时间段的基准作业用于相似度计算。

由于存在“取整误差”，第一阶段划分结束后可能还存在没有被划分到任何子时间段的作业，对于这些作业，在第二阶段进行划分。该阶段的划分只针对“工作量最不足”的子时间段，即找出作业量最小的子时间段并将剩余作业中与其相似度最高的作业加入该子时间段，重复操作直到剩余作业全部划分结束。

图1 作业集划分流程

4 应用实例

以某型号“3天完成25台设备安装”的总装计划为例，按以下步骤开展作业集划分相关工作。

a．创建属性向量。

对所有25台设备在表1所定义的属性空间中创建属性向量，其各分量的取值见表2。

表2 设备安装属性向量表

b．计算相似度。

根据表2中各设备安装操作属性分量的取值，使用C语言编写程序，按公式 (2)计算两两设备之间的相似度，计算结果见式 (3)。矩阵中第x行第y列或第x列第y行所对应的取值即为u(wx，wy)。

c．获取作业量及作业量约束值。 经过实地调研，得到各设备安装操作作业量的经验值(无量纲，最小作业量取1)，见表3。

表3 设备安装操作作业量

d．作业集划分。

根据相似度、作业量及其约束值信息，按图1所示流程进行作业集划分，划分结果见表4。

结果显示，“第一天上午”和“第二天下午”的操作集中使用了升降车和行车;所有7项带热控的操作被分配到“第一天上午”、“第二天上午”和“第三天下午”统一实施;2项具有特殊着装要求的操作被安排在“第三天下午”连续开展;同时，分配在每个子时间段内的操作具有很高的“进舱”一致性，除“第一天下午”和“第三天下午”外的其他4个子时间段均只有1个操作与其他操作有不一样的“进舱”属性。

5 结束语

基于相似度的作业集划分具有逻辑上的合理性。通过总装现场应用发现，行车和升降车的使用效率提高，操作一岗转移工位的频率下降，操作工具及辅助物资摆放混乱或遗失的情况好转，整个过程有条不紊。

为了取得更好的划分效果，可改进划分依据，采用基于相似度的聚类算法代替本文中的基准作业相似度进行划分。但由于高维空间中的聚类算法需要很大的计算开销，需开发专门的智能系统来实现。

表4 设备安装作业集划分结果

［1］ 林耿．混合遗传模拟退火算法求解背包问题［J］．河南工程学院学报：自然科学版，2012，24(3)：66-69．

［2］ 刘明术，方宏彬，张建，等．属性相似度在聚类算法中的有效性研究［J］．计算机应用与软件，2012，29(9)：146-148．

［3］ 陈天，刘文浩．相似度算法分析与比较研究［J］．现代计算机，2012(18)：18-20．

［4］ 李海霞．购物网站个性化推荐系统应用分析［J］．产业经济，2012(15)：201．

［5］ 宋雅婷，徐天伟．基于用户兴趣的个性化推荐技术综述［J］．云南大学学报：自然科学版，2012，34(增刊 1)：20-23．