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

Solvability of k-track assignment problem:a graph approach

将图论及一种新的数学分析工具——矩阵的半张量积(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.