ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (4): 872-885.doi: 10.7544/issn1000-1239.2017.20151174

• 软件技术 • 上一篇    下一篇

基于协作相容性的工作流任务分配优化方法

胡海洋1,2,3,姬朝配1,胡华1,2,葛季栋3   

  1. 1(杭州电子科技大学计算机学院 杭州 310018); 2(复杂系统建模与仿真教育部重点实验室(杭州电子科技大学) 杭州 310018); 3(计算机软件新技术国家重点实验室(南京大学) 南京 210046) (huhaiyang@hdu.edu.cn)
  • 出版日期: 2017-04-01
  • 基金资助: 
    国家自然科学基金项目(61572162,61272188,61572251);浙江省哲学社会科学重点研究基地项目(14JDXX04YB);江苏省自科学基金项目(BK20131277);中央高校基本科研业务费专项资金项目(021714380004);南京大学计算机软件新技术国家重点实验室开放基金项目(KFKT2014B15);南京大学计算机软件新技术国家重点实验室创新项目(ZZKT2013B14)

Method for Optimizing Task Allocation in Workflow System Based on Cooperative Compatibility

Hu Haiyang1,2,3, Ji Chaopei1, Hu Hua1,2, Ge Jidong3   

  1. 1(College of Computer Science, Hangzhou Dianzi University, Hangzhou 310018 ); 2(Key Laboratory of Complex Systems Modeling and Simulation (Hangzhou Dianzi University), Ministry of Education, Hangzhou 310018); 3(State Key Laboratory for Novel Software Technology (Nanjing University), Nanjing 210046)
  • Online: 2017-04-01

摘要: 工作流系统中任务分配策略将对其系统运行性能有很大的影响,在分配任务时不仅需要考虑执行者对相应任务的熟悉度,还需分析执行者之间配合协作的默契程度.传统研究工作在进行工作流任务分配时缺乏对执行者工作负载、执行者之间协作相容性的综合考虑.为了实现有效的任务分配,首先通过分析历史日志的信息,对执行者间的协作相容性进行分析计算,在此基础上综合考虑执行者当前的任务负载,提出了基于协作相容性的、负载均衡式任务分配模型,并给出了多目标联合优化的任务分配方法,可提高整个流程实例的执行效率,并保持执行者间的负载均衡.提出4种相应的算法,并分析了算法的时间复杂度,进行了系统性的对比实验,评估了所提出方法的正确性和有效性.

关键词: 工作流, 任务分配, 协作相容性, 负载均衡, 任务交互

Abstract: Task allocation strategy has an important influence on the performance efficiency of workflow system. When allocating tasks among executors, it needs to consider both the capability of each executor and the cooperative compatibility between the executors. Traditional methods for assigning tasks usually only consider the technical skills of executors and ignore the social cooperation compatibility among the executors. Although a few of research works have considered the social cooperation compatibility, they fail to consider how to maintain load balancing among executors when allocating the tasks. Based on the workflow log, cooperative compatibilities among executors are modeled and computed. The relations of interaction tasks are also taken into account. By analyzing the current workload of each executor, a multi-objective joint optimization framework for maintaining load balancing and maximizing the cooperative compatibility among executors is proposed. In this framework, when a new task is assigned, the current workload of each executor that can perform this task will be analyzed and its cooperation capability to other executors that have been assigned those tasks having interactions with this new task will be computed. Several corresponding algorithms are designed for optimizing different objectives and their time complexity is analyzed. Extensive experiments are conducted for comparing the proposed methods which demonstrate the correctness and effectiveness of our approaches.

Key words: workflow, task assignment, cooperation compatibility, load balancing, task interaction

中图分类号: