 |  |  |
We are about to examine a situation in which greedy methods give the best solution to a very important problem.
Suppose n projects E(1),....E(n) are given.For each and everyone of those projects there is a deadline d(i)>0 which is an integer number of time units and a profit p(i)>0 which is gained only if the project is fulfilled before the exceeded of the deadline.The execution of a project(any of them)requires a time unit.Which projects and in what order should be constructed in order to maximize the total profit?
An expectable or possible solution for this problem, is a set of projects which can all be constructed before their deadline in a certain order,but not necessarily with their order of appearance in the set.If for example we consider n=3, (d(1),d(2),d(3)=2,2,1) and (p(1),p(2),p(3))=(50,100,60) a possible solution is the following set:L={E(1),E(2)} with a total profit of 150, whereas another possible solution(which happens to be the best) is the : L{E(2),E(3)},with order of construction E(3) first, followed by E(2).This solution has a profit which adds up to 160.
If L is a possible solution then the whole profit k is:
k =Sum( p(i) ) (Presuming that E(i) belongs to the L set).
Let's accept a greedy algorithm which starts with L=0 and who in every step selects a project with the maximum possible profit(out of the remaining projects).This algorithm will add the project to the L set,if it still gives us a possible solution. To check whether the overadded solution still is possible the algorithm should logically check all the possible transpositions of the elements of the solution.If in the present step there are k elements in the candidate possible solution, the algorithm would have to check k! cases in the worst case,a number forbiddingly big.The 5.3-1 Lemma which follows provides us a way out to this problem,because we must only try a transfer of projects with inclining deadline order.If this execution order aborts our deadlines we do not add this new project in our solution,and a new project(one with the maximum profit) is selected out of the remaining projects.The algorithm ends when there are no more projects left.
"The L solution is possible <=> the execution of the projects in L in inclining order of
deadlines can be done with no deadlines violation."
Click to see the theoretical proofing of the Lemma 5.3-1 .
"The greedy algorithm always gives a best solution to the ordering projects by deadline
precedence problem."
Click to see the theoretical proofing of the Theorem 5.3-1 .
| | |
HTML PAGE DIRECTOR :Papaioannou Panagiotis