Scheduling independent jobs on nonuniform, unequal processors
研究了在多个不等处理器上调度独立作业以最小化总延迟的问题，提出了一个高效、快速且易于实现的启发式算法，并通过实验验证了其有效性。
Abstract The problem of scheduling n independent jobs on a single processor to minimize the total tardiness of the assignment has attracted much attention. Solution algorithms, both exact and approximate, have been reported, but no polynomial time exact algorithm has yet been found, nor has the problem been proven NP‐complete. In this paper we consider the more general case of scheduling n independent jobs on m unequal processors to minimize total tardiness. Since this problem is more complex than the corresponding single‐processor problem, no polynomial‐time algorithm is in sight. For problems of this nature, approximate algorithms may be more valuable than exact algorithms in terms of applications. A heuristic algorithm is developed to solve the multiple‐processor problem. Computational experiments show that the heuristic algorithm is efficient, fast, and easy to implement.