algorithm - Muntz-Coffman 算法（调度）

Question

我想知道您究竟是如何计算时间片（2、4、5.5、7、8.5）的。

Answer 1

Muntz-Coffman 基本上是关键路径法。每个作业的优先级是从该作业开始的依赖链的最大持续时间。在每个时间点，正在运行的作业都是具有最高优先级的作业。

初始优先级以反向拓扑顺序以线性时间计算。

K: 1 + max(0) = 1
H: 1 + max(0, K) = 2
I: 2 + max(0, K) = 3
J: 4 + max(0) = 4
E: 3 + max(0, H) = 5
F: 2 + max(0, H, I) = 5
G: 3 + max(0, I, J) = 7
A: 2 + max(0, E, F) = 7
B: 1 + max(0, E, F, G) = 8
C: 1 + max(0, G) = 8
D: 2 + max(0, F, G) = 9

D（2 个单位）是唯一的最大值，因此它自己拥有一台机器。B（1 个单元）和 C（1 个单元）并列，因此它们以 50/50 拆分另一台机器。在t时刻，D的优先级为9-2t，B和C的优先级为8-t。在这三个工作完成之前，它们保持在优先级 7 之上，次高，D 高于 B 和 C，B 和 C 保持并列。

在时间 2，下一个最高的是 A（2 个单位）和 G（3 个单位），它们各自收到自己的机器。2个单位时间后，A完成，G的优先级降为5，与E、F并列。现在E、F、G都被调度为偶数三路拆分，一直持续到时间5.5 G 点结束，其他点现在处于优先级 4，与 J 并列。

三向工作一直持续到时间 7，F 完成，E 和 J 的优先级滑到 3。现在 E、I 和 J 被安排到 E 完成并且 I 和 J 的优先级下降到 2，此时（时间 8.5) H、I 和 J 已安排好。H 和 I 完成，J 在 1，此时（时间 10）J 和 K 被安排为 50/50，直到时间 11 结束。