! 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; ! 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; ! 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 = 300ENDDATA ! 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)); );