Title Job Scheduling1 Mathematical Concepts Physics & Mathematics Mathematics Mathematical Analysis 431.1 KB 36
##### Document Text Contents
Page 18

17

GREEDY ALGORITHM TO OBTAIN AN

OPTIMAL SOLUTION (Contd..)

• If t < t1, we may interchange the job scheduled in [t1

t1+1] in SI with i; if no job is scheduled in [t
1 t1+1] in

SI then i is moved to that interval.

• With this, i will be scheduled at the same time in S I
and SJ.

• The resulting schedule is also feasible.

• If t1 < t, then a similar transformation may be made in
S j.

• In this way, we can obtain schedules SI
1 and SJ

1 with
the property that all the jobs common to I and J are
scheduled at the same time.

Page 19

18

GREEDY ALGORITHM TO OBTAIN AN

OPTIMAL SOLUTION (Contd..)

• Consider the interval [Ta Ta+1] in SI
1 in which the

job a is scheduled.

• Let b be the job scheduled in S j
1 in this interval.

• As a is the highest profit job, pa  p b.

• Scheduling job a  from ta to ta+1 in S j
1 and

discarding job b gives us a feasible schedule for
job set J1 = J-{b} U {a}. Clearly J1  has a profit
value no less than that of J and differs from in one
less job than does J.