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

计算机工程与科学

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

陈振1，朱海滨2，盛寅3，高海波1

(1.湖南涉外经济学院信息科学与工程系，湖南长沙 410205;

2.尼普森大学计算机与数学系，安大略诺斯贝 P1B8L7;3.南京大学工程管理系，江苏南京 210008)

收稿日期:2015-10-09 修回日期:2015-11-26 出版日期:2016-12-25 发布日期:2016-12-25
基金资助:
加拿大国家科学与工程研究委员会基金(2620752013)

Multitask assignment algorithms

based on the ECARGO model

CHEN Zhen1,ZHU Haibin2,SHENG Yin3,GAO Haibo1

(1.School of Information Science and Engineering,Hunan International Economics University,Changsha 410205,China;

2.Department of Computer Science and Mathematics,Nipissing University,North Bay,ON P1B 8L7,Canada;

3.Department of Control and System Engineering,Nanjing University,Nanjing 210008,China)

Received:2015-10-09 Revised:2015-11-26 Online:2016-12-25 Published:2016-12-25

摘要/Abstract

摘要：

多任务分配是管理和协同工作中的重要问题。采用ECARGO建模来解决常规多任务分配问题（GMTAP）与组角色多任务分配问题（GRMTAP）。提出了两种算法：(1）通过把GMTAP质量评估矩阵转置转化为组角色分配问题（GRAP），再利用GRAP算法来完成多任务分配；(2）将GRMTAP分配问题转化为常规分配问题（GAP），利用KM（亦称匈牙利）算法来实现多任务分配。最后，通过实验验证了GMTAP与GRMTAP算法的有效性，即，算法很好地满足了多任务分配问题的需要，也有效地扩展了GRAP算法与KM算法的应用范围。

关键词:

ECARGO模型, 常规多任务分配, 组角色多任务分配, 常规分配问题（GAP）, 组角色分配问题（GRAP）

Abstract:

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 assignment 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.

Key words:

ECARGO model, general multitask assignment, group role multitask assignment, general assignment problem, group role assignment problem

陈振1，朱海滨2，盛寅3，高海波1. 基于E-CARGO模型的多任务分配算法[J]. 计算机工程与科学.

CHEN Zhen1,ZHU Haibin2,SHENG Yin3,GAO Haibo1.

Multitask assignment algorithms

based on the ECARGO model

[J]. Computer Engineering & Science.

参考文献［26］

［1］	Zhu H, Zhou M C. Rolebased collaboration and its kernel mechanisms［J］.IEEE Transactions on System,Man, and Cybernetics,PartC:Applications and Reviews,2006,36(4):578589.
［2］	Zhu H, Zhou M C. Roles in information systems:A survey［J］.IEEE Transactions on System,Man, and Cybernetics,Part C:Applications and Reviews,2008,38(3):377394.
［3］	Zhu H,Zhou M C,Alkins R.Group role assignment via a KuhnMunkres algorithmbased solution［J］.IEEE Transactions on Systems,Man and Cybernetics,Part A:Systems and Humans,2012,42(3):739750.
［4］	Zhu H,Zhou M C.MM roletransfer problems and their solutions［J］.IEEE Transactions on Systems,Man and Cybernetics,Part A:Systems and Humans,2009,39(2):448459.
［5］	Bertsekas D P.A new algorithm for the assignment problem［J］.Mathematical Programming,1981,21(1):152171.
［6］	Kuhn H W.The Hungarian method for the assignment problem［J］.NavalResearch Logistic Quarterly,2005,52(1):721.
［7］	Munkres J.Algorithms for the assignment and transportation problems［J］.Journal of the Society for Industrial and Applied Mathematics,1957,5(1):3238.
［8］	Riesen K,Bunke H.Approximate graph edit distance computation by means of bipartite graph matching［J］.Image and Vision Computing,2009,27(7):950959.
［9］	Turoff M,Chumer M,Van de Walle B,et al.The design of a dynamic emergency response management information system (DERMIS)［J］.Journal of Information Technology,Theory and Applications, 2004,5(4):135.
［10］	Zhu H,Zhou M C.Role transfer problems and algorithms［J］.IEEE Transactionson Systems,Man,and Cybernetics,PartA:Systems and Humans,2008,36(6):14421450.
［11］	Mi Jun. ISO application testing guide［M］. Beijing:Publishing House of Electronics Industry, 2014.(in Chinese)
［12］	Hatime H,Pendse R.Comparative study of task allocation strategies in multirobot systems［J］.IEEE Sensors Journal,2012,13(1):253262.
［13］	Alighanbari M.Task assignment algorithms for teams of UAVs in dynamic environments［D］.Massachusetts:Massachusetts Institute of Technology,2004.
［14］	Shi Z F,Yang B,Liu H Y.Modeling and simulation of UCAV swarm cooperative task assignment ［C］∥Proc of the 3rd International Conference on Information and Computing, 2010:308311.
［15］	Zhong L,Luo Q,Wen D,et al.A task assignment algorithm for multiple aerial vehicles to attack targets with dynamic values［J］.IEEE Transactions on Intelligent Transportation System,2013,14(1):236247.
［16］	Li Y Y, Min C P, Shen C L. MultiUCAV cooperative task assignment based on mixed generate algorithm［J］.EastSouth University Transaction,2005,35(suppl):5358.
［17］	Oh J, Wu C S. Geneticalgorithmbased realtime task scheduling with multiple goals［J］.Journal of Systems and Software,2004,71(3):24525.
［18］	Shen C,Tsai W. A graph matching approach to optimal task assignment in distributed computing system using a mini max criterion［J］.IEEE Transactions on Computer,1975,34(3):197203.
［19］	Wu W.On run time parallel scheduling for processor load balancing［J］.IEEE Transactions on Parallel and Distributed System,1997,8(2):173185.
［20］	Lee C,Shin K.Optimal task assignment in homogeneous networks［J］.IEEE Transactions on Parallel and Distributed System,1997,8(2):119129.
［21］	Liu J,Zhuge Q F,Gu S Z,et al.Minimizing system cost with efficient task assignment on heterogeneous multicore processors considering time constraint［J］.IEEE Transactions on Parallel and Distributed Systems,2014,25(8):21012112.
［22］	Armstrong R R,Hensgen D,Kidd T.The relative performance of various mapping algorithms is independent of sizable variances in runtime predictions ［C］∥Proc of the 7th IEEE Heterogeneous Computing Workshop,1998:7987.
［23］	Freund R,Gherrity M,Ambrosius S S,et al.Scheduling resources in multiuser,heterogeneous,computing environments with smartnet［C］∥Proc of the 7th IEEE Heterogeneous Computing Workshop,1998:184199.
［24］	Pilloni V,Navaratnam P,Vural S,et al.TAN:A distributed algorithm for dynamic task assignment in WSN［J］.IEEE Sensors Journal,2014,12(4):12661279.
［25］	Zhu J H,Gao H.An energy efficient algorithm for task allocation in wireless sensor networks［J］.Journal of Software,2007,18(5):11981207.(in Chinese)
［26］	Fu Qiang, Zheng Weimin. A dynamic task scheduling method in cluster of workstations［J］. Journal of Software, 1999,10(1):1923.(in Chinese)
	附中文参考文献:
［11］	芈峮.ISO测试指南［M］.北京：电子工业出版社，2014.
［25］	朱敬华,高宏.无线传感器网络中能源高效的任务分配算法［J］.软件学报,2007,18(5):11981207.
［26］	傅强,郑纬民.一种适用于机群系统的任务动态调度方法［J］.软件学报,1999,10(1):1923.

[1]	范韫. 基于EMD距离的稀疏自编码器[J]. 计算机工程与科学, 2022, 44(05): 894-900.
[2]	张志远, 陈海进. 基于动态矩阵的未知环境地图构建与路径规划[J]. 计算机工程与科学, 2022, 44(03): 563-570.
[3]	冯琪堯, 张惊雷, . 基于混合注意力机制的目标跟踪算法[J]. 计算机工程与科学, 2022, 44(02): 276-282.
[4]	张鑫, 冯秀芳. WiFi环境下基于CGRU-ELM混合模型的手势识别[J]. 计算机工程与科学, 2022, 44(02): 298-305.
[5]	万本庭, 方地长. 区间值广义正交模糊Frank算子及群决策方法[J]. 计算机工程与科学, 2022, 44(02): 345-354.
[6]	耿召里, 李目, 曹淑睿, 刘昶忻. 基于混合反向学习策略的鲸鱼优化算法[J]. 计算机工程与科学, 2022, 44(02): 355-363.
[7]	沈郭鑫, 蒋中云. 基于密度和中心指标的Canopy二分K-均值算法优化[J]. 计算机工程与科学, 2022, 44(02): 372-380.
[8]	崔振礼, 罗宇. 一种嵌入式双操作系统架构中外设资源动态迁移的研究与实现[J]. 计算机工程与科学, 2022, 44(01): 9-15.
[9]	侯兴旺, 赵若宇, 张玉书. 一种精确缩略图保持的图像加密方案[J]. 计算机工程与科学, 2022, 44(01): 60-67.
[10]	张晶, 李煜, . 改进的无约束优化3D-DV-Hop定位算法[J]. 计算机工程与科学, 2022, 44(01): 75-83.
[11]	火元莲, 徐晓鹏, 郑海亮. 基于无线能量采集的多跳网络安全传输中的路径选择[J]. 计算机工程与科学, 2021, 43(12): 2150-2156.
[12]	张治, 魏嘉鑫, 王林. LoRa数据传输网络混合加密设计[J]. 计算机工程与科学, 2021, 43(12): 2177-2182.
[13]	尹玲, 谢志军. 基于时空协作的多移动充电器充电路径规划的研究[J]. 计算机工程与科学, 2021, 43(12): 2183-2189.
[14]	孙宝贵, 车文刚, 廖江福, . 一种改进的KNN案例推理检索算法[J]. 计算机工程与科学, 2021, 43(12): 2263-2271.
[15]	裴凇莹, 陈振国. 基于文献计量的国内区块链技术研究及应用态势分析[J]. 计算机工程与科学, 2021, 43(11): 1966-1978.