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:

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