Assume that yo have a set of jobs in which each has only a processing time that you need to minimize the sum of the completion (finish) times. Prove that your schedule is optimal.
The wording throws me off a little, but I think the question is trying to minimize the average waiting time. If so, it's best to sort the jobs in increasing order of processing time. Moving a short job before a long job decreases the waiting time of the short process more than it increases the waiting time of the long process. Please correct me if I'm wrong. If not, how do I go about proving this?
let's say you have N jobs, job k has processing time $t_k$, and is ordered in $M_k^{\text {th}}$ position, the waiting time is $∑t_k(N−M_k)$. Then it's optimal to sort the jobs in increasing order of $t$. Since for an arbitrary assignment $(M_1,M_2...M_k)$, if $\exists M_i>M_j$ while $t_i<t_j$, we can always reduce the waiting time by exchange the order of job $i$ and $j$ as $t_i(N-M_j)+t_j(N-M_i)<t_i(N-M_i)+t_j(N-M_j)$