! 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));
);
|