Greedy algorithms for Job Scheduling

In this programming problem and the next you'll code up the greedy algorithms from lecture for minimizing the weighted sum of completion times..This file describes a set of jobs with positive and integral weights and lengths. It has the format

[number_of_jobs]
[job_1_weight] [job_1_length]
[job_2_weight] [job_2_length]
...
For example, the third line of the file is "74 59", indicating that the second job has weight 74 and length 59. You should NOT assume that edge weights or lengths are distinct.

Your task in this problem is to run the greedy algorithm that schedules jobs in decreasing order of the difference (weight - length). This algorithm is not always optimal. IMPORTANT: if two jobs have equal difference (weight - length), you should schedule the job with higher weight first. Beware: if you break ties in a different way, you are likely to get the wrong answer. You should report the sum of weighted completion times of the resulting schedule --- a positive integer --- in the box below.

Sol:

we will compute weighted sum with the following formula :

And our goal is to minimize that function:

our task in this problem is to run the greedy algorithm that schedules jobs in decreasing order of the difference (weight - length) . In code this implemented in the following way:

Algo is straight forward, we make  a job with  length, weight and  difference (weight - length). then we keep all the jobs in a list and sorted them in non- decreasing order. If two jobs have same difference we break the tie by choosing a job with higher weight. This tie breaking is achieved by implementing Comparable in Job class.

 public int compareTo(Object o) {  
           // TODO Auto-generated method stub  
     Job          jobOther=(Job)o;  
            int delta= jobOther.getDifference().intValue()-this.difference.intValue() ;  
             if(delta==0){  
                  delta=this.weight.intValue()-jobOther.getWeight().intValue();  
                  return delta;  
             }  
           return delta;  
      }  

   
Source code of above problem is available in the following link along with input file that contains 10,000 jobs with different weights and lengths.

SourceCode

Note:

I am  prone to  typo; please report them and I will try to update the posts accordingly.