! LINGO model for sequencing jobs in a flow shop.
Assume that same sequence is used on all machines;
SETS:
JOB;
JINP( JOB, JOB):Y;
MACH;
MXP( MACH, JOB): PT, FT;
ENDSETS DATA:
MACH = A..C; ! The set of machines;
JOB = 1..6; ! The set of jobs;
PT = 9 3 4 8 2 1 ! Processing time on machine 1;
3 7 6 2 4 5 ! Processing time on machine 2;
6 5 2 4 8 3; ! on machine 2;
! Keywords: Sequencing, Scheduling, Flow shop scheduling;
ENDDATA
! Variables:
Y(j,p) = 1 if job j is assigned to position p,
FT(m,p) = finish time on machine m of job in position p;
@FOR( JINP(j,p): @BIN(Y(j,p))); ! The Y's = 0 or 1;
nm = @SIZE(MACH);
nj = @SIZE(JOB);
!MIN = @SUM( JOB(p): FT(nm, p)); MIN = FT(nm,nj); ! Minimize makespan;
! Each job must be assigned a position;
@FOR( JOB(j):
@SUM( JOB(p): Y(j,p)) = 1;
);
! Each position gets a job;
@FOR( JOB(p):
@SUM( JOB(j): Y(j,p)) = 1;
);
! Finish time on machine m of job in position p;
! Jobs on machine 1 have no predecessors;
FT(1,1) >= @SUM( JOB(j): PT(1,j)*Y(j,1));
@FOR( JOB( p) | p #GT# 1:
! Job in position p cannot start until job in position p-1 finishes;
FT(1,p) >= FT(1,p-1) + @SUM( JOB(j): PT(1,j)*Y(j,p));
);
@FOR( MACH(m) | m #GT# 1:
! Job in position p on machine m cannot start until it finishes on m-1;
FT(m,1) >= FT(m-1,1) + @SUM( JOB(j): PT(m,j)*Y(j,1));
@FOR( JOB( p) | p #GT# 1:
! Job in position p cannot start on m until previous job
finishes on m;
FT(m,p) >= FT(m,p-1) + @SUM( JOB(j): PT(m,j)*Y(j,p));
! Job in position p on machine m cannot start until it finishes on m-1;
FT(m,p) >= FT(m-1,p) + @SUM( JOB(j): PT(m,j)*Y(j,p));
);
);
|