k轨道任务分配问题的可解性条件:图论方法

摘要：

将图论及一种新的数学分析工具–—矩阵的半张量积(semi-tensor product of matrices,STP),作为研究工具,通过研究图的κ内稳定集的充分必要条件,研究了κ轨道任务分配问题的可解性条件.定义了图的顶点子集的特征向量,利用STP方法得到图的κ内稳定集新的若干充分必要条件.基于这些新的充分必要条件,建立了能够搜索出图的所有κ内稳定集的两种算法.进而将上述结果应用到κ轨道任务分配问题,得到了该问题可解性的两个充分必要条件.此外,通过这些充分必要条件,也发现了一些有趣的现象.例如,完全最优方案(completely optimal schedules)的存在.

关键词：κ轨道任务分配、κ内稳定集、可解性、图论方法、矩阵的半张量积

所属期刊栏目：34

分类号：TP273(自动化技术及设备)

资助基金：Key Scientific Research Program of the Higher Education Institutions of Henan Educational Committee15A416005;2015 Science Foundation of Henan University of Science and Technology for Youths2015QN016;National Natural Science Foundation of China61573199;Sub-project of National Key Research and Development Program2016YFD0700103–2

在线出版日期：2017-07-11（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：457-466