I've an issue stated as follows:
We have 10000 jobs to do, each with some length $l_i$ and weight (importance) $w_i$. Our goal is to arrange the schedule of doing these jobs (in other words, the order of doing jobs) in such way that minimizes the weighted sum of completion times
For this, I'm using the ratio greedy algorithm, that is ratio weight/length to order the jobs, and it is working fine. But now I've to do its correctness proof and I'm stuck with it.
The strategy to prove your ratio greedy algorithm is what I called "unimprovable solution by exchange of elements".
Instead of proving that an algorithm produces the optimal solution, this strategy require you to show that every optimal solution that cannot be improved by an exchange of two or more elements must be or must be equivalent to the solution produced by that algorithm.
Firstly, there must be at least one optimal solution in this scheduling problem. You may want to take a moment to verify that this is indeed true.
Now suppose $OPT$ is an optimal solution. Let us analyze two adjacent jobs in $OPT$. Note that we can switch these two adjacent jobs without changing the contribution of other jobs to the weighted sum of completion times, since the switch does not change the completion times of other jobs. How should these two jobs be arranged so that the total contribution of these two jobs to the weight sum of completion times might be smaller? Now it is time to show the power of arithmetic using unknowns. You will be able to conclude that, the job whose weight/length ratio is bigger must be scheduled earlier than the other job. Assuming the ratio weight/length of each job is distinct, you can then deduce that $OPT$ must schedule all jobs by the descending order of their weight/length ratio; otherwise you will find two adjacent jobs in ascending order of their weight/length ratio. Well, the only scheduling that schedules all jobs by the descending order of their weight/length ratio is produced by your greedy algorithm!
I will let you fill the detail of a complete rigorous proof, which should mention why there should no idle time between two adjacent jobs and which should deal with the case when there are jobs of the same weight/length ratio.
