Minimizing total completion time in two‐processor task systems with prespecified processor allocations
研究了双处理器系统中预分配处理器的任务调度问题，以最小化总完工时间。可抢占情况可在O(n log n)时间内求解，不可抢占情况被证明是强NP难的，并提出了一个相对误差不超过100%的启发式算法。
We consider the problem of scheduling multiprocessor tasks with prespecified processor allocations to minimize the total completion time. The complexity of both preemptive and nonpreemptive cases of the two-processor problem are studied. We show that the preemptive case is solvable in O(n log n) time. In the nonpreemptive case, we prove that the problem is NP-hard in the strong sense, which answers an open question mentioned in Hoogeveen, van de Velde, and Veltman (1994). An efficient heuristic is also developed for this case. The relative error of this heuristic is at most 100%. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 231–242, 1998