多机相关任务均衡调度问题的复杂性与新算法

The Complexity and New Algorithm on the Equilibrium Scheduling Problem for Dependent Tasks in Multiprocessors

本文讨论了多处理机系统中的一种相关任务均衡调度问题 ,证明了该问题是 NP完全问题 ,并给出了一个新的启发式算法。该算法克服了现有算法的不足。数值实例和仿真结果表明 。

This paper discusses an equilibrium scheduling problem for dependent tasks in multiprocessors,proves that the scheduling problem is a NP complete problem and presents a new heuristic algorithm to solve the problem.The new algorithm eliminates the drawbacks of existing algorithms.The numerical emulation result given in this paper illustrates that the new algorithm is satisfying.