论文部分内容阅读
一般形式下的进程调度问题是NP完全的,一般采用多项式时间复杂性的启发式算法求其次优解。我们提出一种调度问题。其求最优解的复杂性也是NP完全的。我们先将问题化成图论问题。然后提出一种有效的分布式算法求其次优解。最后,基于分析和模拟,我们对该算法的行为进行了讨论。
The general form of the process scheduling problem is NP complete, the general use of the polynomial complexity of the heuristic algorithm to find the next best solution. We propose a scheduling problem. The complexity of finding the optimal solution is NP complete. We first turn the problem into a graph theory. Then an efficient distributed algorithm is proposed to find the next best solution. Finally, based on analysis and simulation, we discuss the behavior of this algorithm.