广东工业大学学报 ›› 2021, Vol. 38 ›› Issue (05): 10-15.doi: 10.12052/gdutxb.210033

• • 上一篇    下一篇

冷却时间约束多对多任务分配及其优化

刘冬宁, 郑楚楚   

  1. 广东工业大学 计算机学院，广东省 广州市 510006
  • 收稿日期:2021-03-03 出版日期:2021-09-10 发布日期:2021-07-13
  • 作者简介:刘冬宁(1979–)，男，教授，博士，主要研究方向为协同计算、分布式智能系统
  • 基金资助:
    国家自然科学基金资助面上项目(62072120)

Task Allocation under Cool Down Time Constraints via the Many to Many Assignment

Liu Dong-ning, Zheng Chu-chu   

  1. School of Computers, Guangdong University of Technology, Guangzhou 510006, China
  • Received:2021-03-03 Online:2021-09-10 Published:2021-07-13

HTML

PDF (PC)

2620

摘要： 由于人员分配或资源调度过程中存在冷却时间, 导致人机协同多对多任务分配困难并且难以优化, 协同效应急剧下降, 本文旨在解决冷却时间约束多对多任务分配问题。主要使用角色协同理论(Role-Based Collaboration)及其通用模型E-CARGO(Environments-Classes, Agents, Roles, Groups, and Objects)的子模型群组角色多对多指派(Group Multirole Assignment, GMRA), 以医院医生出诊场景为例, 对冷却时间约束多对多指派形式化建模; 继而采用整数规划方法对冷却时间约束进行解耦与消解, 利用IBM CPLEX优化包对团队执行力的最大化做最优求解。进而在大规模仿真实验中, 采用必要条件对解空间进行了快速归约, 实现了秒级精确求解, 进一步论证了模型与方法的一般性、高效性和可靠性。

关键词: 人机协同, 任务分配, 多对多指派, 冷却时间约束

Abstract: Task allocation is a common and important problem in personnel management. In the process of allocation, it is often affected by many different constraints. One of them is the cool down time constraint. Due to the cool down time in personnel allocation or resource scheduling, it is difficult to allocate and optimize the many to many tasks in human-computer cooperation, and the collaboration effect drops sharply. The group multirole assignment (GMRA) is used to formalize the problem, and the integer programming used to decouple and eliminate the cool down time constraints. After that, IBM ILOG CPLEX optimization package (CPLEX) is used to optimize the team execution. In addition, in the large-scale simulation experiment, the necessary conditions are used to reduce the solution space quickly, and the second level accurate solution is achieved. The generality, efficiency and reliability of the model and method are further demonstrated.

Key words: human machine cooperation, task allocation, the many to many assignment, cool down time constraint

中图分类号: 

  • TP301
[1] MA S, ZHENG Y, WOLFSON O. Real-time city-scale taxi ridesharing [J]. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(7): 1782-1795.
[2] WANG F, XU J, CUI S. Optimal energy allocation and task offloading policy for wireless powered mobile edge computing systems [J]. IEEE Transactions on Wireless Communications, 2020, 19(4): 2443-2459.
[3] CAO Z, LIN C, ZHOU M, et al. Scheduling semiconductor testing facility by using Cuckoo search algorithm with reinforcement learning and surrogate modeling [J]. IEEE Transactions on Automation Science and Engineering, 2019, 16(2): 825-837.
[4] ZHAO Z, LIU S, ZHOU M, et al. Decomposition method for new single-machine scheduling problems from steel production systems [J]. IEEE Transactions on Automation Science and Engineering, 2020, 17(3): 1376-1387.
[5] ZHANG D X, LUH P B, FAN J Q, et al. Chiller plant operation optimization with minimum up/down time constraints [J]. IEEE Robotics and Automation Letters, 2018, 3(1): 9-15.
[6] HU J, JIANG M, ZHANG Q. Joint optimization of UAV position, time slot allocation, and computation task partition in many user aerial mobile-edge computing systems [J]. IEEE Transactions on Vehicular Technology, 2019, 68(7): 7231-7235.
[7] ZHANG P, ZHOU M. Dynamic cloud task scheduling based on a two-stage strategy [J]. IEEE Transactions on Automation Science and Engineering, 2018, 15(2): 772-783.
[8] AKBAR N, YAN S, YANG N, et al. Location-aware pilot allocation in many-cell many-user massive mimo networks [J]. IEEE Transactions on Vehicular Technology, 2018, 67(8): 7774-7778.
[9] LI W, BAI Q, ZHANG M. A many-agent system for modelling preference-based complex influence diffusion in social networks [J]. The Computer Journal, 2019, 62(3): 430-447.
[10] DU Y, XU C, TAO D. Matrix factorization for collaborative budget allocation [J]. IEEE Trans. on Automation Science & Engineering, 2018, 15(4): 1471-1482.
[11] 刘冬宁, 刘统武, 宋静静, 等. 面向基站代维人员分工协作优化的多重指派研究[J]. 广东工业大学学报, 2018, 35(6): 69-76.
LIU D N, LIU T W, SONG J J, et al. Multiple assignment in task allocation of communication base stations [J]. Journal of Guangdong University of Technology, 2018, 35(6): 69-76.
[12] ZHU H, LIU D, ZHANG S, et al. Solving the group many-role assignment problem by improving the ILOG approach [J]. IEEE Transactions on Systems Man & Cybernetics Systems, 2017, 47(12): 3418-3424.
[13] ZHU H. Role-based collaboration and the E-CARGO: revisiting the developments of the last decade [J]. IEEE Systems, Man, and Cybernetics Magazine, 2015, 1(3): 27-35.
[14] ZHU H, ZHOU M C. Role-based collaboration and its kernel mechanisms [J]. IEEE Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2006, 36(4): 578-589.
[15] ZHU H, LIU D, ZHANG S, 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.
[16] ZHU H. Avoiding conflicts by group role assignment [J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2016, 46(4): 535-547.
[17] LIU D, HUANG B, ZHU H. Solving the tree-structured task allocation problem via group many-role assignment [J]. IEEE Transactions on Automation Science and Engineering, 2020, 17(1): 41-55.
[18] 刘冬宁, 武小亮, 卢明健, 等. 广告关键字群组角色组合投资预测研究[J]. 广东工业大学学报, 2018, 35(3): 54-60.
LIU D N, WU X L, LU M J, et al. Bidding prediction of advertisement keywords via group role combination [J]. Journal of Guangdong University of Technology, 2018, 35(3): 54-60.
[19] IBM. ILOG CPLEX Optimization Studio[EB/OL]. (2018-06-08) [2020-11-15]. http://www01.ibm.com/software/integration/optimization/cplex-optimization-studio/.
[1] 张巍, 仝茹, 吴诗珏, 王子奇, 滕少华. 基于KD45闭包的群组角色指派研究[J]. 广东工业大学学报, 2021, 38(04): 26-34.
[2] 刘冬宁, 刘统武, 宋静静, 侯艳. 面向基站代维人员分工协作优化的多重指派研究[J]. 广东工业大学学报, 2018, 35(06): 69-76.
[3] 张巍, 张思勤, 宋静静, 滕少华, 刘艳. 基于E-CARGO的在线社区多对多好友推荐机制研究[J]. 广东工业大学学报, 2017, 34(03): 36-42.
[4] 王昌元； 李代平； . PVM并行平台上的负载均衡[J]. 广东工业大学学报, 2005, 22(4): 53-57.
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
本系统由北京玛格泰克科技发展有限公司设计开发