8,714 views

Consider a job scheduling problem with 4 jobs $J_1, J_2, J_3$ and $J_4$ with corresponding deadlines: $(d_1, d_2, d_3, d_4) = (4, 2, 4, 2)$. Which of the following is not a feasible schedule without violating any job schedule?

1. $J_2, J_4, J_1, J_3$
2. $J_4, J_1, J_2, J_3$
3. $J_4, J_2, J_1, J_3$
4. $J_4, J_2, J_3, J_1$

### Subscribe to GO Classes for GATE CSE 2022

TO OPTIMIZE AND TO GET A FEASIBLE SOLUTION WE HAVE TO FINISH ALL THE JOBS WITH IN THEIR DEAD LINE.

SINCE THE DEADLINE OF J2 AND J4 ARE 2.SO THEY MUST BE COMPLETED BY 2.SO WE CAN SCHEDULE ANY ONE

THAT IS J2 OR J4..

IN OPTION C,D J4 IS SCHEDULED FIRST AND THEN J2 AND

IN OPTION A, FIRST J2 THEN J4             SO WE CAN ABLE TO SCHEDULE OTHER 2 JOBS

NOW CONSIDER OPTION B

J4 IS SCHEDULED AND NEED TO BE COMPLETED ....BY 2  ---NO PROBLEM

J1 IS SCHEDULED AND NEED TO BE COMPLETED ....BY 4     --NO PROBLEM

BUT NOW AS J2 SHOULD COME BEFORE TIME 2..BUT WE SCHEDULED J1....SO J2 CANT BE SCHEDULED

by
21 55 133

Very good explanation.
nice explanation
edited
What does it mean that J2 and J4 should be completed by 2?

If we assign J4 at time 1 and assign J2 at time 2 than how will both of them be completed by time 2?
its assuming run time is 1 unit only .. start from 0 --1--2--3--4 now schedule them

Option B

 J4 J1

1             2              3           4

now we can’t scheduled J2 bcz deadline up to 2 already full

Option A: 2,2,4,4. No problem.

Option B: 2,4,2,4. The third job in this sequence had to be completed under 2 time units. But it took 3 time units. This isn't an optimal solution, hence the answer.

Option C: 2,2,4,4. No problem.

Option D: 2,2,4,4. No problem.

by
4 8 39

1
6,942 views