Journal of Guangdong University of Technology ›› 2017, Vol. 34 ›› Issue (03): 21-29.doi: 10.12052/gdutxb.170013

Previous Articles     Next Articles

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

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

CLC Number: 

  • 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] Zhang Wei, Tong Ru, Wu Shi-jue, Wang Zi-qi, Teng Shao-hua. Group Role Assignment Based on KD45 Closure [J]. Journal of Guangdong University of Technology, 2021, 38(04): 26-34.
[2] Liu Dong-ning, Liu Tong-wu, Song Jing-jing, Hou Yan. Multiple Assignment in Task Allocation of Communication Base Stations [J]. Journal of Guangdong University of Technology, 2018, 35(06): 69-76.
[3] Liu Dong-ning, Wu Xiao-liang, Lu Ming-jian, Lu Ming-jun. Bidding Prediction of Advertisement Keywords via Group Role Combination [J]. Journal of Guangdong University of Technology, 2018, 35(03): 54-60.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!