Lindo Systems

MODEL:
! PERT/CPM project scheduling with resource constraints;
! 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.
! This is the six job, six machine, six operations per job scheduling problem
    of Fisher and Thompson. Ref.
    Muth, J. and G. Thompson(1963) Industrial Scheduling, Prentice-Hall, Englewood Cliffs, NJ.;
! Keywords: Scheduling, Resource constraints, Fisher-Thompson, Pritzker;
    SETS:
! There is a set of tasks with a given duration, and
    a start time to be determined;
   TASK: TIME, 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, B;       
  ENDSETS
 
 DATA: 
 ! This data set represents a jobshop in which each job consists 
of six operations that must be done in order, each operation 
requiring a specific machine;
 ! Upper limit on number of periods required to complete the project;
   PERIOD = 1..60;
 ! Task names and duration, the Fisher-Thompson problem;
   TASK  TIME = 
    j11   1    j12   3    j13   6    j14   7    j15   3    j16   6
    j21   8    j22   5    j23  10    j24  10    j25  10    j26   4
    j31   5    j32   4    j33   8    j34   9    j35   1    j36   7
    j41   5    j42   5    j43   5    j44   3    j45   8    j46   9
    j51   9    j52   3    j53   5    j54   4    j55   3    j56   1
    j61   3    j62   3    j63   9    j64  10    j65   4    j66   1
    j00   0; 

! The machines,
   with capacities...;
   RESOURCE = M1 M2 M3 M4 M5 M6; 
        CAP =  1, 1, 1, 1, 1, 1;
! How much each task needs of each resource;
      TXR, NEED = 
    j11 M3  1    j12 M1  1    j13 M2  1    j14 M4  1    j15 M6  1    j16 M5  1
    j21 M2  1    j22 M3  1    j23 M5  1    j24 M6  1    j25 M1  1    j26 M4  1
    j31 M3  1    j32 M4  1    j33 M6  1    j34 M1  1    j35 M2  1    j36 M5  1
    j41 M2  1    j42 M1  1    j43 M3  1    j44 M4  1    j45 M5  1    j46 M6  1
    j51 M3  1    j52 M2  1    j53 M5  1    j54 M6  1    j55 M1  1    j56 M4  1
    j61 M2  1    j62 M4  1    j63 M6  1    j64 M1  1    j65 M5  1    j66 M3  1; 
! The predecessor/successor pairs;
  PRED=  j11 j12  j12 j13  j13 j14  j14 j15  j15 j16  j16 j00
         j21 j22  j22 j23  j23 j24  j24 j25  j25 j26  j26 j00
         j31 j32  j32 j33  j33 j34  j34 j35  j35 j36  j36 j00
         j41 j42  j42 j43  j43 j44  j44 j45  j45 j46  j46 j00
         j51 j52  j52 j53  j53 j54  j54 j55  j55 j56  j56 j00
         j61 j62  j62 j63  j63 j64  j64 j65  j65 j66  j66 j00;
 ENDDATA
!----------------------------------------------------------;
! Variables:
    SX(i,t) = 1 if task i starts in period t,
    B(i,t) = 1 if task i starts in period t or earlier,
  Computed parameters:
    ES(i) = earliest start of task i;

NL = @SIZE( TASK);
! Minimize start time of last task;
 MIN = @SUM( PERIOD( T): T * SX( NL, T));

 @FOR( TASK( I):
!  Each task must be done;
   [DO]  @SUM( PERIOD( T): SX( I, T)) = 1;
! The B vars are binary, i.e., 0 or 1;
   @FOR( PERIOD( T): 
     @BIN( B( I, T));
     @BND(0, B(I,T), 1);
        );
! B(I,T) = 1 if task I starts in T or earlier;
    B(I,1) = SX(I,1);
    @FOR( PERIOD(T)| T #GT# 1:
       B(I,T) = B(I,T-1) + SX(I,T); 
        )
      );

! Precedence constraints. If task j starts in
  t or earlier, then its predecessor i must
  start in T-TIME(i) or earlier;
  @FOR( PRED( I, J):
    @FOR( PERIOD(T)| T #LE# TIME(I): B(J,T)= 0;);
    @FOR( PERIOD(T)| T #GT# TIME(I):
    [PCD] B(J,T) <= B(I,T-TIME(I));
        )
    !  START( J) >= START( I) + TIME( I);
      );

! Resource usage, For each resource R and period T;
  @FOR( RESOURCE( R):
    @FOR( PERIOD( T):
! Sum over all tasks I that use resource R in period T;
    [RS] @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;
       );
 END