收稿日期:20160113;修回日期:20160311 基金项目:加拿大国家科学与工程研究委员会基金资助项目(2620752013)
作者简介:陈振(1966),男,湖南冷水江人,副处长,教授,硕士,主要研究方向为数字图像处理、数据库系统实现技术与协同系统(chenZ2@
hieu.edu.cn);朱海滨(1963),男,山东东营人,加拿大尼普森大学协作系统实验室(CollaborativeSystemsLaboratory)主任及创始人,教授,博士,主
要研究方向为软件工程、服务计算与云计算、计算机协同、人机交互等;盛寅(1987),男,江苏南京人,博士,主要研究方向为计算机软件工程、分布
式计算机与协同计算.
GRMTAP算法中的任务权重与质量阈值分配问题
陈 振
1
,朱海滨
2,3
,盛 寅
3
,张 诚
1
(1.湖南涉外经济学院 教务处,长沙 410205;2.尼普森大学 计算机与数学系,加拿大 安大略 北部湾 P1B8L7;
3.南京大学 工程管理系,南京 210008)
摘 要:任务权重与质量阈值分配问题是管理和协同工作中多任务分配中的重要问题。基于 GRMTAP算法对
含有任务权重与质量阈值的多任务分配问题提出了有效的解决办法:a)针对任务权重提出了使用权重向量调整
多任务质量评价矩阵,调用 GRMTAP算法完成多任务的有效分配;b)针对质量阈值提出采用任务类别向量的元
素值之和之负值置换质量评价矩阵中评价质量值小于阈值的质量值,再调用 GRMTAP算法完成多任务的分配,
且以分配矩阵评价质量之和作为该分配是否成功的判断依据。这样有效地解决了含任务权重与质量阈值的多
任务分配问题,扩展 GRMTAP算法的应用范围。
关键词:ECARGO模型;组角色多任务分配;任务权重;质量阈值
中图分类号:TP301 文献标志码:A 文章编号:10013695(2017)03071805
doi:10.3969/j.issn.10013695.2017.03.018
AssignmentproblemwithtaskweightandqualificationthresholdinGRMTAP
ChenZhen
1
,ZhuHaibin
2,3
,ShengYin
3
,ZhangCheng
1
(1.AcademicAffairsOffice,HunanInternationalEconomicsUniversity,Changsha410205,China;2.Dept.ofComputerScience&Mathematics,
NipissingUniversity,NorthBayON,P1B8L7,Canada;3.Dept.ofManagement&Engineering,NanjingUniversity,Nanjing210008,China)
Abstract:Multitaskassignmentswithtaskweightsandqualificationthresholdsarecriticalproblemsinmanagementandcol
laboration.ThispaperproposedanefficientmethodbasedonGRMTAPformultitaskassignmentproblemwithtaskweights
andqualificationthresholds.a
)Itadjustedthequalityevaluationmatrixbyaweightvector,andthencalledtheGRMTAPalgo
rithmtorealizemultitaskassignment.b)Itreplacedtheevaluationvaluesthatwerelessthanthethresholdinthequalityevalu
ationmatrixwiththenegativesumofelementsinthetaskclassificationvector,calledtheGRMTAPalgorithmtofulfillthemulti
pletaskassignment,andthentookthemaximumsumoftheassignedevaluationqualityvaluesasthejudgmentstandard.This
methodeffectivelysolvesmultitaskassignmentproblemwithtaskweightsandqualificationthresholdsandextendstheapplica
tionscopeoftheGRMTAPalgorithm.
Keywords:ECARGOmodel;grouprolemultitasksassignment;taskweight;qualificationthreshold
0 引言
在协同系统中,基于角色的协同(rolebasedcollaboration,
RBC)是一种新兴的计算方法学,它以角色为核心机制,描述并
支持解决管理中的协同问题
[1]
。RBC主要包括角色协商、角
色分配与角色实施三项主要工作
[1]
。为了有效地利用 RBC解
决一些实际问题,文献[1~4]提出了 ECARGO模型来构建协
同系统,且利用 ECARGO建模完成了角色分配与角色转换的
相关研究。在 RBC中,角色分配是其重要问题之一。为了提
高协同的整体 性 能 与 效 果,文献 [5~7]提出常规分配问题
(generalassignmentproblems,GAP)相应 的 算 法与 改 进算 法。
其中,包括了非常著名的
KM算法
[6,7]
,也称为匈牙利算法,该
算法的时间复杂度为 O(m
3
),在工程领域中得到了广泛应用。
文献[3]就 组 角 色 分 配 问 题 (grouproleassignmentproblems,
GRAP)提出了算法,把 GRAP转换为 GAP,然后利用 KM算法
完成组角色的有效分配。
在 GAP与 GRAP中,一个 agent分配给一个角色,角色是
完整的,是不可再分割的。为了解决角色的可分割性,完成多
任务的分配,提出组角色多任务分配问题(grouprolemultitask
assignmentproblems
,GRMTAP)的分配算法。GRMTAP算法具
体实现过程是:a)把一个用于任务分配的 m×n的质量矩阵 Q
按照 agents要求分配的任务数向量 Z[i]与任务类别任务数量
分布向量 L[j]进行行列扩展;b)遵循 KM算法的要求把分配
求最大值问题转换为求最小值问题;c)调用 KM算法来求最
佳分配中间矩阵;d)完成分配矩阵的行列收缩共四个步骤,得
到最佳 m×n的任务分配矩阵 X,此时的
∑
n-1
i=0
∑
m-1
j=0
Q[i,j]×
X[i,j]值为最大值。这样,把多任务分配问题转换为 KM 算
法能够解决的问题,且通过算法实现和性能仿真实验验证了所
提方法的有效性。该算法的时间复杂度为 O(p×q)
3
,其中:p
是一个组中的 agent数,q是平均分配任务数。
该算法可应用于许多实际问题中,但是实际的多任务分配
第 34卷第 3期
2017年 3月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol34No3
Mar.2017