Rescheduling to minimize makespan on a changing number of identical processors
Rescheduling to minimize makespan on a changing number of identical processors
复制标题
重新调度以最大程度地减少数量不断变化的相同处理器的完工时间
DOI：
10.1002/nav.3800330414
复制
发表时间：
1986
期刊：
影响因子：
--
通讯作者：
C. Tovey
中科院分区：
文献类型：
--
作者：
C. Tovey
我们考虑当 m 的值发生变化时重新调度 n 个作业以最小化 m 个并行相同处理器上的完工时间的问题。我们证明这个问题一般来说是 NP 困难的。如果列表调度对于所有 m = 1, …,n 都是最优的，则称该列表调度是完全最优的。当 n 小于 6 时，总是存在完全最优的调度，但是当 n ≥ 6 时，这可能会失败。我们证明了精确解的鲁棒性不如最大处理时间优先（LPT）启发式，并讨论了对多项式逼近方案和分层规划模型的影响。
We consider the problem of rescheduling n jobs to minimize the makespan on m parallel identical processors when m changes value. We show this problem to be NP-hard in general. Call a list schedule totally optimal if it is optimal for all m = 1, …,n. When n is less than 6, there always exists a totally optimal schedule, but for n ≥ 6 this can fail. We show that an exact solution is less robust than the largest processing time first (LPT) heuristic and discuss implications for polynomial approximation schemes and hierarchical planning models.