! Job selection and sequencing.
  Given a
    Set of jobs, each with an
     earliest begin time,
     latest finish time,
     processing time, and
     value if processed, and a
     machine that can process only one job at a time, 
   Decide 
     which jobs to accept, and the
     sequence in which to process accepted jobs;

! Keywords: machine sequencing, sequencing,
   scheduling, due dates, job selection;
SETS:
  job: r, p, d, v, s, z;
  jxj(job,job): y;
ENDSETS
DATA:
 !      1  2  3  4  5  6  7  8  9 10 11
 ! Ready times;
   r =  0  0  2  2  3  5  5  6 12 20 20 ;
 ! The processing times;
   p = 18 24  4  8 13  1 12  2  3  6  5 ;
 ! Due date of each job;
   d = 22 25  8 11 29 10 25 14 16 29 32 ;
 ! Value of processing the job;
   v =  2  6  1  2  3  5  7  4  4  3  1 ;
ENDDATA

SUBMODEL JOBDO:
! Variables:
    z(j) = 1 if job j is accepted,
    y(j,k) = 1 if both jobs j and k accepted and
               j is processed earlier than k in sequence,
    s(j) = start time for job j, if j accepted, else 0;

! Maximize the value of accepted jobs;
 MAX = OBJ;
    OBJ = @SUM( job(j): v(j)*z(j));

! Cannot start accepted job i before its ready time;
 @FOR( job(i):
   [STIM] s(i) >= r(i)*z(i);
    @BIN( z(i));
     );

! Cannot finish job i after its due-date;
 @FOR( job(i):
   [FTIM] s(i) <= (d(i)-p(i))*z(i);
     );

! The sequencing constraints;
   @FOR( jxj( i,j) | i #LT# j:
  ! If both i and j are accepted, must choose a sequence;
    [DOIJ] y(i,j)+ y(j,i) >= z(i) + z(j)-1;
  ! If either not accepted, do not choose a sequence; 
    [NOTI] y(i,j) + y(j,i) <= z(i);
    [NOTJ] y(i,j) + y(j,i) <= z(j);
     @BIN(y(i,j)); @BIN(y(j,i)); 
  ! If i precedes j, then s(j) >= s(i) + p(i);
    [IPJ]  s(j) >= s(i) + y(i,j)*p(i) - (d(i)-p(i))*(1-y(i,j));
  ! If j precedes i, then s(i) >= s(j) + PT(j);
    [JPI]  s(i) >= s(j) + y(j,i)*p(j) - (d(j)-p(j))*(1-y(j,i));
      );
 ENDSUBMODEL


 CALC:
  @SET('TERSEO',2); ! Turn off default output;
  @SOLVE ( JOBDO);
 ! Display a little report;
  @WRITE(' Which jobs should we do, in what order to Max Profit?',@NEWLINE(1));
  @WRITE('        Various times', @NEWLINE(1));
  @WRITE(' Job  Ready  Processing  Due  Value  Start  Finish   ',@NEWLINE(1));
   @FOR( job(i):
     @WRITE( @FORMAT( i,"3.0f"),'    ', @FORMAT(r(i),"3.0f") ,'     ', @FORMAT(p(i),"3.0f"),
      '       ', @FORMAT(d(i) ,"3.0f"),'   ', @FORMAT(v(i),"3.0f"));
     @IFC( z(i) #GT# 0.5:
       @WRITE('   ',@FORMAT(s(i),"3.0f"),'     ', @FORMAT(s(i)+p(i),"3.0f"),@NEWLINE(1));
      @ELSE
       @WRITE('    --      -- ',@NEWLINE(1))
         );
       );
    @WRITE(@NEWLINE(1),' Total value of accepted jobs=  ',OBJ, @NEWLINE(1));
 ENDCALC