广东工业大学学报 ›› 2017, Vol. 34 ›› Issue (03): 21-29.doi: 10.12052/gdutxb.170013

• 大数据基础理论与应用专题 • 上一篇    下一篇

先序约束下的群组角色指派及其优化

刘冬宁, 卢明俊, 黄宝莹, 梁路   

  1. 广东工业大学 计算机学院, 广东 广州 510006
  • 收稿日期:2017-01-11 出版日期:2017-05-09 发布日期:2017-05-09
  • 作者简介:刘冬宁(1979-),男,副教授,博士,主要研究方向为人工智能逻辑、协同计算.
  • 基金资助:

    国家自然科学基金资助项目（61402118，61673123）；广东省科技计划项目（2015B090901016，2016B010108007）；广东省教育厅项目（粤教高函2015[133]号，粤教高函[2014]97号）；广州市科技计划项目（201604020145，2016201604030034，201508010067）

Group Role Assignment and its Optimization with Preorder Constraints

Liu Dong-ning, Lu Ming-jun, Huang Bao-ying, Liang Lu   

  1. School of Computers, Guangdong University of Technology, Guangzhou 510006, China
  • Received:2017-01-11 Online:2017-05-09 Published:2017-05-09

HTML

PDF (PC)

2947

摘要：

在协同工作中如团队分工明确具体，协作将轻松易行，然而复杂的数据耦合、时空冲突等约束关系往往制约了任务的分工和指派.先序约束是最重要而又难于处理的约束之一，其体现了任务分发的先决条件关联.为此本文于指派模型中引入角色，使用角色对任务分工进行抽象与建模，并对先序约束下的指派作表达与计算.相关问题的穷举处理时间复杂度为Σ2P级，为优化加速，论文提出了能快速收敛的多对多线性指派规划算法，并用IMB ILOG CPLEX软件包进行了模拟仿真.经比较，相关方法的优化率可达80%~100%，均值为94%，能满足有限时间内对问题处理规模与团队性能保持的要求，为团队协作与生产管理提供了有效支撑.

关键词: 角色协同, 群组角色指派, 先序约束, 线性指派规划, 大数据

Abstract:

If everyone or a unit in a team is assigned to specific work, the cooperation between teammates will be much easier than that without specific assignments. Nonetheless, due to the complexity of data coupling and space-time, the assignments with conflict constraints are a big challenge. As one of the most important but intractable constraints, the preorder constraint determines the prerequisites of assignments. Therefore, roles are introduced to abstract and model the assignment problem and express the assignment with the preorder constraints. Tested by the exhaustive method, the complexity of the proposed problem is of Σ2P. In order to optimize the solution of the problem and accelerate the processing speed, a multiple objective linear programming approach is proposed with the application of IMB ILOG CPLEX. To verify the proposed approach, simulation experiments are conducted. The optimization rate of the proposed approach could reach 80% to 100%, average 94%, which can meet the requirements of solving a certain number of problems within limited time as well as guarantee an excellent team performance and hence help support collaboration and management effectively.

Key words: role-based collaboration, group role assignment, preorder constraint, linear assignment problem, big data

中图分类号: 

  • TP301

[1] 王元卓, 靳小龙, 程学旗. 网络大数据:现状与展望[J]. 计算机学报, 2013, 36(6):1-15. WANG Y Z, JIN X L, CHENG X Q. Network big data:present and future[J], Chinese Journal of Computers, 2013, 36(6):1-15.
[2] 王勇, 许钟涛, 王瑛. 大数据环境下竞争情报系统的研究与实验[J]. 广东工业大学学报, 2014, 31(3):27-31. WANG R, XU Z T, WANG Y. Research and implementation on competitive intelligence system based on big data[J]. Journal of Guangdong University of Technology, 2014, 31(3):27-31.
[3] ZHU H, ZHOU M C. Role-based collaboration and its kernel mechanisms[J]. IEEE Transactions on Systems, Man and Cybernetics, Part C, 2006, 36(4):578-589.
[4] 宋静静, 李振坤, 胡其伟, 等. MAOCW及其在Web选课中的应用[J]. 广东工业大学学报, 2005, 22(2):83-88. SONG J J, LI Z K, HU Q W, et al. MAOCW and its application in course selecting on Web[J]. Journal of Guangdong University of Technology, 2005, 22(2):83-88.
[5] ZHU H, ZHOU M C. Efficient role transfer based on Kuhn-Munkres algorithm[J]. IEEE Trans. on Systems, Man and Cybernetics, Part A:Systems and Humans, 2012, 42(2):491-496.
[6] ZHU H, ZHOU M. M-M role-transfer problems and their solutions[J]. IEEE Trans. on SMC(A), 2009, 39(2):448-459.
[7] 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.
[8] MUNKRES J. Algorithms for the assignment and transportation problems[J]. Journal of the Society for Industrial and Applied Mathematics, 1957, 5(1):32-38.
[9] ZHU H B, LIU D N, ZHANG S Q, et al. Solving the Many to Many assignment problem by improving the Kuhn-Munkres algorithm with backtracking[J]. Theoretical Computer Science, 2016, 618:30-41.
[10] BALINSKI M L. Signature methods for the assignment problem[J]. Operations Research, 1985, 33(3):527-536.
[11] 王若鹏, 徐红敏. 基于X2拟合优度检验的席位公平分配模型[J]. 系统工程理论与实践, 2014, 34(7):1732-1738. WANG R P, XU H M. A fair apportioning seats model based on chi square goodness of fit test[J]. Systems Engineering-Theory & Practice. 2014, 34(7):1732-1738.
[12] 张其亮, 陈永生. 基于混合粒子群-NEH算法求解无等待柔性流水车间调度问题[J]. 系统工程理论与实践, 2014, 34(3):802-809. ZHANG Q L, CHEN R S. Hybrid PSO-NEH algorithm for solving no-wait flexible flow shop scheduling problem[J]. Systems Engineering-Theory & Practice, 2014, 34(3):802-809.
[13] LEE Z J, SU S F, LEE C Y. Efficiently solving general weapon-target assignment problem by genetic algorithms with greedy eugenics[J]. Systems, Man, and Cybernetics, Part B:Cybernetics, IEEE Transactions on, 2003, 33(1):113-121.
[14] TOROSLU I H, ARSLANOGLU Y. Genetic algorithm for the personnel assignment problem with multiple objectives[J]. Information Sciences, 2007, 177(3):787-803.
[15] 赵继军, 谷志群, 薛亮, 等. WSN中层次型拓扑控制与网络资源配置联合设计方法[J]. 自动化学报, 2015, 41(3):646-660. ZHAO J J, GU Z Q, XIE L, et al. A joint design method of Hierarchical topology control and network resource allocation for Wireless Sensor Network[J]. Acta Automatica Sinica, 2015, 41(3):646-660.
[16] BURKARD R E, DELL'AMICO M, MARTELLO S. Assignment problems[M]. Revised Reprint. Siam:[s. n.], 2009.
[17] HAJRI-GABOUJ S. A fuzzy genetic multi-objective optimization algorithm for a multilevel generalized assignment problem[J]. Systems, Man, and Cybernetics, Part C:Applications and Reviews, IEEE Transactions on, 2003, 33(2):214-224.
[18] KIM Y H, MOON B R. Multicampaign assignment problem[J]. Knowledge and Data Engineering, IEEE Transactions on, 2006, 18(3):405-414.
[19] 孔维健, 柴天佑, 丁进良, 等. 镁砂熔炼过程全厂电能分配实时多目标优化方法研究[J]. 自动化学报, 2014, 40(1):51-61. KONG W J, CHAI T Y, DING J L, et al. A real-time multiobjective electric energy allocation optimization approach for the smelting process of magnesia[J]. Acta Automatica Sinica, 2014, 40(1):51-61.
[20] STÜTZLE T. Iterated local search for the quadratic assignment problem[J]. European Journal of Operational Research, 2006, 174(3):1519-1539.
[1] 张巍, 仝茹, 吴诗珏, 王子奇, 滕少华. 基于KD45闭包的群组角色指派研究[J]. 广东工业大学学报, 2021, 38(04): 26-34.
[2] 刘洪伟, 梁周扬, 左妹华, 陆丹, 范梦婷, 何锐超. 利用消费者浏览行为识别品牌竞争关系研究[J]. 广东工业大学学报, 2019, 36(05): 1-6,13.
[3] 黄健文, 朱雪梅, 徐莹, 熊璐, 张伟国. 基于多源大数据的岭南地区老旧小区空间形态量化研究[J]. 广东工业大学学报, 2019, 36(04): 70-79.
[4] 刘冬宁, 刘统武, 宋静静, 侯艳. 面向基站代维人员分工协作优化的多重指派研究[J]. 广东工业大学学报, 2018, 35(06): 69-76.
[5] 白颉, 姚家进, 张茂军, 李桥兴. 金融大数据中条件非相关波动模型的单纯形搜索算法[J]. 广东工业大学学报, 2018, 35(05): 26-30.
[6] 孙为军, 谢胜利, 汪谷银, 刁俊武, 阮航. 智能工厂工业大数据云平台的设计与实现[J]. 广东工业大学学报, 2018, 35(03): 67-71.
[7] 李卫华, 李志猛. 基于大数据运输集团生产运营决策系统的构建及应用[J]. 广东工业大学学报, 2018, 35(03): 113-118.
[8] 饶东宁, 王军星, 魏来, 王雅丽. 并行最小割算法及其在金融社交网络中的应用[J]. 广东工业大学学报, 2018, 35(02): 46-50.
[9] 谢振东, 吴金成, 李之明, 伍冠桦. 企业大数据能力的构建与培育研究[J]. 广东工业大学学报, 2017, 34(03): 110-114.
[10] 饶东宁, 温远丽, 魏来, 王雅丽. 基于Spark平台的社交网络在不同文化环境中的中心度加权算法[J]. 广东工业大学学报, 2017, 34(03): 15-20.
[11] 毛莉娜, 李卫华. 用信息流和知网构建大数据语义共享通道研究[J]. 广东工业大学学报, 2017, 34(03): 30-35.
[12] 杜汉昌, 丁磊, 冯永晋. 面向零售业的大数据商业智能系统研究[J]. 广东工业大学学报, 2014, 31(4): 41-45.
[13] 李桥兴, 强保华, 杨春燕. 大数据基元的HBase数据库存储模型与实现[J]. 广东工业大学学报, 2014, 31(3): 8-13.
[14] 王勇, 许钟涛, 王瑛. 大数据环境下竞争情报系统的研究与实现[J]. 广东工业大学学报, 2014, 31(3): 27-31.
[15] 刘洪伟, 刘智慧, 朱慧, 陆涛. 大数据环境下跨组织间协同优化决策的隐私保护算法[J]. 广东工业大学学报, 2014, 31(3): 21-26.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2017 《广东工业大学学报》编辑部
地址：广州市东风东路729号广东工业大学 邮编：510090
电话：020-37626653,020-37626139,020-37626396
邮箱：xbzrb@gdut.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发