基于蚁群的工作流任务分配算法研究

Research on Workflow Task Allocation Algorithm Based on Ant Colony

影响工作流系统性能的因素不仅有工作流执行者的经验、兴趣与能力,还有执行者的当前任务负载,尤其在实例密集的情况下,通常会出现负载失衡或过载的现象,导致工作流效率与流程系统性能降低。针对这一问题,首先考虑流程关键任务对执行者负载的影响,将工作流任务结构定义成有向无环图DAG模型,使用拓扑序列确定关键路径与关键任务,在关键任务与任务负载之间建立联系。在此基础上,考虑执行者的预测负载,对执行者的负载进行量化与等级区间划分。随后给出一个基于蚁群的、依据关键任务与负载区间进行任务分配以保证负载均衡的任务分配算法(ACO-CT)。通过对比HEFT算法、Round_Robin算法,表明该算法可在兼顾负载均衡的基础上提升流程效率,并且具有较好的收敛性。

The factors that affect the performance of workflow system are not only the experience,interest and ability of workflow executor,but also the current task load of the executor.Especially in the case of dense instances,the load imbalance or overload often occurs,which leads to the decrease of workflow efficiency and process system performance.In order to solve this problem,firstly considering the impact of process critical tasks on the performer load,the workflow task structure is defined as the DAG model of directed acyclic graph,and the key path and key task are determined by topological sequence,and the relationship between the key task and task load is established.On this basis,considering the executor’s predicted load,the executor’s load is divided into grades and intervals.Then a task allocation algorithm based on ant colony(ACO-CT)is proposed,which is based on key tasks and load intervals to ensure load balance.The comparison of HEFT algorithm and Round_Robin algorithm shows that the proposed algorithm can improve the process efficiency on the basis of load balancing with better convergence.