a scheduling application

1. Problem Scenario :

    - One shared resource (e.g., a processor).

    - Many "jobs" to do (e.g., processes).

    Assume: Each job has a:

    - weight wj ("priority")

    - length lj

    Question: In what order should we sequence the jobs?

 

2.  Completion Times : The completion time Cj of job j = Sum of job lengths up to and including j.

 

3.  Goal: Minimize the weighted sum of completion times: min{ Sum(j=1 to n) {wjCj} }

 

4.  Two special case : 

    a)  With equal lengths, schedule larger or smaller-weight jobs earlier? -- larger

    b)  With equal weights, schedule shorter or longer jobs earlier? -- shorter

 

5.  Idea: Assign "scores" to jobs that are:

    a)  inscreasing in weight

    b)  decreasing in length

 

6.  Two guess of the "score" function:

    a)  wj-lj

    b)  wj/lj

 

7.  To distinguish among several greedy algorithm : Find example where the several algorithms produce different outputs. Only the one that has the best output can be the optimal algorithm.

    a)  l1 = 5, w1 = 3 (longer ratio)

    b)  l1 = 2, w1 = 1 (larger difference)

 

8.  Proof of correctness of Algorithm #2 (use wj/lj as the score) : Fix arbitrary input of n jobs. Let G = greedy schedule, G* = optimal schedule. Will produce schedule even better than G*, contradicting purported optimality of G*.

      Assume : All wj/lj is different

      Renaming jobs: w1/l1 > w2/l2>...>wn/ln ( so greedy schedule is 1, 2, 3, ...n)

      If G* <> G , then there are consecutive jobs i , j with i > j .

      Exchange argument: Suppose we exchange order of i&j in G* , then the weighed completion time of other jobs except i,j are not changed. And :

           a)  i's weighed completion time goes up by wi*lj

           b)  j's weighed completion time goes down by wj * li 

       So the sum of weighed completion time of all the jobs goes up by wi*lj - wj*li, while because i > j , then wj/lj > wi/li  ==> wj*li > wi*lj , so the total value goes down ==> G* is not optimal.

 

9.  Claim: Algorithm #2 (order jobs in nonincreasing order of ratio wj/lj ) is always correct. (handling tie)

    Fix arbitrary input of n jobs. Let G = greedy schedule, let G* = any other schedule. Will show G at least as good as G* ==> Implies that greedy schedule is optimal.

    Proof. similar as proof of no ties scenario. Exchange Argument: exchange consecutive jobs i , j  in G*, where i > j, if G <> G*, then after exchange, it will be no worse than G* because wi/li <= wj/lj ==> wi*lj <= wj*li ==> the total sum of weighed completion time will not increase. So after exchange the schedule is at least as good as G*. Continue to exchange ( at most C(n,2) such exchanges) until the schule is same as greedy schedule G ==> G is at least as good as any schedule G*