ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2017, Vol. 54 ›› Issue (4): 872-885.doi: 10.7544/issn1000-1239.2017.20151174

Previous Articles     Next Articles

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

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

CLC Number: