Single machine job scheduling to minimize weighted sum of completion time

Question

Given $n$ jobs, schedule them such that the weighted sum is minimum.

weighted minimum sum S for the schedule $\sigma = \{ J_1, J_2, ... J_n \}$ is given by :

$S = \sum_{1\leqq i \leqq n} w_i C_i$ where $C_i\ = \sum_{1\leqq j \leqq i} t_j$ and $w_i$ is the weight of job $J_i$, $t_i$ is the time $J_i$ takes to complete.

I think the solution is to schedule the jobs in shortest weighted processing time i.e. to arrange them in the increasing order of $ t_i/w_i $.

But how to prove this.

Answer 1

Hint: Let $\sigma$ be the optimal schedule. Suppose that jobs $k$ and $k+1$ are switched. How is the cost affected? What does the optimality of $\sigma$ tell us about $w_k,w_{k+1},t_k,t_{k+1}$?