THIS IS OUR GREEDY APPROACH

SOME SET OF JOB IS ASSOCIATED WITH PROFIT

JOBS J1 J2 J3 J4 J5
PROFIT 50 15 10 25 45
DEADLINE 2 1 2 1 3

ASSUMPTION :

  1. THIS IS SINGLE PROCESSOR OR UNIPROCESSOR BASED SYSTEM
  2. NON PREAMPTIVE SCHEDULING
  3. 1 UNIT FOR EACH JOB AND THAT ONE UNIT CAN BE IN TERMS OF ONE DAY, WEEK, MONTH OR YEAR

BURST TIME IS ACTUAL COMPLETION TIME

SOLUTION ARRANGE THE PROFIT IN DESC ORDER

JOBS J1 J5 J4 J2 J3
PROFIT 50 45 25 15 10
DEADLINE 2 3 1 1 2

GANTT CHART
25 50 45
0-1 1-2 2-3

Q.

1000182784.heic

J3 J9 J7 J2 J4 J5 J8 J1 J6

J2 J7 J9 J5 J3 J1 J8
20 23 25 18 30 15 16
0-1 1-2 2-3 3-4 4-5 5-6 6-7

ALGORITHM

STEP 1 : SORT ALL JOBS IN DECREASING ORDER OF PROFIT STEP 2: ITTERATE ON JOBS IN DECREASING ORDER OF PROFIT FOR EACH JOB DO THE FOLLOWING

FIND TIME SLOT i SUCH THAT SLOT IS EMPTY THAT IS a[ i ]= null AND i IS LESS THAN DEADLINE AND i SHOULD BE MAXIMUM

STEP 3 : PUT THE JOB IN THIS SLOT AND MARK THIS SLOT AS FILLED