Lindo Systems
! Job to Machine Assignment and Sequencing. (MachAsgSeq)
A number of jobs (trucks, airplanes, patients, ...)
arrive over time at a facility (terminal, hospital...).
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, or operating rooms.
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 find
a sequence of jobs on each 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,
hotel guests to hotel rooms, surgical procedures to operating rooms,
and 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, Scheduling,
Operating Room 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, e.g., if DD(j) = 10, must finish in 9 or less;
! 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..40; ! Assume at most 30 minutes in horizon, should be >= max DD;
SFWGT = 0.001; ! Weight applied to minimizing sum of completion times;
JOB = J1..J20;
MACH = A B C D;
! Arrival time or first period in which task can be started;
! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20;
ARVT = 2 1 2 1 1 4 7 8 8 11 8 9 21 9 11 3 6 12 17 22;
! Last processing of a job must be in a period < DD(j);
DD = 13 15 11 11 15 14 27 20 18 17 19 24 28 31 32 9 14 19 23 35;
! Processing time of tasks on machines;
PT = 4 8 5 6 4 3 2 3 5 4 6 5 6 8 6 4 5 6 4 9 ! Mach 1;
5 9 7 7 5 5 1 3 5 5 7 6 7 9 10 5 3 7 6 10 ! Mach 2;
6 9 8 7 5 6 3 3 6 5 7 7 7 9 9 6 7 6 5 11 ! Mach 3;
5 9 8 7 5 5 2 3 4 6 8 8 8 10 5 6 7 7 6 12;! Mach 4;
! Value of doing a specific job on a specific machine;
VAL = 5 8 7 7 6 5 2 1 9 6 4 3 4 6 8 9 9 7 5 6! Mach 1;
6 9 7 7 6 5 3 3 9 7 6 6 6 8 9 7 5 8 3 3! Mach 2;
6 9 7 8 7 5 2 4 9 8 7 7 8 8 9 3 4 5 4 7! Mach 3;
1 4 2 5 9 7 4 5 3 8 3 2 5 9 4 3 3 5 8 9;!Mach 4;
ENDDATA
SETS:
! Key observation: job j can be assigned to/started in time slot t only if
( (ARVT( j) #LE# t) #AND# t + PT(m,j) #LE# DD(j) ) ;
MXTXJ( MACH, TSLOT, JOB) |
( ARVT( &3) #LE# &2) #AND# ( &2 + PT(&1,&3) #LE# DD(&3) ) : Z, FLAG;
ENDSETS
SUBMODEL ASGSEQ:
! Maximize the value of the assignments;
MAX = OBJVALA - SFWGT* SUMFIN;
OBJVALA = @SUM( MXTXJ(m,t,j) : VAL(m,j)*Z(m,t,j));
! Compute sum of finish times;
SUMFIN = @SUM( MXTXJ(m,t,j): (t+PT(m,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 active on 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) | (ARVT(j) #LE# t-PT(m,j)) #AND# t #LE# DD(j): Z(m,t-PT(m,j),j))
= IDLE(m,t)
+ @SUM( JOB(j) | ( ARVT( j) #LE# t) #AND# ( t + PT(m,j) #LE# DD(j)) : 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));
TSTART = @TIME();
@SOLVE( ASGSEQ); ! Solve assignment and sequencing problem;
TEND = @TIME();
! Display a short report;
! Sort the report by MACH, Start time;
! Set FLAG(m,t,j) = 1 for items still needed to print;
@WRITE(' Number jobs assigned= ',@SUM(MXTXJ(m,t,j) | Z(m,t,j) #GT# 0.5: 1),
', out of ',@SIZE(JOB), @NEWLINE(1));
@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('Value of job assignments= ', OBJVALA, @NEWLINE(1));
@WRITE('Sum of finish times= ', SUMFIN, @NEWLINE(2));
@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),'4.0F'), ' ', @FORMAT(DD(js),'4.0F'), @NEWLINE(1));
FLAG( ms, ts, js) = 0; ! This line is done;
);
);
@WRITE(@NEWLINE(1), ' Total solve time= ', @FORMAT(TEND-TSTART,'10.2f'),' seconds.',@NEWLINE(1));
ENDCALC