Question

Consider the following scheduling problem. There are n jobs and a single machine. Each job has a length ℓi and a weight wi . The weight wi represents the importance of job i.

a) Let fi be the finishing time of job i. Design a greedy algorithm to minimize the weighted sum of the completion times ∑n i=1 wifi . Your algorithm should run in time O(n log n) and output an ordering of the jobs.

b) Prove the correctness of your algorithm and analyze its running time.

Example: Suppose there are two jobs: t1 = 1, w1 = 2, t2 = 3, and w2 = 1. Doing job 1 first would give f1 = 1, f2 = 4, and a weighted sum of 2 · 1 + 1 · 4 = 6, which is optimal. Doing job 2 first would yield f1 = 4, f2 = 3, and a larger weighted sum of 2 · 4 + 1 · 3 = 11. (Hint: how does the weighted sum change if we swap two adjacent jobs?)

Answer 1

Solution (a): Algorithm:

Step 1. For each job calculate the ratio, calculate the ratio w_i / l_i i.e., weight per unit length

Step 2. Order all the jobs on the basis of calculated weigth per unit length in descending order and return this order.

Solution (b): Correctness proof -

       Suppose O is an optimal solution which is having weight W. Now let we swap the order of any pair of jobs Ji(=wi/li) and Jj(=wj/lj), then this swapping will result in change of weighted sum from W to W'.This change is only because of two swapped adjacent jobs as the completion time of other remaining jobs will remain same.
 
Now for W' to be smaller than W, it is required that two jobs Ji and Jj must be order in descending order of weight per length order. ---(1)

If the order of Ji and Jj is ascneding, then W'>W and thus O will not be optimal solution. Thus for any two adjacent jobs, argument 1 applies for the solution to be optimal and thus we can conclude that whole order will be descending in order of weight per length ratio.

Running time analysis:- Step 1 requires only one pass over all the given jobs and thus takes O(n), step 2 requires sorting on basis of weight per length and thus takes O(n log n). Thus, as a whole algorithm takes O(n) + O(n log n) = O(n log n) time.