Lemma L5.3-1

"The L solution is possible <=>The execution of the projects in L in inclining order of deadlines can be done with no deadlines violation."

Proofing:The "<=" direction is obvious.For the "=>" direction,we assume that the L solution is possible, which means that there is an execution order(let's call it :E(1),...,E(k) ),which is executed with no deadline's violation,that is j<d(j) for j=1,..,k. If E(i1),...E(ik) is another order of the same projects with inclining deadlines,that is d(i1)<=..<=d(ik) ,we must show that our projects can be executed in this order,without deadline's violation. Let's consider that the i(a) project is the first project our two orders differ.Then there will be i(a)>a.We change the places of E(a) and E(ia) in the possible solution,and because there is d(ia)>=d(a) there is no violation in the deadlines.If we repeat this procedure the two orders will finally be the same.

HTML PAGE DIRECTOR :Papaioannou Panagiotis