deadline.pptx

Job Sequencing deadline

1. Job Sequencing with Deadlines Dr.P.Anusha Assistant Professor Department of Software Engineering Periyar Maniammai Institute of Science & Technology

2. Job Sequencing with Deadlines In job sequencing problem ,the objective is to find a sequence of jobs which is completed with their deadlines and give maximum profit. In this problem we have n jobs j1,j2………. jn. Each job has an associated with deadline d1,d2…….dn. And profit p1,p2…. pn .

3. Job Sequencing with Deadlines Profit will be only earned or awarded if the job is completed on or before the deadline. we assume that each job has takes unit of time to complete. The objective is to earn max profit, when only one job can be scheduled or processed at any given time.

4. Job Sequencing with Deadlines Consider the following 5 jobs and associated deadline, profit: INDEX 1 2 3 4 5 JOB j1 j2 j3 j4 j5 DEADLINE 2 1 3 2 1 PROFIT 60 100 20 40 20

5. Job Sequencing with Deadlines Sort the jobs according to their profit in descending order: INDEX 1 2 3 4 5 JOB j2 j1 j4 j3 j5 DEADLINE 1 2 2 3 1 PROFIT 100 60 40 20 20

6. Job Sequencing with Deadlines Jobs j3 and j5 are having profit 20. so we placed j3 as first as it come before j5. FIND THE MAX DEADLINE VALUE: Looking at the jobs, we can say the max deadline value is 3. Dmax =3; So we will have 3 slots to keep track of free the time slot

7. Job Sequencing with Deadlines Set the timeslot to empty Total number of jobs=5; So n=5; And Dmax =3 TIME SLOT 1 2 3 STATUS empty empty empty

8. We look at job j2, it has a deadline one. This means we have to complete job j2 in timeslot1. if we want to earn the profit. We look at job j1, it has a deadline two. This means we have to complete job j1 before timeslot 2 in order to earn profit. We look at job j3, it has a deadline three. This means we have to complete job j3 before timeslot 3 in order to earn profit.

9. OBJECTIVE: To select jobs that will give us higher profit i =1; K=min( dmax,deadline (x)), Or k=min(3,deadline(1)), Or k=min(3,1), Or k=1; Is k>=1; 1>=1 yes Check time slot(k)==empty; Timeslot(1)==empty? Yes, Fill the timeslot1 with j2.

10. i =2; K=min( dmax,deadline (x)), Or k=min(3,deadline(2)), Or k=min(3,2), Or k=2; i >k>=1 2>=1 Yes Check time slot(k)==empty; Timeslot(2)==empty? Yes, Fill the timeslot2 with j1.

11. i =3; K=min( dmax,deadline (x)), Or k=min(3,deadline(2)), Or k=min(3,2), Or k=2; i >k>=1 2>=1 Yes Check time slot(k)==empty; Timeslot(2)==empty? No Reduce K by 1 So i =3 K=1 1>k>=1 1>=1 yes

12. Check time slot(k)==empty; Timeslot(1)==empty? No Reduce K by 1 So i =3 K=0 1>k>=1 0>k=1; No So we will move to next job

13. i =4; K=min( dmax,deadline (x)), Or k=min(3,deadline(3)), Or k=min(3,3), Or k=3; i >k>=1 3 >=1 Yes Check time slot(k)==empty; Timeslot(3)==empty? Yes

14. Fill the time slot 3 with j3. now time slot has filled with jobs so we have to stop here. Required job sequence: J2 → j1 → j3. Then Maximum profit: 100+60+20=180 .

15. Thank you