ALGORITHM 40 CRITICAL PATH SCHEDULING 

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

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: 
	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], 
	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; 
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 h 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]l + DIJ[k]; 
			if ti[J[kH = 0 V ti[J[k]] < max then ti[J[k]] := max; 
A: 		end ti; 
	te[J[n]] := ti[J[n]l; 
	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 

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.