Question

Consider a job scheduling problem with 4 jobs j1, j2, j3, j4 and with corresponding deadlines: ( d1, d2, d3, d4) = (4, 2, 4, 2). Find out the feasible schedule without violating any job schedule?

Answer 1

Answer: The feasible schedules without violating any job schedule would be:

1. j2, j4, j1, j3
2. j2, j4, j3, j1
3. j4, j2, j1, j3
4. j4, j2, j3, j1

• We need to finish all the jobs within their respective deadlines.
• Since the deadline for both j2 and j4 are 2, we can schedule anyone of them first, and the other next.
• For the remaining jobs j1 and j3, the deadline is 4.
• So, after scheduling j2 and j4, we can schedule j1 / j3 next.
• If you choose j1 in the last step, then schedule j3 at last. Instead, if you choose j3 in the last step, then step j1 at last.

Thus all these 4 schedules are feasible.