algorithm - 在异构机器上调度异构任务

Question

我们有 n 个工作和 m 台机器。每个作业 i 都有一个发布时间 r[i]。在机器 j 上处理作业 i 需要 p[i][j] 时间。对于一项工作 k，|{p[i][j] | i == k}| <= c，其中 c << m。我们将作业 i 的延迟定义为 f[i] - r[i]，其中 f[i] 是作业 i 完成的时间。系统不是抢占式的，即当一个作业在某台机器上启动时，它在完成之前不能被中断。目标是提供一种调度算法，使所有作业的延迟总和最小化。任何的想法？

Answer 1

这是3 分区问题的简化。

令 S = {x ₁ , ..., x _3m } 是 3 分区的实例，使得对于每个 i，B/4 < x _i < B/2，其中 B = ∑x _i /m 是目标总和。

假设有 m台相同的机器。在时间 0，发布 3m 个长度为 x ₁ , ..., x _3m的作业。每次 B, B + 1, ..., B + 4mB - 1，释放 m 个长度为 1 的作业，总共 4m ² B 个作业。

当且仅当初始作业的制造跨度小于或等于 B 时，3 分区的实例才有解。如果有解，则初始作业对目标的贡献最多为 3mB。其他工作的贡献是 4m ² B.

如果制造期比 B 长，那么一连串 4mB 的作业至少会延迟一个单元，为目标贡献 4mB。因此，如果 3 分区问题是可解决的，则目标最多为 3mB + 4m ² B，如果 3 分区问题不可解决，则目标至少为 4mB + 4m ² B。