Prove scheduling algorithm for one shared machine and one with infinite parallel capacity

Question

Here is a problem: All pieces p_i need to be processed by one shared machine and then the pieces get refined once by other machines. The shared machine can only process one piece at a time. The refine machine(s) can process unlimited pieces at a time. It takes a time of t_i for processing in the shared machine and r_i for processing in the refinement. My job is to find an algorithm that minimizes total completion time and prove correct and running time.

I think the solution is to sort the pieces in descending refinement time order. This would take n*log(n). How do I prove correctness though? I just know that we should do those with large refinement first so that refinement can happen while the other pieces are processed in the shared machine.

Answer 1

Inductively. Let H(k) be the hypothesis that there exists an optimal schedule with at most n(n−1)/2 − k inversions with respect to your sorted order. H(n(n−1)/2) implies the correctness of your algorithm. H(0) is obvious. To show that H(k) implies H(k+1), you take an optimal solution with at least one inversion and argue that you can reverse the order of two consecutive out-of-sorted-order pieces (decreasing the number of inversions by one) without harming the objective.

Answer 2

Since all pieces must first be processed by the shared machine, the optimal solution invariably has some permutation of a continuous order of t_is for the component of the solution processed by the shared machine.

t_a + t_b ... + t_z

The above sum is constant regardless of the chosen permutation.

Each r_i, however, is augmented by the prefix of t_is preceeding it, which leads to parallel sums.

t_a + r_a
       .
       .
t_a + t_b + r_b
             .
             .
t_a + t_b + t_c + r_c
                   .
                   .
...etc.

As discussed above, the prefix sum, T, is constant regardless of the chosen permutation. Since each prefix delays the start of r_is, we know that each r_i must have a different starting time as illustrated above. Lets try switching two pieces in a descending sequence of r_is:

Before:

t_a + r_a
       .
       .
t_a + t_b + r_b

After:

t_b + r_b
       .
       .
t_b + t_a + r_a

we've made the second sequence longer! We know that now r_a must start after r_b, but since r_a ≥ r_b, we've made the overall sum greater.