 |  |
"The greedy algorithm always gives a best solution to the ordering projects by deadline precedence problem."
Proofing: Let's call L the solution we receive from the greedy algorithm,and M a best solution.If L=M there is nothing else to prove,our job is done,so we consider the case that L not equal to M.We must only show that we can make some changes in M and finally receive L without a decrease of M's total profit.
At first let's consider random common projects between L and M,E(i). E(i) belong in L as well as in M.Let's also consider as [t,t+1]&[t',t'+1] the time unit in which the E(i) project is executed in L and M accordingly.If t<t' we transfer the execution time of E(i) in L from t to t'.Whichever project was supposed to be executed at t' time unit is transferred at t time unit.If t>t' we do exactly the same in M .Now,the new order of execution in either L or M continues not to abort out deadlines(can you tell why?).We can say that all common projects of L and M are executed at the same time units.
Besides L not equal to M there is also that L is not a subset of M and M is not a subset of L.If L was a subset of M,the greedy algorithm would not had finished.If M was a subset of L than, M solution would not be a best one.Therefore,there are projects belonging to L and do not belong to M and vice versa.We consider the set of projects,that belong to L and do not belong to M,we call it:L-M.Out of this set we choose the one with the maximum profit E(a).For all the projects E(b) of the M-L set we can easily say that P(a)>P(b),otherwise the greedy method would have added the E(b) project in L before E(a).Let's say that the E(a) project is executed at the [t,t+1] time unit.At the exact same moment another project E(b) is executed in M,and E(b) does not belong in L,since the projects are executed simultaneously.If we erase E(b) out of M,and replace it with E(a) the total profit of M does not decrease,and those two solutions (L and M ) have one more common project.If we continue with the same project we end up in L without decrement of the total profit of M.Therefore L is also best solution.
| |
HTML PAGE DIRECTOR :Papaioannou Panagiotis