Let us look at the entire question: "Consider the scheduling problem wherein you are given a single resource and a set of requests having deadlines. A request is said to be late be late if it misses the deadline, Your goal is to minimize the maximum lateness. With respect to a schedule S, idle time is defined as the time during which the resource is idle, in between two requests. S is said to have an inversion when request i has been scheduled before j and d(i) > d(j), where d(i) and d(j) are the deadlines of the requests i and j respectively. Argue that all schedules with no idle time and no inversions have the same maximum lateness."
To minimize maximum lateness, we use the EDD Rule. The Earliest Due Date (EDD) rule is a scheduling heuristic used to minimize the maximum lateness in a set of jobs. The rule is straightforward: it schedules jobs in order of their due dates, starting with the job that has the earliest due date and proceeding in ascending order of due dates.
Consider a scenario with three jobs:
Job A: deadline = 5, Processing Time=2
Job B: deadline = 3, Processing Time=3
Job C: deadline = 6, Processing Time=1
According to EDD rule, the correct order should be B, A, C. Here, scheduling A before B would be an inversion since it leads to higher maximum lateness compared to the optimal order of B, A, C. An inversion occurs when a job that is scheduled earlier should ideally be scheduled later to minimize maximum lateness. It often means a job with a later due date is scheduled before a job with an earlier due date, contrary to the optimal ordering.
Time during which the resource is idle between two requests. A schedule with no idle time means the resource is continuously processing requests without any gaps.
Now, let's consider two schedules S1 and S2 that have no idle time and no inversions. In both schedules, requests are processed continuously, and they are ordered by non-decreasing deadlines.
Since there are no inversions, both schedules will have the same ordering of requests. Since both schedules are continuously working and following the same order of deadlines, they effectively do the same thing. They start with the task that has the earliest deadline and move on to the next, always picking the next task that is due the soonest. Because they follow these same rules, the order in which tasks are completed will be the same in both schedules. As a result, the latest any task finishes relative to its deadline (the maximum lateness) will be the same in both schedules.