You are given a set of n jobs, where each job j is associated with a size s(how much time it takes to process the job) and a weight w(how important the job is). Suppose you have only one machine that can process one unit of jobs per time slot. Assume all jobs are given at time t = 0 and are to be processed one by one using this machine. Let C > to be the time that job j is completed. The goal is to find a schedule (of all the jobs) that minimizes the weighted completion time, i.Σ(j=1 to n) wj * Cj
- Approach 1: Process Jobs according to the highest weight first
- Approach 2: Process jobs in ascending order of their size
- Approach 3: Process jobs in descending order of their density (w/s)
So basically, I need to find out which approach is optimal and why the other 2 wouldn't work. My understanding is as follows:
Hence, my answer is that Approach 2 would be the optimal choice out of the 3 as it focuses on minimizing w*c. Is this answer correct? Is there a better way to prove why approach 2 is the optimal choice in this question?