Lindo Systems

MODEL:
! PERT/CPM project scheduling with resource constraints(PERTRSRC);
! Keywords: PERT, CPM, Scheduling, Resource constraints, Project management;
! See:  Pritzker, A., L. Watters, and P. Wolfe(1969),"Multiproject Scheduling with 
  Limited Resources: a Zero-One Programming Approach", Management Science,
  vol. 16, no. 1, Sept., pp. 93-108.
! A project consists of a collection of activities.  Each activity is described by:
!  a) duration,  b) set of predecessor activities,  c) set of resources or machines required.
! There is a limited number of each resource/machine.
! An activity cannot be started until: 1) all its predecessors have completed, and 
! 2) resources/machines required are available.
   !
   ! The precedence diagram is:
   !       /FCAST\---SCHED----COSTOUT\
   !      /       \                   \
   ! FIRST         \                   \
   !      \         \                   \
   !       \SURVEY-PRICE---------------FINAL;
 
SETS:
! There is a set of tasks with a given duration, and
    a start time to be determined;
   TASK: TIME, START, ES;
! The precedence relations, the first task in the
    precedence relationship needs to be completed before the
    second task can be started;
   PRED( TASK, TASK);
! There are a set of periods;
   PERIOD;
   RESOURCE: CAP;
! Some operations need capacity in some department;
   TXR( TASK, RESOURCE): NEED;
! SX( I, T) = 1 if task I starts in period T;
   TXP( TASK, PERIOD): SX;
   RXP( RESOURCE, PERIOD);         
  ENDSETS
 
 DATA: 
 ! Upper limit on number of periods required to complete the project;
   PERIOD = 1..20;
 ! Task names and duration;
   TASK  TIME = 
   FIRST    0
   FCAST    7
   SURVEY   2
   PRICE    1
   SCHED    3
   COSTOUT  2
   FINAL    4; 

! The predecessor/successor combinations;
  PRED=  FIRST,FCAST,    FIRST,SURVEY,
         FCAST,PRICE,    FCAST,SCHED,    SURVEY,PRICE,
         SCHED,COSTOUT,  PRICE,FINAL,    COSTOUT,FINAL;
! There are 2 departments, accounting and operations,
   with capacities...;
   RESOURCE = ACDEPT, OPNDEPT; 
        CAP =   1,      1;
! How much each task needs of the various rource;
          TXR,       NEED = 
     FCAST,   ACDEPT,  1
     SURVEY, OPNDEPT,  1
     SCHED,  OPNDEPT,  1
     PRICE,   ACDEPT,  1
     COSTOUT, ACDEPT,  1; 
 ENDDATA
!----------------------------------------------------------;
! Decision variables:
    SX( i,t) = 1 if task i is started in period t,
    START(i) = start time of product i;

SUBMODEL SEQUENCE:
! Minimize start time of last task;
  NTSK = @SIZE(TASK);
 MIN = START( NTSK);
! Start time for each task;
 @FOR( TASK( I):
   [DEFSTRT] START( I) = @SUM( PERIOD( T): T * SX( I, T));
     );
 @FOR( TASK( I):
!  Each task must be started in some period;
   [MUSTDO]  @SUM( PERIOD( T): SX( I, T)) = 1;
! The SX vars are binary, i.e., 0 or 1;
   @FOR( PERIOD( T): @BIN( SX( I, T)););
      );
! Precedence constraints;
  @FOR( PRED( I, J):
    [PRECD]  START( J) >= START( I) + TIME( I);
      );
! Resource usage, For each resource R and period T;
  @FOR( RXP( R, T):
! Sum over all tasks I that use resource R in period T;
    [RSRUSE] @SUM( TXR( I, R):
       @SUM( PERIOD( S)| S #GE# ( T - ( TIME( I) - 1)) #AND# S #LE# T:
               NEED( I, R) * SX( I, S))) <= CAP( R);
      );
! The following makes the formulation tighter;
! Compute earliest start disregarding resource constraints;
   @FOR( TASK( J):
     ES( J) = @SMAX( 0, @MAX( PRED( I, J): ES( I) + TIME(I)));
   ! Task cannot start earlier than unconstrained early start;
     @SUM( PERIOD(T) | T #LE# ES( J): SX( J, T)) = 0;
       );
 ENDSUBMODEL

CALC:
  @SET('TERSEO',2); ! Turn off default output;
  @SOLVE( SEQUENCE);
  ! Print a simple report;
  @WRITE(@NEWLINE(1),' Project length= ', START(NTSK)+TIME(NTSK), @NEWLINE(1));
   @WRITE('   Task   Start_At  End_At  Resources_used', @NEWLINE(1));
 ! Print in time order;
  @FOR(PERIOD( t):
    @FOR(TASK(j) | @ABS(START(j)- t) #LE# .5:
      @WRITE( ' ', @FORMAT(TASK(j),"8s"),
              ' ', @FORMAT(START(j),"7.1f"),
              ' ', @FORMAT(START(j)+TIME(j),"7.1f"));
    ! Find any resources r used by task j;
      @FOR( TXR(j,r):
          @WRITE('  ', @FORMAT(RESOURCE(r),"8s"));
            );
      @WRITE(@NEWLINE(1));
     );
  );
ENDCALC