! Compute critical paths, earliest and latest start times  (CritPath.lng);
! Keywords: CPM, Critical path, PERT, Project Management, Scheduling, Slack;
SETS:
   TASK: PTIME, ES, LS
       , WORK1, WORK2 ;
! The precedence relations, the first task in the
    precedence relationship needs to be completed before the
    second task can be started;
    PRED( TASK, TASK);
ENDSETS
DATA:
! Case: Prepare a marketing plan for a product;
  ! The precedence diagram is:
  !       /FCAST\---SCHED----COSTOUT\
  !      /       \                   \
  ! FIRST         \                   \
  !      \         \                   \
  !       \SURVEY-PRICE-----------FINAL;
! The activities, or tasks;
!CaseMP  TASK= FIRST, FCAST, SURVEY, PRICE, SCHED, COSTOUT, FINAL;
! and their processing times;
!CaseMP  PTIME= 0,     14,     3,      3,     7,     4,       10;
! Here are the predecessor -> successor pairs;
!CaseMP   PRED=   FIRST, FCAST,    FIRST, SURVEY,
          FCAST, PRICE,    FCAST, SCHED,
         SURVEY, PRICE,
          SCHED, COSTOUT, 
          PRICE, FINAL,  
        COSTOUT, FINAL;

! Case Build a Home: Dig basement, Pour Foundation, Pour basement floor,
   Install floor joists,  Wall studding, Rough out interior, Roof,  Landscaping;
! The activities, or tasks and their processing times;
!CaseBH; TASK  PTIME = 
          DIG   3  
        FOUND   4  
        POURB   2  
       JOISTS   3    
        WALLS   5  
      RAFTERS   3    
        FLOOR   4    
        ROUGH   6  
         ROOF   7    
       FINISH   5    
        SCAPE   2 ;

! Here are the predecessor -> successor pairs;
!CaseBH; PRED = 
     DIG    FOUND 
   FOUND    POURB  
   FOUND   JOISTS 
   FOUND    WALLS 
   WALLS  RAFTERS
   POURB  RAFTERS 
  JOISTS    FLOOR  
   FLOOR    ROUGH  
 RAFTERS     ROOF 
   ROUGH   FINISH 
    ROOF   FINISH  
   POURB    SCAPE 
   WALLS    SCAPE
; 
ENDDATA
PROCEDURE ErlStrtGet:
! Compute Earliest start times for each TASK.
 Inputs:
   PTIME( j) = processing time for task j,
   PRED( i, j) = predecessor->successor pairs,
   ES( j) = initial lower bound on earliest start of task j,
 Outputs:
   ErlStrt = 0 if successful,
             1 if the PRED graph has cycles
   ES( j) = earliest start time for j, taking into account PRED;
! Count number of predecessors, WORK1( j)  of each task j;
  @FOR( TASK( j) : WORK1( j) = 0);
  @FOR( PRED( j, k): WORK1( k) = WORK1( k) +1);
! Put all tasks with 0 preds on the WORK2 stack;
  stacknum = 0;
  @FOR( TASK( j) | WORK1( j) #EQ# 0:
    stacknum = stacknum + 1;
    WORK2( stacknum ) = j;
      );
! While there is a task j on the stack;
  @WHILE( stacknum #GT# 0:
! Remove task j from stack. We now know its ES;
     jnow = WORK2( stacknum);
     stacknum = stacknum - 1;
     @FOR( PRED( j, k) | j #EQ# jnow:
        ES( k) = @SMAX( ES( k), ES( j) + PTIME( j)); ! Update ES( k) for all successors k;
        WORK1( k) = WORK1( k) - 1; ! decrement number unprocessed predecesors;
        @IFC( WORK1( k) #EQ# 0: ! Is k now ready for the ready stack?;
          stacknum = stacknum + 1; ! Yes, put on stack;
          WORK2( stacknum) = k;
            );
         );
        );
ENDPROCEDURE
PROCEDURE LstStrtGet:
! Compute Latest start times for each TASK.
 Inputs:
   PTIME( j) = processing time for task j,
   PRED( i, j) = predecessor successor pairs,
   LS( j) = initial upper bound on latest start of task j,
 Outputs:
   LstStrt = 0 if successful,
             1 if the PRED graph has cycles
   LS( j) = earliest start time for j, taking into account PRED;
! Count number of successors, WORK1( j)  of each task j;
  @FOR( TASK( j) : WORK1( j) = 0);
  @FOR( PRED( j, k): WORK1( j) = WORK1( j) +1);
! Put all tasks with 0 successors on the WORK2 stack;
  stacknum = 0;
  @FOR( TASK( k) | WORK1( k) #EQ# 0:
    stacknum = stacknum + 1;
    WORK2( stacknum ) = k;
      );
! While there is a task k on the stack;
  @WHILE( stacknum #GT# 0:
! Remove task k from stack, we now know its LS;
     know = WORK2( stacknum);
     stacknum = stacknum - 1;
     @FOR( PRED( j, k) | k #EQ# know:
        LS( j) = @SMIN( LS( j), LS( k) - PTIME( j)); ! Update LS( j) for all predecessors j;
        WORK1( j) = WORK1( j) - 1; ! decrement number unprocessed successors;
        @IFC( WORK1( j) #EQ# 0: ! Is j now ready for the ready stack?;
          stacknum = stacknum + 1;
          WORK2( stacknum) = j;
            );
         );
        );
ENDPROCEDURE
CALC:
  @SET( 'OROUTE',1);   ! Buffer size for routing output to window;
  @SET( 'TERSEO',1);   ! Output level (0:verb, 1:terse, 2:only errors, 3:none);
  @SET( 'WNLINE',10000);! Max command window lines saved (Windows only);

! Begin: critical path, slack analysis;
  @FOR( TASK( j): ES( j) = 0); ! Initially, assume every task is available at time 0;
  ErlStrtGet; !  Get earliest start times;
! Compute latest starts;
! Earliest finish for project;
  PROJLEN = @MAX( TASK( j): ES( j) + PTIME( j));
  @FOR( TASK( j): LS( j) = PROJLEN - PTIME( j)); ! Initial latest finish for all tasks;
  LstStrtGet;  ! Get latest start times;
! Compute slack for each task;
  @FOR( TASK( j): WORK1( j) = LS( j) - ES( j));
! Write a simple report;
! Put sort order in WORK2( j), sorted 1st on slack, 2nd on early start;
  WORK2 = @SORT( WORK1, ES);
  @WRITE('    Project length= ', PROJLEN, @NEWLINE( 1));
  @WRITE('      Task  Slack  EarlyStart  LateStart  PTime', @NEWLINE( 1));
  @FOR( TASK( j):  ! Display sorted list;
    jnow = WORK2( j);
    xrow = j + 2;
    @WRITE(   @FORMAT( TASK( jnow),'10s'), ' ',     @FORMAT( WORK1( jnow) ,'6.1f') ,
       ' ',   @FORMAT( ES( jnow),'6.1f'), '      ', @FORMAT( LS( jnow),'6.1f'),
      '    ', @FORMAT( PTIME( jnow),'6.1f'), @NEWLINE( 1));
    );
! End: critical path, slack analysis;
ENDCALC