Solvability of κ--track assignment problem:a graph approach
YUE Ju-mei
CHEN Zeng-qiang
YAN Yong-yi
JIN Xin
Abstract：The theory of graph and a new mathematical analysis tool, semi-tensor product (STP) of matrices are applied to consider the solvability conditions of κ-track assignment problem by investigating the necessary and sufficient conditions of κ-internally stable sets of graphs (κ-ISS). By defining characteristic vectors for vertex subsets of graphs and using the STP, several new necessary and sufficient conditions of κ-ISS are obtained, based on which two algorithms able to find all the κ-ISSs of a graph are established. The results obtained are further applied to the κ-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.
Keywords：κ-track assignmentκ-internally stable setsolvabilitygraph methodsemi-tensor product of matrices
Publication Date：2017-01-01
Online Publishing Date：2025-08-15(First online date of this platform, not the publication date of the document)
Pages：10( 457-466 )