基于启发式算法的检测资源分配研究

屈力刚，宋昕一，田健琪，万景洋，肖 龙

（1.沈阳航空航天大学 航空制造工艺数字化国防重点学科实验室，辽宁 沈阳 110136；2.华晨汽车集团控股有限公司，辽宁 沈阳 110000）

随着国内制造业的快速发展，生产线自动化、柔性程度越来越高，企业多型号产品并线生产，产量成倍增加，因此，需要对产品几何量的检测效率提出更高的要求。

目前，产品几何量检测技术的研究已经从降低测点数量[1]、优化检测路径[2]、降低人为因素影响[3，4]、使用三维数模代替二维图纸进行编程等很多方面进行了研究。但企业同时存在严重的检测资源利用率低下，检测资源分配不合理等现象。以某研究院为例，其大量检具长时间闲置，个别检具满载运转。若能进行合理的检测资源分配，提高闲置检测资源的利用率，则能大大提高企业的检测效率。针对此问题，本文提出了基于启发式算法，针对检测资源分配问题进行了系统研究。

1 检测资源能力模型建立

启发式算法（Heuristic Algorithm），是用一个问题的最优算法求得该问题每一个实例的最优解。基于启发式算法的检测资源分配在分配过程中需考虑三点：①检具是否有所需的检测能力；②总检测时间；③检测总成本。

检具的检测能力主要分为：尺寸检测能力、精度能力、形状检测能力、检测效率能力。若使用三坐标测量机，则还包括测头库和检测工艺能力，如图1所示。

图1 检测设备资源能力模型

在测量一个零件时，首先考虑零件的基本尺寸是否在其测量范围内，测量设备的测量精度是否满足要求。其次通过零件的外形，判断检具是否具有其形状检测能力（若使用三坐标测量机，则还需考虑其测针是否够长，测座可旋转角度，球头能否顺利进行触测）。在此基础上，考虑其测量效率和批量检测能力[5]。

2 检测工艺过程节点图构建

2.1 非线性检测工艺规划

在产品的整个生产周期中，检测工艺伴随加工工艺贯穿始终。一套完整的工艺由多个加工工序和检测工序组合而成。其检测工艺描述如图2所示。

图2 某非线性检测工艺描述

其中符号表示选择关系，符号表示并行关系。图中的非线性检测工艺结构化描述如下：

如图3所示，每道检测工序有多种检测资源类型可供选择，而每种检测资源类型又对应着多型号的检测设备。检测工艺与检测资源之间存在着复杂的相互影响的关系，不同检测设备的检测效率、测量精度和使用成本不同，因此不同的分配方式决定了不同的测量效率和测量成本。因此，检测资源的分配是复杂的非线性规划的问题。

2.2 检测工艺过程节点图构建

产品的检测工艺路线将直接影响检测时间。某零件的非线性检测工艺路线如图4所示。

可以利用检测过程节点图将检测工艺资源分配问题变换为网络图问题。通过其关键路径得出检测时间，再通过仿真，实现工艺规划。其工艺路线图可转化为如图5所示的节点图[6]。

图中各节点表示各道检测工序，箭头指向表示各道检测工序之间的顺序。当涉及到多个零件的检测工艺路线时，不同的零部件可以并行地进行检测，这样就可以构建整个产品检测工艺路线节点图。

对每道检测工序进行检测资源分配后，网络图就会有具体的检测时长和检测成本信息。不同的检测设备检测相同的工序所需时间和成本不同，因此，检测设备的分配直接影响整个检测的成本和时间。

图3 检测工艺资源优化分配模型

图4 某零件的非线性检测工艺路线图

图5 非线性检测工艺路线节点图

对检测工艺结构图来说，在检测能力满足的情况下，对总检测时间影响最大的是图中的最长路径，即关键路径（Critical Path）。当检测资源分配情况不同时，检测时间会因检测设备的不同而发生变化。因此，此问题可以使用CPM（Critical Path Method）计算。

3 检测工艺资源分配模型的建立

3.1 模型优化规则

在满足检测能力的基础上，检测工艺资源分配主要考虑两个因素：检测成本和检测时间。现确定检测工艺资源分配的基本规则如下：

规则1：某一类检测工艺资源的检测设备在同一时间只能检测一道工序。这是因为企业的检测资源具有唯一性。在企业中，每台设备都有唯一的标识。制定这一规则是为了保证检测资源分配不冲突。

规则2：产品的检测时间都是有限制的，因此检测工艺资源的分配必须满足时间约束。超出规定的时间约束就扰乱产品生产的效率。当所分配的检测资源不能满足时间约束的时候，就必须进行重新分配，以减少检测时间。

规则3：在满足1、2条的基础上，尽可能保证检测工艺资源成本最低。

规则3是检测工艺资源分配的总目标，时间约束和资源不冲突约束都是对检测过程的约束。

根据检测工艺资源分配的基本规则，制定如下步骤：

（1）检测资源在分配过程中必须达到的是规则1和3，检测资源分配成本最低，且进行检测的资源都是独一无二的，以保证无冲突。

（2）如果检测资源在分配过程中违反了规则2，那么必须对检测资源进行重新分配，缩短检测完成时间。

（3）若检测资源分配方案最后得出的时间远小于约束时间，则应适当的对检测资源进行调整，以保证成本最低。

3.2 检测工艺资源分配模型的建立

由检测资源分配规则可知，所建立的数学模型是以检测时间和检测资源唯一性为约束条件，总检测成本为优化目标的函数。

假设一个检测工艺网络图中有N个任务节点，每道工序有M种检测资源可用，若第j种检测资源分配到每i个检测任务工序的每小时检测成本为Cij（j=1，2…m），第j种检测资源完成该道检测工序的时间是Tij。选中第j种检测资源是Aij=1。则可以得出检测工艺资源的分配的求解函数：

需要保证总的检测成本最低，有如下约束：

（3）Tcpm（T1，T2，…Tn）≤T0（4），表示检测的最长时间不得超过规定的检测时间。

4 算法求解

基于启发式算法的检测工艺资源分配共用到三种函数，分别是：①基于检测成本的检测工艺资源分配函数；②冲突调节函数；③考虑到时间约束的检测工艺资源分配函数。如图6所示。

算法的输入是：①各检测任务之间的先后顺序，即检测工艺路线节点图；②检测资源的分类和检测成本；③检测资源的检测能力信息。

算法的输出是：①检测资源分配信息；②最长检测时间；③总检测成本。

图6 基于启发式算法的检测工艺资源分配流程

4.1 基于成本的检测工艺资源分配

基于成本的检测工艺资源分配算法是在不计检测时间和工艺资源唯一性的约束的前提下，直接以成本最低为目的对检测资源进行优化分配，并未考虑检测资源的唯一性，只是将检测成本最低纳入考量。启发式算法的输入是检测资源分配情况，检测任务先后顺序和每一类检测资源的检测能力、成本信息等。启发式算法的输出是资源分配表、总检测时间和成本。

其分配过程如图7所示。

4.2 冲突调节函数

检测工艺资源初始值分配完毕后，需对有检测资源冲突的任务节点进行筛选，采用双重嵌套循环检查。当检查到任务节点V和V0之间有检测工艺资源冲突时，在不改变其他节点资源分配的情况下进行重新分配。在重新进行检测工艺资源分配的过程中，主要考虑总检测时间和总检测成本。在检测时间最短的情况下，控制使其检测成本最低。如图8所示。

4.3 考虑时间约束的检测工艺资源分配

基于成本的检测工艺资源分配算法没有考虑时间限制，但为了满足生产节拍需求，实际应用过程中的检测资源分配必须满足时间约束，在基于成本的分配方法前提下进行调整。如图9所示。

图7 基于检测成本的检测工艺资源分配算法流程图

图8 冲突调节函数流程图

该算法的最终目的是在保证检测时间满足要求的情况下，追求检测成本最低。在某一任务节点中，若重新分配检测工艺资源，则检测时间和检测成本都会发生改变。设节点T0中，按前两个算法对检测工艺资源S0（检测成本Expense0、检测时间T0）进行了选择。将其他可选的检测工艺资源（检测成本Expense′、检测时间T′）与已选定的检测工艺资源进行对比。计算补偿率△Time/△Expense的值。高补偿率检测资源在保证增加成本较小的情况下更有利于缩短检测时间。补偿率计算公式为：（T0-T′）/（Expense′-Expense0）。

此调整算法需首先选择当前的关键路径，其中各任务节点可用检测工艺资源的补偿率进行计算，选择最大补偿率资源，并进行冲突消解，计算整个检测工艺过程节点图的补偿率。对所有任务节点进行遍历后，选择整个检测工艺过程中补偿率最大的资源分配方法进行检测工艺资源重新分配。然后判断检测时间是否满足要求，若检测时间不满足要求，则需重新寻找关键路径并继续对检测工艺资源进行优化分配，以缩短时间。当检测最大路径在要求范围内时，循环结束，完成资源分配。若所有检测工艺资源能力不足以满足时间要求时，直接退出循环。

4.4 实例验证

图9 考虑时间约束的检测工艺资源分配调整算法流程图

以下图所示的检测工艺路线为例，共有7个任务和3条路径。本道检测工艺限制时间为8小时。

针对如图10所示检测工艺路线，设如表1所示的检测资源分类情况。假设同种类检测资源的使用成本和检测能力相同。

图10 检测工艺路线图

设检测资源检测能力如表2所示。

工艺路线的节点图如图11所示。

由图11可见，该检测工艺路线比较简单。首先，计算出各道工序所需成本和时间，如表3所示，括号内为工序所需的检测时间。

表1 检测资源分类表

首先，运用基于成本的检测工序资源分配算法，对检测资源进行初始分配。为每一道检测工序选取检测成本最低的检测资源，得到如表4所示资源分配结果。

表中的检测设备分配结果较为理想化，其关键路径是P1-P2（P3）-P4-P7可见检测任务P1和检测任务P6之间存在检测资源冲突。在此情况下，使用冲突调解算法，将设备S5分配给任务P1和任务P6再重新进行成本计算。将设备S5分配给任务P1时，任务P6可使用检测设备S22，分配情况如表5所示。

表2 检测资源能力表

图11 检测工艺节点图

表3 各道检测工序总成本和所用时间表

表4 基于成本的检测工艺资源分配结果

因检测工艺的限制时间是8小时，而最长检测时间是9小时，显然不能满足需求。这时利用考虑时间约束的算法调整，计算关键路径P1-P2（P3）-P4-P7中各个检测资源的补偿率Rv=△Time/△Expense值，经过计算，只有P4工序的比值为正，Rv=0.25。对工序P4的检测资源进行调整，将P4的检测资源调整为S42，这时满足了时间限制，退出算法。其最终分配结果如表6所示。

表5 冲突调节后的检测工艺资源分配结果

表6 考虑时间约束的检测工艺资源分配结果

若需要进一步缩短检测时间，则需针对分配情况重新确定关键路径，计算每一道工序的时间成本比Rv，并选择Rv最大的工序进行调整分配。

5 结论

本文分析了检测资源分配多样性的成因，并且建立了检测资源能力模型和检测资源分配求解函数，以检测时间为约束，检测总成本为目标函数，通过启发式算法进行检测资源分配的优化求解，实现了企业检测资源分配的合理化、规范化和利用率最大化。本算法支持从检测资源能力方面进行检测资源合理分配，并且能够从检测时间和检测成本两方面进行检测资源的合理分配，为企业节省检测成本及时间成本。经某汽车企业实例验证，基于启发式算法的检测工艺资源分配可提高检测效率30%，对于企业生产来说，具有很大的实用价值及深远意义。

参考文献：

[1] 卢耀晖，周继伟，张 蔚，等.基于三坐标测量机的平面测量方法研究[J].装备制造技术，2011，（4）：110-113.

[2] 王世刚，付宜利.数字化环境下在线检测路径优化技术的研究[J].组合机床与自动化加工技术，2009，（5）：52-55+60.

[3] 屈力刚，田健琪，韩 义，等.基于MBD的三坐标检测工艺系统构建技术研究[J].制造业自动化，2017，39（2）：1-4.

[4]刘达新.基于三维CAD的智能三坐标测量机检测规划系统的研究与开发[D].合肥：合肥工业大学，2009.

[5] 蔡 菲.工艺资源管理及应用研究[D].武汉：武汉理工大学，2010.

[6] 骆 珣，等.项目管理教程 [M].北京：机械工业出版社，2004：160-170.