9 REM * STANFORD UNIVERSITY GRADUATE SCHOOL OF BUSINESS* 10 REM * PROGRAM : GCPATH 11 REM *PURPOSE: PERFORMS A CRITICAL PATH ANALYSIS * 12 REM *PROGRAMMED BY: W.F. SHARPE, MAY, 1971 * 14 DIM P(100),S(100),T(100),E(100),L(100) 15 DIM A(100) 17 PRINT'HAVE YOU ENTERED YOUR DATA ALREADY'; 18 INPUT A$ 19 IF MID(A$,1,1)='N' THEN 900 20 REM -------------------------------- 22 MAT E=CON 23 MAT E=(-1)*E 24 MAT L=CON 25 MAT L=(-1)*L 99 REM -- PROCESS JOBS 100 GOSUB 300 109 REM -- CALCULATE EARLY START TIMES 110 GOSUB 600 119 REM -- CALCULATE LATE START TIMES 120 GOSUB 700 129 REM -- PRINT RESULTS 130 GOSUB 800 140 GOTO 9999 299 REM --------------------------------- 300 REM -- SUBROUTINE TO PROCESS JOBS 301 DIM Z(100) 302 PRINT'JOB TIME PREDECESSORS' 303 PRINT'--- ---- ------------' 305 J=0 306 N9=1 308 MAT A=ZER 309 MAT T=ZER 310 REM -- GET A JOB 311 GOSUB 400 312 IF Z9<0 THEN 350 313 REM -- JOB IS IN ROW N8 314 REM -- PREDECESSORS ARE IN Z(1) THRU Z(Z9) 330 FOR K=1 TO Z9 332 J=J+1 334 P(J)=Z(K) 336 S(J)=N8 338 NEXT K 340 GOTO 310 350 REM -- ALL JOBS COMPLETE, N9= TOTAL NUMBER 360 REM -- FIND JOBS WITH NO SUCCESSOR 361 MAT Z=ZER 365 FOR K=1 TO J 366 Z(P(K))=1 367 NEXT K 370 REM -- SET UP ARCS TO FINISH 372 FOR I=2 TO N9-1 373 IF Z(I)=1 THEN 377 374 J=J+1 375 P(J)=I 376 S(J)=N9 377 NEXT I 380 REM -- FIND JOBS WITH NO PREDECESSOR 381 MAT Z=ZER 385 FOR K=1 TO J 386 Z(S(K))=1 387 NEXT K 390 REM -- SET UP ARRCS FROM START 392 FOR I=2 TO N9 393 IF Z(I)=1 THEN 397 394 J=J+1 395 P(J)=1 396 S(J)=I 397 NEXT I 398 A9=J 399 RETURN 400 REM ---------------------------------------- 401 REM -- SUBROUTINE TO READ A JOB 405 Z9=0 410 REM -- FORMAT IS: 411 REM JOB #, TIME, PRED.#,PRED#,...PRED.#,-1 412 REM LAST LINE: 413 REM -1 420 READ J1 421 IF J1>0 THEN 430 422 REM -- ALL DONE 423 Z9=-1 424 N9=N9+1 425 RETURN 430 REM -- LOOD FOR THIS JOB 432 FOR I=1 TO N9 434 IF J1=A(I) THEN 445 436 NEXT I 438 REM -- NEW JOB 440 N9=N9+1 441 A(N9)=J1 442 N8=N9 443 GOTO 450 445 N8=I 450 REM -- STORE TIME 451 READ T(N8) 455 REM -- PRINT 456 PRINT USING'### ###',J1,T(N8);:PRINT ' '; 460 REM -- READ PREDECESSORS 462 READ P1 463 IF P1<0 THEN 495 464 PRINTP1; 465 Z9=Z9+1 470 REM -- LOOK FOR PREDECESSOR 472 FOR I=1 TO N9 474 IF P1=A(I) THEN 485 476 NEXT I 478 REM -- NEW JOB 480 N9=N9+1 481 A(N9)=P1 482 Z(Z9)=N9 483 GOTO 490 485 Z(Z9)=I 490 GOTO 462 495 REM -- ALL PROCESSED 496 PRINT 497 RETURN 599 REM ----------------------------------- 600 REM -- SUBROUTINE TO CALCULATE EARLY START TIMES 610 E(1)=0 611 N3=0 615 S9=0 620 FOR J=1 TO A9 625 IF E(P(J))=-1 THEN 640 627 T9=E(P(J))+T(P(J)) 629 IF T9<=E(S(J)) THEN 640 631 E(S(J))=T9 633 S9=1 640 NEXT J 642 IF N3>A9+2 THEN 660 644 N3=N3+1 645 IF S9=1 THEN 615 650 RETURN 660 REM -- TOO MANY ITERATIONS 661 PRINT'****PROBLEM CANNOT BE SOLVED -- CHECK FOR CIRCULARITY' 662 GOTO 9999 699 REM --------------------------------------------- 700 REM -- SUBROUTINE TO CALCULATE LATE START TIMES 710 L(N9)=E(N9) 715 S9=0 720 FOR J=A9 TO 1 STEP -1 725 IF L(S(J))=-1 THEN 740 727 T9=L(S(J))-T(S(J)) 729 IF L(P(J))=-1 THEN 732 730 IF T9>=L(P(J)) THEN 740 732 L(P(J)) =T9 733 S9=1 740 NEXT J 745 IF S9=1 THEN 715 750 RETURN 799 REM --------------------------------------------- 800 REM -- SUBROUUTINE TO PRINT RESULTS 809 PRINT 810 PRINT'EARLIEST COMPLETION TIME FOR THE ENTIRE PROJECT =';E(N9) 811 PRINT 814 PRINT TAB(8);' EARLIEST';TAB(24);' LATEST' 815 PRINT 'JOB';TAB(8);' START';TAB(16);'FINIST';TAB(24);'START'; 816 PRINT TAB(30);'FINISH' 817 PRINT'--- ----- ------ ----- ------' 820 FOR I=2 TO N9-1 830 PRINT A(I);TAB(8);E(I);TAB(16);E(I)+T(I);TAB(24);L(I)-T(I); 831 PRINT TAB(30);L(I);TAB(40); 840 IF E(I)+.0001