Algorithms for semi on-line multiprocessor scheduling problems

In the classical multiprocessor scheduling problems, it is assumed that the problems are considered in off-line or on-line enviromnent. But in practice, problems are often not really off-line or on-line but somehow in between. This means that, with respect to the on-line problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi on-line ones. The authors studied two semi on-line multiprocessor scheduling problems, in which, the total processing time of all tasks is known in advance, or all processing times lie in a given interval. They proposed approximation algorithms for minimizing the makespan and analyzed their performance guarantee. The algorithms improve the known results for 3 or more processor cases in the literature.     

严格第k最小支撑树问题

提出了严格第 k最小树的概念 .利用定长支撑树问题的复杂性 ,证明了求支撑树的长度分布L( G)问题是 NP-C的 ,从而证明了严格第 k最小支撑树问题也是 NP-C的 .对于 k=2的情况 ,给出了一个多项式时间算法 ,其时间复杂性为 $O( | EX| n^2 )$ ,其中 EX是正交换的集合 ,n是顶点数.     

最短路网络及应用

首先提出了最短路网络的概念 ,然后给出了一个时间复杂性为 首先提出了最短路网络的概念 ,然后给出了一个时间复杂性为 0 ( n2 )的构造最短路网络的算法 .最后研究了最短路网络在最小成本最短路 ,最短路计数和最短路树中的应用     

最短路问题的字典序多目标算法

本文研究了双目标最短路问题，给出了字典序最优解的定义，最后给出了一个时间复杂性为Ｏ（ｎ＾２）的字典序双目标算法。