连续时空约束多对多群组角色指派研究

作     者：郑楚楚 

作者单位：广东工业大学 

学位级别：硕士

导师姓名：刘冬宁

授予年度：2021年

学科分类：08[工学] 081104[工学-模式识别与智能系统] 0811[工学-控制科学与工程] 

主      题：任务分配 连续时空约束 多对多指派 群组角色指派 群组角色多对多指派 

摘      要：连续时空约束为任务分配中常见的约束,是工业生产、交通调度、系统设计等领域重要的约束求解问题之一。连续时空约束主要体现在限制执行者连续工作时间和强制性连续空闲时间。在指派过程中,由于任务与执行者之间存在着复杂的时序耦合关系,导致任务分配难度上升,协同效应急剧下降。尤其是在任务的多对多分配过程中,一项任务可由多名执行者协作完成,一名执行者可以执行多项任务,任务集合交织成为高阶二分图,指派拓扑与计算复杂性大幅增加。因此,针对多对多指派,在连续时空约束下拆分、解耦任务,合理分配有限资源,并使得团队收益最大化是一项重要的课题。为了有效的解决连续时空约束下多对多指派中任务集合的高阶形式以及优化求解效率,本文以广州交通法规“四开四停为典型背景,对问题进行了详细地分析和研究,主要内容包括:1)连续时空约束多对多指派问题的建模,本文采用群组角色多对多指派(Group Multirole Assignment,简称GMRA)和E-CARGO模型对问题进行了形式化建模,使用角色和代理抽象化表示任务与执行者之间的关系,并建立了相应的量化指标。2)本文用线性约束组表达了连续时空约束,提出了可行的连续时空约束多对多指派算法,并结合线性约束组的特点采用线性规划工具IBM ILOG CPLEX对模型进行计算。并对充分必要条件和必要条件作形式化证明,依此筛选出无解的案例;3)算法优化与实验验证。为了整体任务的顺利执行,本文采用了传统的迭代法和必要条件法,通过增加代理数量解决连续时空约束多对多指派无解的案例,或提前对连续时空约束多对多指派进行规划,保证指派的顺利进行,并作实验验证。大规模仿真实验结果表明:上述的模型和算法能有效的解决连续时空约束多对多指派问题,并求解连续时空约束下多对多指派问题的效率是秒分级。本文设计的连续时空约束多对多指派的必要条件,能准确无误的筛选出无解案例,并使得改进后的求解方法与原来的方法比较,增加必要条件的实验平均加速比达6826.9%。与此同时,在解决无指派结果的案例时,本文提出的Necessary condition(简称NEC)算法和迭代算法的比较发现,NEC算法增加最少代理的准确率为99.99%,NEC算法的时间复杂度远远小于迭代算法,并且能准确的指出缺少代理数量的角色。决策者使用本文提出的模型和NEC算法可以有效的解决连续时空约束多对多指派问题,必要条件通过筛选出无解案例使得实验的效率提高,并提供了一套合理解决连续时空约束的调度方案,使得交通运输调度总体收益最大化。