Exchange Argument is a different kind of analysis that we are going to use to prove that our greedy algorithm is optimal. The Problem. Consider one resource that has to accomplish a set of n tasks within an interval of time for each resource. In this case we are going to look at deadlines that require a contiguous time interval for every task/request. All these requests must be assigned nonoverlapping intervals as part of the solution. Despite last problem in section 4.1, the algorithm has to create a start and finish time for every request. We will say a request is late is it misses its deadline i.e if its finish time is greater than its deadline. Our goal is to assign intervals to all requests and minimize the maximum lateness. This arises naturally when scheduling jobs that need to use a single machine(one resource). Designing the Algorithm. The data of all requests comes in the form (ti,di) i.e time at which request i starts and its deadline. And we shall use this form to order the requests. We can use two approaches to order the requests:
- Schedule jobs in increasing length. This ignores the deadline of the jobs.
- Order by smallest slack time i.e deadline - length. This unfortunately will not work as proven on page 127.
There is a much better approach than the two above stated and will always yield an optimal solution, and that is ordering them in increasing order of their deadlines. This rule is often called the Earliest Deadline First. Job 1 will start at time s and the next job will start at its preceding job's finish time. In order to prevent idleness of the resource. Algorithm:
Order the jobs in order of their deadlines
Assume for simplicity of notation that d1<= ...<=dn
Initially, f=s
Consider all jobs in order
Assign every job to the time interval from preceding finish time to new finish time+its time length
Let f=f+time length of job
End
Return the set of scheduled intervals for every job.
Analyzing the algorithm. The solution has no gaps first of all, and it is easy to see that there is an optimal schedule with this property. That is, there is no optimal schedule with no idle time. How can we prove that solution A is optimal and its maximum lateness L is as small as possible? Our plan is to gradually modify the optimal solution, preserving its optimality at each step, but eventually transforming it into a schedule that is identical to the schedule A found by the greedy algorithm. We refer to this type of analysis as the Exchange Argument. Inversions. We say a schedule A' has an inversion if a job i with deadline di is scheduled before a job j with deadline dj such that di>dj. We already know that our schedule above is inversion-free. Suppose there jobs with identical deadlines then there can be many different schedules with the same max lateness, and this is proven on Page 128.
The following claim can be made:
- There is an optimal schedule that has no inversions and no idle time.
And we see that if an optimal solution has an inversion, we can swap the inverted jobs to have less inversions and thus yields no larger than the previous lateness as proven on page 129-130. Extensions.
There are many more possible generalizations of this scheduling problem. We only assumed that all jobs were available at the common starting time s. What if all jobs had different starting times? How would we take this into account so as to design an efficient algorithm(ch.8)?
This section was pretty easy to read through and i give it a scale of 8.5/10.
