证明一台共享机和一台具有无限并行能力的调度算法
Prove scheduling algorithm for one shared machine and one with infinite parallel capacity
这里有个问题：
所有碎片p_i需要一台共享机器处理，然后碎片由其他机器精炼一次。共享机器一次只能加工一件。精炼机一次可以处理无限量的碎片。在共享机中处理需要t_i的时间，在细化中处理需要r_i的时间。我的工作是找到一种算法，它可以最大限度地减少总完成时间并证明正确且 运行 时间。
我认为解决方案是按细化时间降序对片段进行排序。这需要 n*log(n)。我如何证明正确性呢？我只知道我们应该先做那些大的细化，这样细化就可以在共享机器上处理其他部分的同时进行。
归纳。让 H(k) 假设存在一个最优调度，其中最多有 n(n−1)/2 − k 个关于你的排序顺序的倒置。 H(n(n−1)/2) 表示算法的正确性。 H(0) 是显而易见的。为了证明 H(k) 蕴含 H(k+1)，您采用至少有一次反转的最优解，并论证您可以反转两个连续的乱序部分的顺序（减少反转的次数）一个）而不伤害 objective.
由于所有部分都必须首先由共享机器处理，因此对于共享机器处理的解决方案的组件，最佳解决方案总是具有 t_is 的连续顺序的某种排列。
t_a + t_b ... + t_z
无论选择何种排列，上述总和都是常数。
然而，每个 r_i 都由前面的 t_i 前缀增加，这导致平行和。
t_a + r_a
.
.
t_a + t_b + r_b
.
.
t_a + t_b + t_c + r_c
.
.
...etc.
如上所述，无论选择何种排列，前缀和 T 都是常数。由于每个前缀都会延迟 r_is 的开始，我们知道每个 r_i 必须具有不同的开始时间，如上所示。让我们尝试按 r_is:
的降序交换两个片段
Before:
t_a + r_a
.
.
t_a + t_b + r_b
After:
t_b + r_b
.
.
t_b + t_a + r_a
我们让第二个序列更长了！我们知道现在 r_a 必须 在 r_b 之后开始，但是由于 r_a ≥ r_b，我们使总和更大。
这里有个问题： 所有碎片p_i需要一台共享机器处理，然后碎片由其他机器精炼一次。共享机器一次只能加工一件。精炼机一次可以处理无限量的碎片。在共享机中处理需要t_i的时间，在细化中处理需要r_i的时间。我的工作是找到一种算法，它可以最大限度地减少总完成时间并证明正确且 运行 时间。
我认为解决方案是按细化时间降序对片段进行排序。这需要 n*log(n)。我如何证明正确性呢？我只知道我们应该先做那些大的细化，这样细化就可以在共享机器上处理其他部分的同时进行。
归纳。让 H(k) 假设存在一个最优调度，其中最多有 n(n−1)/2 − k 个关于你的排序顺序的倒置。 H(n(n−1)/2) 表示算法的正确性。 H(0) 是显而易见的。为了证明 H(k) 蕴含 H(k+1)，您采用至少有一次反转的最优解，并论证您可以反转两个连续的乱序部分的顺序（减少反转的次数）一个）而不伤害 objective.
由于所有部分都必须首先由共享机器处理，因此对于共享机器处理的解决方案的组件，最佳解决方案总是具有 t_is 的连续顺序的某种排列。
t_a + t_b ... + t_z
无论选择何种排列，上述总和都是常数。
然而，每个 r_i 都由前面的 t_i 前缀增加，这导致平行和。
t_a + r_a
.
.
t_a + t_b + r_b
.
.
t_a + t_b + t_c + r_c
.
.
...etc.
如上所述，无论选择何种排列，前缀和 T 都是常数。由于每个前缀都会延迟 r_is 的开始，我们知道每个 r_i 必须具有不同的开始时间，如上所示。让我们尝试按 r_is:
Before:
t_a + r_a
.
.
t_a + t_b + r_b
After:
t_b + r_b
.
.
t_b + t_a + r_a
我们让第二个序列更长了！我们知道现在 r_a 必须 在 r_b 之后开始，但是由于 r_a ≥ r_b，我们使总和更大。