 ```! 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 ```