procedure CRITICALPATH (n, I, J, DIJ, ES, LS, EF, LF, TF, FF); 
     integer n; 
     integer array I, J, DIJ, ES, LS, EF, LF, TF, FF;  

     comment

     ALGORITHM 40 CRITICAL PATH SCHEDULING 

     B. LEAVENWORTH 
     American Machine & Foundry Co., Greenwich, Conn. 

     Given the total number of jobs n of a project, the vector pair I[k],
     J[k] representing the kth job, which is thought of as an arrow
     connecting event I[k] to event Jk[Ik < Jk, k = 1 --", n], and a
     duration vector DIJ[k], CRITICALPATH determines:

     The earliest starting time ES[k], latest starting time LS[k], 
     earliest completion time EF[k], latest completion time LF[k], 
     the total float TF[k], and the free float FF[k]. 

     I1 must be 1 and the Ik, Jk must be in ascending order. 

     For example, if the first three jobs are labeled (1, 2), (1, 3), (3, 4),
     then the I, J vectors are (1, 1, 3) and (2, 3, 4) respectively. 

     The critical path is given by each arrow whose total float is zero. 	

     The following non-local labels are used for exits: 
     purl-I[k] not less than Jk, out2-I[k] out of sequence, out3-Ik missing.


     REFERENCES:

     (1) JAMES E. KELLEY, JR. and MORGAN R. WALKER, "Critical-Path Planning and Scheduling," 
     1959 Proceedings of the Eastern Joint Computer Conference.

     (2) M. C. FRISHBERG, "Least Cost Estimating and Scheduling -- Scheduling Phase Only," 
     IBM 650 Program Library File No. 10.3.005. ; 

  begin 
     integer k, index, max, min; 
     integer array ti, te [1:11] ;
   index ≔ 1; 	
     for k ≔ 1 step 1 until n do 
        begin 
           if I[k] ⩾ J[k] then go to purl ;
         if I[k] < index then go to out2 ;
         if I[k] > index ∧ I[k] ≠ index + 1 then go to out3 ;
         if I[k] = index + 1 then index ≔ I[k]; 
           C: 	end;
   for k ≔ 1 step 1 until n do 
        ti[k] ≔ te[k] ≔ 0; 
     for k ≔ 1 step 1 until n do 
        begin 
           max ≔ ti[I[k]] + DIJ[k]; 
           if ti[J[k]] = 0 ∨ ti[J[k]] < max then ti[J[k]] ≔ max; 
           A: 		end ti; 
     te[J[n]] ≔ ti[J[n]]; 
     for k ≔ n step -1 	until 1 do 	
        begin 
           min ≔ te[J[k]] - DIJ[k]; 
           if te[I[k]] = 0 ∧ te[I[k]] > rain 	then te[I[k]] ≔ rain; 
           B: 	end te; 
     for k ≔ 1 step 1 until n do 
        begin 
           ES[k] ≔ ti[I[k]]; 
           LS[k] ≔ te[J[k]] - DIJ[k]; 
           EF[k] ≔ ti[I[k]] + DIJ[k]; 
           LF[k] ≔ te[J[k]]; 
           TF[k] ≔ te[J[k]] - ti[I[k]] - DIJ[k]; 
           FF[k] ≔ ti[J[k]] - ti[I[k]] - DIJ[k] 
        end 
  end CRITICALPATH;