ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (9): 1865-1879.doi: 10.7544/issn1000-1239.2017.20160513

• 软件技术 •    下一篇

支持社会协同计算的跨组织工作流任务分派算法

孙勇1,谭文安1,2   

  1. 1(南京航空航天大学计算机科学与技术学院 南京 211106);2(上海第二工业大学计算机与信息工程学院 上海 201209) (syong@nuaa.edu.cn)
  • 出版日期: 2017-09-01
  • 基金资助: 
    国家自然科学基金项目(61672022,61272036);安徽省高校自然科学基金重点项目(KJ2017A414)

Cross-Organizational Workflow Task Allocation Algorithms for Socially Aware Collaborative Computing

Sun Yong1, Tan Wenan1,2   

  1. 1(School of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 211106);2(College of Computer and Information, Shanghai Polytechnic University, Shanghai 201209)
  • Online: 2017-09-01

摘要: 针对社会协同计算带来的不可靠性和社会网络所固有的大规模性问题,提出了支持社会协同计算的跨组织工作流任务分派优化算法.首先,采用了基于工作流任务子网分层的优化模型,将复杂社会网络图进行有效地划分,从而简化了社会网络成员的协作关系评估问题;然后,根据划分后网络的拓扑特征,设计了一种基于工作流任务子网连接点的快速介数中心性计算方法,以高效地选取跨组织业务项目的领导者;最后,采用基于任务子网划分的最短路径近似算法,实现了快速查找跨组织业务过程的协作成员;并且,理论证明了支持社会协同计算的工作流分派算法的可行性.实验结果表明所提算法大幅降低了社会协同计算的复杂性,保证了较高的准确性,解决了工作流任务成员之间的关系评价和人工团队组合优化的时效性问题,为社会协同计算的任务分派提供了一种新的思路.

关键词: 协同计算, 团队组合, 任务分派, 跨组织工作流, 社会网络

Abstract: Recently, human-interactions are substantial part of Web service-oriented collaborations and cross-organizational business processes. Social networks can help to process crowdsourced workflow tasks among humans in a more effective manner. However, it is challenging to identify a group of prosperous collaborative partners with a leader to work on joint cross-organizational workflow tasks in a prompt and efficient way, especially when the number of alternative candidates is large in collaborative networks. Therefore, in this paper, a new and efficient algorithm has been proposed to find an optimal group in social networks so as to process crowdsourced workflow tasks. Firstly, a set of new concepts has been defined to remodel the social graph; then, a sub-graph connector-based betweenness centrality algorithm has been enhanced to efficiently identify the leader who serves as the host manager of the joint workflow tasks; finally, an efficient algorithm is proposed to find the workflow task members associated with the selected leader by confining the searching space in the set of connector nodes. Theoretical analysis and extensive experiments are conducted for validation purpose; and the experimental results on real data show that our algorithms outperform several existing algorithms in terms of computation time in dealing with the increasing number of workflow task executing candidates.

Key words: collaborative computing, team formation, task allocation, cross-organizational workflow, social network

中图分类号: