Lindo Systems
! Job to Machine Assignment and Sequencing. (MachAsgSeq)
A number of jobs (trucks, airplanes...)
arrive over time at a facility (terminal...).
A job cannot be started before its arrival time.
Each job has a due date by which its processing must be finished.
The facility has a number of docks or machines.
Each machine can handle at most one job at a time.
For each job and machine combination, there is a
value of this assignment, as well as a
processing time of the job on the specific machine.
We would like to assign jobs to machines, and
a sequence of jobs on the machine so that
at most one job is assigned to a specific machine
at a specific instance, and
there is very little delay, and
the value of the assignments is maximized;
! Examples are: Assigning airplanes to gates at an airport,
assigning trucks to docks at a freight terminal, and
assigning manufacturing jobs to machines in a factory.
An extension, not considered here, is to allow a
job to finish after its due date (be tardy), at a penalty;
! Keywords: Assignment, Gate assignment, Dock assignment,
Sequencing, Machine Assignment, Task assignment;
SETS:
JOB: ARVT, DD;
MACH;
TSLOT;
MXJ( MACH, JOB) : PT, VAL;
MXT( MACH, TSLOT): IDLE;
ENDSETS
! Parameters:
ARVT(j) = arrival or available time of job j, the first
period in which j can be processed,
PT(m,j) = processing time/number periods needed on machine m of job j,
VAL(m,j) = value or profit of assigning job j to machine m,
DD(j) = due date for job j;
! This formulation assumes ARVT, DD, and PT are integers;
! Variables:
Z(m,t,j) = 1 if job j is assigned to machine m starting during time slot t,
IDLE(m,t) = 1 if machine m is idle during period t;
DATA:
TSLOT = 1..30; ! Assume at most 30 minutes in horizon, should be >= max DD;
DWGT = 0.001; ! Weight applied to minimizing sum of completion times;
JOB = J1..J12;
MACH = A B C ;
! Arrival time or first period in which task can be started;
ARVT = 2 1 2 1 1 4 6 7 8 11 8 9;
! Task must be finished at end of this period;
DD = 13 15 11 11 15 14 17 20 18 17 19 24;
! Processing time of tasks on machines;
PT = 4 8 5 6 4 3 2 3 5 4 6 5 ! Mach 1;
5 9 7 7 5 5 1 3 5 5 7 6 ! Mach 2;
6 9 8 7 5 6 3 3 6 5 7 7;! Mach 3;
! Value of doing a specific job on a specific machine;
VAL = 5 8 7 7 6 5 2 2 9 6 4 3 ! Mach 1;
5 9 7 7 5 5 2 3 9 7 6 5 ! Mach 2;
6 9 7 8 6 5 2 3 9 8 7 5;! Mach 3;
ENDDATA
SETS:
! Key observation: job j can be assigned to/started in time slot t only if
( DD(j) - PT(m,j) #GE# t ) #AND# (ARVT( j) #LE# t);
MXTXJ( MACH, TSLOT, JOB) |
( DD(&3) - PT(&1,&3)+1 #GE# &2) #AND# ( ARVT( &3) #LE# &2) : Z, FLAG;
ENDSETS
SUBMODEL ASGSEQ:
! Maximize the value of the assignments;
MAX = OBJVALA - DWGT* DELAYA;
OBJVALA = @SUM( MXTXJ(m,t,j) : VAL(m,j)*Z(m,t,j));
! Compute delay amount, if delayed;
DELAYA = @SUM( MXTXJ(m,t,j): (t- ARVT(j))*Z(m,t,j));
! Each job must be assigned to at most one machine;
@FOR( JOB( j):
[CANDO] @SUM( MXTXJ(m,t,j): Z(m,t,j)) <= 1;
);
! At most one job can be at a machine m at timeslot t, for t not
in an obviously idle period;
! Every machine starts idle before 1st period and remains idle or gets some work;
@FOR( MACH( m):
[JUST1] 1 = IDLE(m,TSTRT) + @SUM( MXTXJ(m,t,j) | t #EQ# TSTRT: Z(m,t,j)) ;
);
! For subsequent periods, in period t-1 (the LHS), if the machine is either:
a)idle, or b)not idle but some job finishes, then
in period t (the RHS) the machine will be either:
a) idle, or b) starts a new task;
@FOR( TSLOT(t) | t #GT# TSTRT #AND# t #LE# TENDT :
@FOR( MACH( m):
[JUSTN] IDLE(m,t-1)
+ @SUM( JOB(j) | t-PT(m,j) #GE# ARVT(j) #AND# t #LE# DD(j)+1: Z(m,t-PT(m,j),j))
= IDLE(m,t)
+ @SUM( JOB(j) | (DD(j) - PT(m,j) + 1 #GE# t) #AND# ( ARVT( j) #LE# t) : Z(m,t,j));
); !@FOR( MACH;
); ! @FOR(TSLOT;
! The 0/1 variables;
@FOR( MXTXJ(m,t,j):
@BIN( Z(m,t,j));
);
ENDSUBMODEL
CALC:
@SET( "TERSEO", 2);
! Get the start and end of the interesting periods;
TSTRT = @MIN( JOB(j): ARVT(j));
TENDT = @MAX( JOB(j): DD(j));
@SOLVE( ASGSEQ); ! Solve assignment and sequencing problem;
! Display a short report;
! Sort the report by MACH, Start time;
! Set FLAG(m,t,j) = 1 for items still needed to print;
@FOR( MXTXJ(m,t,j):
@IFC( Z(m,t,j) #GT# 0.5:
FLAG(m,t,j) = 1;
@ELSE
FLAG(m,t,j) = 0;
);
);
@WRITE(' Mach- Ready Start Finish Due',@NEWLINE(1));
@WRITE(' ine Job time time time time', @NEWLINE(1));
MORE = 1; ! = 0 when no more lines to print;
@WHILE( MORE:
! Find the lexico smallest (machine, Start time) remaining to print;
ms = 1 + @SIZE( JOB);
ts = 1 + @SIZE(TSLOT);
MORE = 0;
@FOR( MXTXJ(m,t,j) | FLAG(m,t,j):
@IFC( m #EQ# ms #AND# t #LT# ts:
ts = t; ! New smaller start time, same machine;
js = j;
MORE = 1;
);
@IFC( m #LT# ms:
ms = m; ! New smaller machine;
ts = t;
js = j;
MORE = 1;
);
);
@IFC( MORE: ! Did we find another line to print?;
@WRITE( ' ', @FORMAT( MACH(ms), '5s'));
@WRITE( ' ',@FORMAT( JOB(js), '5s'),' ', @FORMAT(ARVT(js),'4.0F'), ' ', @FORMAT(ts,'4.0f'), ' ',
@FORMAT(ts+PT(ms,js)-1,'4.0F'), ' ', @FORMAT(DD(js),'4.0F'), @NEWLINE(1));
FLAG( ms, ts, js) = 0; ! This line is done;
);
);
ENDCALC