Lindo Systems
! Single Machine 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,
and changeover times between jobs,
Decide
which jobs to accept, and the
sequence in which to process accepted jobs;
! Keywords: Changeover times, Due dates, Job selection, Machine sequencing,
Scheduling, Sequence dependent setups, Sequencing, Setup time;
SETS:
!Parameters:
r( k) = earliest allowed start time of job k,
d( k) = latest allowed finish time of job k,
p( k) = processing time of job k,
cot( i, k) = changeover time from job i to k,
v( k) = value of job k,
Variables:
y( i, k) = 1 if both jobs i and k are accepted and
job i immediately precedes job k, else 0,
s( k) = start time of job k,
drop( k) = 1 if we do not do job k,
y0( k) = 1 if job k is first,
yL( k) = 1 if job k is last;
job: r, p, d, v, s, y0, yL, drop;
jxj( job, job): COT, y;
ENDSETS
DATA:
! 1 2 3 4 5 6 7 8 9 10 11 12
! Ready times;
r = 0 0 2 2 3 5 5 6 12 20 20 21;
! The processing times;
p = 18 24 4 8 13 1 12 2 3 6 5 5;
! Due date of each job;
d = 22 25 8 11 29 10 25 14 16 29 32 31;
! Value of processing the job;
v = 2 6 4 2 3 5 7 4 4 3 1 6;
! Change over time matrix;
COT= 0 1 3 2 1 2 5 3 2 1 1 1
2 0 2 3 5 1 2 2 0 3 2 1
3 4 0 3 4 2 1 1 2 1 4 1
1 1 3 0 4 1 2 1 1 3 3 1
2 3 2 3 0 3 5 3 2 2 2 1
4 1 2 1 4 0 2 2 4 3 2 4
5 0 2 3 4 4 0 3 4 3 0 4
1 2 2 3 1 1 2 0 4 4 2 4
2 0 2 2 4 2 3 3 0 3 1 4
2 1 2 3 4 1 2 3 4 0 2 4
2 0 2 3 4 0 2 3 4 3 0 4
4 1 1 1 1 1 3 3 3 3 4 0
;
ENDDATA
SUBMODEL JOBROUTE:
! Maximize the value of accepted jobs;
MAX = OBJ ;
OBJ = @SUM( job( j): v( j)*(1- DROP( j)));
! For each JOB k...;
@FOR( JOB( k):
! A job cannot follow itself...;
y( k, k) = 0;
! it must be either the first job, or preceded by some
other job i, or not done;
[NTR] y0( k) + @SUM( JOB( i)| i #NE# k : y( i, k)) + DROP( k) = 1;
! it must be either the last job, or followed by some
other job j, or not done;
[XIT] yL( k) + @SUM( JOB( j)| j #NE# k : y( k, j)) + DROP( k) = 1;
);
! There can be only one job that is...;
@SUM( JOB( k): y0( k)) <= 1; ! ... first;
@SUM( JOB( k): y0( k)) = @SUM( JOB( k): yL( k)); ! ... last;
! Make the y's binary, 0 or 1;
@FOR( jxj( j, k): @BIN( y( j, k)));
! Compute time at which job k starts;
@FOR( JOB( k):
@FOR( JOB( i) | i #NE# k:
! Time of start of job k if preceding job was i;
[RTM] s( k) >= s( i) + ( p( i) + COT( i, k))* y( i, k)
+ ( r( k) - d( i) + p( i))*(1- y( i, k)); ! otherwise;
);
s( k) >= r( k); ! Not early;
s( k) + p( k) <= d( k); ! Not late. Assume r( k) + p( k) <= d( k);
);
ENDSUBMODEL
CALC:
@SET( 'TERSEO', 2); ! Make default output terse;
@SET( 'IPTOLR', .01); ! Relative optimality tolerance;
@SET( 'TIM2RL', 30); ! Time to turn on IPTOLR in seconds;
@SOLVE( JOBROUTE);
! Display a little report;
@WRITE(' Which jobs should we do, in what order to Max Profit,',@NEWLINE(1),
' taking into account ready, changeover(COT), processing, & due times?',
@NEWLINE(1));
@WRITE(@NEWLINE(1),' Various times', @NEWLINE(1));
@WRITE(' Job Ready Processing Due Value COT 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( drop( i) #LT# 0.5:
cotij = @SUM( job( k): cot( k, i)*y( k, i));
@WRITE(' ',@FORMAT( cotij, "3.0f"), ' ', @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