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

Solvability of k--track assignment problem: a graph approach

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

英文关键词  k--track assignment  k--internally stable set  solvability  graph method  semi-tensor product of matrices

中文摘要

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

英文摘要

      The theory of graph and a new mathematical analysis tool, semi-tensor product (STP) of matrices are applied to consider the solvability conditions of k--track assignment problem by investigating the necessary and sufficient conditions of k--internally stable sets of graphs (k--ISS). By defining characteristic vectors for vertex subsets of graphs and using the STP, several new necessary and sufficient conditions of k--ISS are obtained, based on which two algorithms able to find all the k--ISSs of a graph are established. The results obtained are further applied to the k--track assignment problem, and two necessary and sufficient conditions of the solvability of the problem are proposed; also some interesting phenomena such as completely optimal schedules are discovered by the new method.