Lindo Systems

! One Machine Weighted tardiness problem;
! Find the best sequence for processing a set of tasks
 on a single machine. Each task has a processing time,
 duedate, and a penalty weight for finishing past the due date.
 We want to minimize total weighted tardiness;
! Keywords: Due dates, Machine sequencing, Scheduling, 
     Sequencing, Tardiness, Weighted tardiness;
sets:
  task: p, w, d, t, e, s;
  txt( task, task): z;
endsets
data: ! Case 1;
 ! Obj= 1592,  10 tasks;
 ! The processing times;
 !Case01   p =  1 25 18  5 24  4  9 13 19 12;
 ! Weight to be applied to any tardiness;
 !Case01   w =  4  9  2  4  5  8  1 10  6  3;
 ! Due date of each job;
 !Case01   d = 10  6 22 32 25  8 11 19 15 14;
!Case01  BigM = 200;

 ! Case 2;
 ! Obj= 1638, 12 tasks;
 ! The processing times;
 !Case02   p =  1 25 18  5 24  4  9 13 19 12  2   6;
 ! Weight to be applied to any tardiness;
 !Case02   w =  4  9  2  4  5  8  1 10  6  3  7   3;
 ! Due date of each job;
 !Case02   d = 10  6 22 32 25  8 11 19 15 14 60 125;
 !Case02  BigM = 300;

 ! Case 3;
 ! Obj= 1895, 14 tasks;
 ! The processing times;
 !Case03   p =  1 25 18  5 24  4  9 13 19 12  2   6   9   6;
 ! Weight to be applied to any tardiness;
 !Case03   w =  4  9  2  4  5  8  1 10  6  3  7   3   2   3;
 ! Due date of each job;
 !Case03   d = 10  6 22 32 25  8 11 19 15 14 60 125  11 124;
 !Case03 BigM = 300;  ! Upper bound on finish times;


! Case 4 Obj= 13128, 13 tasks;
! Inputs: task, ProcessTime, DueDate, WeightOnTardiness;
!Case04
  TASK  p  d  w =
  T013 21 25 10
  T023 25 28  8
  T033 15 20 10
  T043 10 14 10
  T053  9 10  8
  T063 15 18 15
  T073 30 35 10
  T083 20 22 15
  T093 20 22 15
  T103 35 38 10
  T113 29 30  8
  T123 35 38 10
  T133 30 35 10;
!Case04  BigM = 300;  ! Upper bound on finish times;

! Case 5;
! Obj= 2309, 14 tasks;
! The processing times;
!Case05;   p =  1 25 18  5 24  4  9 13 19 12  2   6   9   6;
! Weight to be applied to any tardiness;
!Case05;   w =  4  9  5  5  5  8  1 10  6  5  7   3   2   3;
! Due date of each job;
!Case05;   d = 10  6 22 32 25  8  9 19 15 14 60 125  11 124;
!Case05; BigM = 300;  ! Upper bound on finish times;
enddata
! Variables:
    z( j, k) = 1 if task j appears earlier than k in sequence,
    s( j) = start time for task j,
    t( j) = tardiness for task j relative to due date,
    e( j) = earliness of task j relative to d( j);
! Minimize weighted tardiness;
 MIN = @SUM( task( j): w( j)*t( j));

 @FOR( txt( j, k)| j #LT# k:
    ! If j precedes k, then start of k >= finish of j;
     s( k) >= s( j) + p( j) - BigM* z( k, j);
    ! If k precedes j, then start of j >= finish of k;
     s( j) >= s( k) + p( k) - BigM* z( j, k);
    ! Either j precedes k or k precedes j;
      z( j, k) + z( k, j) = 1;
      @bin( z( j, k)); ! Must be 0 or 1;
       );

  @FOR( task( j):
    ! Compute earliness or tardiness;
      t( j) - e( j) = s( j) + p( j) - d( j); 
      z( j, j) = 0;  ! Task cannot precede itself;
        );

 ! If all tasks need the same single resource, 
   then can add these cuts. 
   The start time of task k is at least as large as the 
   sum of the processing times of all the tasks that precede k;
  @FOR( task( k):
     s( k) >= @sum( task( j) | j #NE# k: p( j)* z( j, k));
      );