# Correctness proof for greedy algorithm based on ratio

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.

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!