基于E-CARGO模型的多任务分配算法  

Multi-task assignment algorithms based on the E-CARGO model

作　　者：陈振[1] 朱海滨 盛寅[3] 高海波[1] 

机构地区：[1]湖南涉外经济学院信息科学与工程系,湖南长沙410205 [2]尼普森大学计算机与数学系 [3]南京大学工程管理系,江苏南京210008

出　　处：《计算机工程与科学》2016年第12期2542-2551,共10页Computer Engineering & Science

基　　金：加拿大国家科学与工程研究委员会基金(262075-2013)

摘　　要：多任务分配是管理和协同工作中的重要问题。采用E-CARGO建模来解决常规多任务分配问题(GMTAP)与组角色多任务分配问题(GRMTAP)。提出了两种算法:(1)通过把GMTAP质量评估矩阵转置转化为组角色分配问题(GRAP),再利用GRAP算法来完成多任务分配;(2)将GRMTAP分配问题转化为常规分配问题(GAP),利用K-M(亦称匈牙利)算法来实现多任务分配。最后,通过实验验证了GMTAP与GRMTAP算法的有效性,即,算法很好地满足了多任务分配问题的需要,也有效地扩展了GRAP算法与K-M算法的应用范围。Multi-task assignments are a critical problem in management and collaboration. At first, we formalize the general multi-task assignment problem （GMTAP） and the group role multi-task assignment problem （GRMTAP） with the Environments-Classes, Agents, Roles, Groups and Objects （E- CARGO） model. Then we propose two algorithms： （1） converting the GMTAP into a group role assign- ment problem （GRAP） by matrix transposing and using the GRAP algorithm to realize the task assignment; and （2） converting the GRMTAP into a GAP that is solved by the Kuhn-Munkres （K-M, also called Hungarian） algorithm. Finally, we conduct numerical experiments and analyze the solutions＂ performance. Results show that the proposed algorithms are effective, can meet the requirement of practical multi-task assignments and extend the application scope of the GRAP algorithm and the K-M algorithm.

关 键 词：E-CARGO模型 常规多任务分配 组角色多任务分配 常规分配问题(GAP) 组角色分配问题(GRAP) 

分 类 号：TP316[自动化与计算机技术—计算机软件与理论]