多影响因素的加权任务分配范文

《计算机与数字工程杂志》2014年第七期

1任务分配策略研究

1.1分配策略的形式化表示定义1在工作流定义中有一项任务Jnew被分配给一个抽象的角色，而这个角色包含了多个员工。每一个候选员工都已经存在一个任务列表，任务分配问题就是根据任务属性及候选人状态把任务分配给最适合的候选人。定义2参与员工状态有效性。在参与员工执行工作过程中，经常会因为如出差、休假等原因而无法工作。对于给定的参与员工Ui∈U。

1.2基于多影响因素的加权任务分配策略通过对实际流程中的任务分配进行分析，发现最影响任务的执行效率的是任务分配不均导致的任务间等待，负载均衡在任务实际分配当中是至关重要的，所以将本分配算法设计为两阶段：第一阶段根据参与者的状态有效性和负载状况划分资源候选者集合，第二阶段从资源候选者集合中按照综合匹配度进行执行者集合划分，将任务分配给评估分数最高的执行者集合。在计时器规定的时间内，如果没有员工执行此项任务，则工作流引擎会从之前的评估结果中筛掉目前执行者集合，然后再次对任务进行分配。资源执行者集合的确定过程如下：对一项特定的工作项任务Jnew，计算其相对预测负载偏差值，将参与员工划分成不同的负载区间，每一区间内的参与员工被认为具有相似的任务负载。参与员工的相对预测负载偏差区间数量的选择，可以根据具体的企业需求灵活的调整。预测负载偏差区间的设定方法如下：设N为相对预测负载偏差区间数，R［N＋1］为相对预测负载偏差数组。其中，R［0］＝－1，R［N］＝＋1，区间的上下界可以根据工作流要求确定。Sk为属于第k个区间中的候选者集合，k越大预测负载越重，k＝1，2，…，N。对于参与者Ui，如果N［k－1］β（Ui，Jj）＜N［k］，则Ui被划分到k区间。当区间数过小的时候，负载均衡的程度将会变得很低，也失去了负载均衡的意义；当区间数过大接近员工数时，对于后面的综合评估就没有意义了，所以相对预测负载偏差区间数不宜过小，也不宜过大。选择相对负载较轻的区间为资源候选集合，对集合中的每一个员工的执行能力、感兴趣度和成本进行综合的评估，本文提出了一个带有权值的综合评估分数计算方法，根据确定的评估值，对确定的资源候选集合进行排序，并再次进行区间划分，设定方法如下：设M为评估值区间数，P［M＋1］评估值区间数组，对评估值最高的数值偏差在a之内的，放入P［0］，偏差为a～2a的放入P［1］，依次类推，直到M数组执行完毕。M和a值可设定，评估值区间数M的选择也可以根据企业的需求灵活的调整；这样排名最靠前的候选集合就是任务的最合适执行者集合。

1.3算法实现1）启动计时器，初始化参数，置T＝1；2）获取要执行的任务Jnew，确定相对预测负载偏差区间数N、评估值区间数M和偏差值a及各影响因素权值w1、w2、w3；3）根据流程定义找到符合条件能够承担任务的所有参与者集合S（其中要求参与者的状态有效性availability（Ui）＞0）；4）计算每个参与者Ui的预测负载PreWol（Ui），以及任务Jnew的平均预测负载TaskPreWol（Jj）。

2实验

与当前的基于多准则的任务分配策略相比，本策略增加了状态有效性和成本两个影响因素，能够在算法执行前筛除状态无效用户，避免了由无效用户执行任务导致流程挂起的情况，可以提高流程执行效率，对于成本因素的计算使得该策略更加具有普适性。为了评价本文提出的任务分配算法的负载性能，我们将算法进行仿真实验。各个员工对分配任务得到的处理顺序是先进先出的处理原则，不进行任何的优先调度，由于采用这种原则，本实验不考虑计时器进行再次分配的情况。在测试期间测试100个工作流实例的运行情况，将三个并行任务T1、T2和T3分配给四个员工（U1，U2，U3，U4），设所有参与者状态有效性均为1，评估因素影响权值为w1＝0．6，w2＝0．2，w3＝0．2。表2给出了参与员工执行三类任务的影响因素评估值，表3给出了员工完成任务所需时间。根据上述测试环境，对Round－Robin以及基于多影响因素的加权任务分配算法进行负载分析，负载结果如图1～图3所示。从图1与图2中可看出，当执行任务数较多时，Round－Robin算法的负载不均衡，执行能力强、速度快的U1和U2负载较轻，而执行能力一般的U3和U4则负载较大；基于多影响因素的加权任务分配算法则做到了负载均衡，随着任务数的增加曲线也成线性增长，负载均衡趋势不会改变。而且，在任务的总执行时间上，本文的算法相对于Round－Robin算法也有了一定程度的降低，如图3所示。从图中可以看出，当任务数大于60后，多因素加权算法的总执行时间相对较少。综合进行评估，基于多影响因素的加权任务分配算法在提高流程执行效率方面有很大帮助。

3结语

实现任务的自动优选分配是提高工作流系统运行效率的关键步骤，本文在前人研究的基础上提出了基于多影响因素的加权任务分配策略，该策略综合考虑了参与者状态有效性、负载、参与者能力、兴趣度以及成本因素，设计并实现了基于多影响因素的加权任务分配算法。通过实验结果可以看出，该算法可有效降低任务平均等待时间和人员负载，提高了任务平均处理效率。同时，由于各影响因素权重可按需调节，该策略能很好地适应不同领域业务对任务分配的不同需求，解决工作流在任务分配上的灵活性问题，更加具有普适性。

作者：尚福华孙胜男陈效果单位：东北石油大学计算机信息技术学院东方地球物理勘探有限公司