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.
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.