We look further into some of the algorithms for job scheduling today.we discuss feasibility and optimality of scheduling. Feasibility is defined in this way. A schedule of jobs is feasible if and only if the deadlines of the jobs involved are in increasing order and less than the target. This is called deadline order. Suppose J is feasible, J = {1,2,..k} we maintain some order 1,2,...k but J is feasible in some order other than that.
Suppose r1, r2...rk is a feasible solution. we can show that it can be modified to the schedule above. Let us say at some point that the two orders disagree. At that point, we can check and find that 11a job is the same and we have one more point that it agrees. Eventually the given schedules are shown feasible
A schedule of jobs is optimal such as when it's greedy. We said the greedy solution is one when the order of profits is in the descending order
Suppose we have two job schedules J and k there is a job in one that does not belong to the other and vice versa. The claim is the profit from the non optimal schedule is less than the one in the optimal one. We can establish this formally but intuitively we see why the greedy solution is considered optimal since we covered what greedy job scheduling is in the previous post.
To prove that greedy algorithm is optimal we take the greedy solution as I and optimal solution as J
We begin with I is not equal to J i.e. I and J are not comparable. If J belongs to I is not possible, then J is not optimal. If I belongs to J any missing job is compatible.
Let's look at highest profit job in I, not in J. i.e. a belongs to I, a does not belong to J and has the highest profit. b belongs to J and b does not belong to I,
The claim is profit from a is greater than or equal to profit from b.
a arrange J also in descending order of profit.
I ----- a this schedule has job a with Max profit
J -----b this schedule has job b with Max profit
If profit of b is more than a, it would have been included in I since the jobs are compatible but this is not the case because I has listed a as max
This is one proof.
Now lets take SI as schedule for I and SJ schedule for J for symmetrical schedules. We want to make SI & SJ agree on time slots for all common job
If we take a job x and a job z common to both , we show that if x occurs after z on Si, and x occurs before z on Sj, then we walk the events from the rightmost end where we had the least profit and we see that this ordering is a discrepancy. Note that with regard to absolute time the same job in both schedules can be aligned or fixed to the time reference which could be chosen as the original positions of either schedule for that job. Having fixed a job this way, we now repeat for all the common jobs such that they occupy the same time slots
In the above we use I as the reference for our assumptions and findings in j.
We establish the following two facts
If there's a job a with Max profit this in I but not J
Then the profit of any job b in j that is not in I Is lesser than that of a
And common jobs have the same time
Suppose r1, r2...rk is a feasible solution. we can show that it can be modified to the schedule above. Let us say at some point that the two orders disagree. At that point, we can check and find that 11a job is the same and we have one more point that it agrees. Eventually the given schedules are shown feasible
A schedule of jobs is optimal such as when it's greedy. We said the greedy solution is one when the order of profits is in the descending order
Suppose we have two job schedules J and k there is a job in one that does not belong to the other and vice versa. The claim is the profit from the non optimal schedule is less than the one in the optimal one. We can establish this formally but intuitively we see why the greedy solution is considered optimal since we covered what greedy job scheduling is in the previous post.
To prove that greedy algorithm is optimal we take the greedy solution as I and optimal solution as J
We begin with I is not equal to J i.e. I and J are not comparable. If J belongs to I is not possible, then J is not optimal. If I belongs to J any missing job is compatible.
Let's look at highest profit job in I, not in J. i.e. a belongs to I, a does not belong to J and has the highest profit. b belongs to J and b does not belong to I,
The claim is profit from a is greater than or equal to profit from b.
a arrange J also in descending order of profit.
I ----- a this schedule has job a with Max profit
J -----b this schedule has job b with Max profit
If profit of b is more than a, it would have been included in I since the jobs are compatible but this is not the case because I has listed a as max
This is one proof.
Now lets take SI as schedule for I and SJ schedule for J for symmetrical schedules. We want to make SI & SJ agree on time slots for all common job
If we take a job x and a job z common to both , we show that if x occurs after z on Si, and x occurs before z on Sj, then we walk the events from the rightmost end where we had the least profit and we see that this ordering is a discrepancy. Note that with regard to absolute time the same job in both schedules can be aligned or fixed to the time reference which could be chosen as the original positions of either schedule for that job. Having fixed a job this way, we now repeat for all the common jobs such that they occupy the same time slots
In the above we use I as the reference for our assumptions and findings in j.
We establish the following two facts
If there's a job a with Max profit this in I but not J
Then the profit of any job b in j that is not in I Is lesser than that of a
And common jobs have the same time
No comments:
Post a Comment