#include #include #include #include #include "aloca.h" #include "sbd.h" #include "gls.h" #include "sbtools.h" #include "glstools.h" #include "longest.h" #include "random.h" /* * */ CRITICAL( long FEASIBILITY_MODE , long MKSP_GUESS , long *actdeadline , long *actrelease , long *listall , long fixed_arcs , long end1 , long sta1 , long *tlist , long *which_machine , long *pdc , long *scs , long *macpred , long *macsucc , long *jobpred , long *jobsucc , long finishing , long *releases , long *tails , long *processing_time , long *fix ) { long u ; long v ; long lbuv ; long OK , cifin ; long taboo ; long they_are_not_fixed ; u = end1 ; while (u != sta1) { v = u ; u = pdc[u] ; if (u) { OK = 1 ; if (which_machine[u] != which_machine[v]) OK = 0 ; if (which_jobg[u] == which_jobg[v]) OK = 0 ; if (((pdc[u] != jobpred[u]) && ( scs[v] != jobsucc[v]))) OK = 0 ; if ((releases[u] == 0) && (pdc[u] == 0) && (scs[v] == macsucc[v])) OK = 0 ; if ((tails [ v ] == 0) && (pdc[u] == macpred[u]) && (scs[v] == finishing)) OK = 0 ; cifin = jobpred[v] ; if (((releases[u]+processing_time[u]) < (releases[cifin]))) OK = 0 ; cifin = jobsucc[u] ; if (((tails[v]+processing_time[v]) < (tails[cifin]))) OK = 0 ; /* if ((tails [ v ] > 0) && (pdc[u] == macpred[u]) && (scs[v] == finishing)) { if ((jobsucc[u] == finishing) && (tails[u] > tails[v])) OK = 0 ; } */ if (OK) { taboo = 0 ; FIXING_TEST(u, v, &they_are_not_fixed, fixed_arcs, fix) ; if (!they_are_not_fixed) taboo = 1 ; if (!taboo) { CALCULATE_lbuv(FEASIBILITY_MODE, MKSP_GUESS, actdeadline, actrelease, u, v, &lbuv, releases, tails, processing_time, macpred, macsucc, jobpred, jobsucc, finishing) ; listall[((*tlist)*5)+0] = 0 ; listall[((*tlist)*5)+1] = u ; listall[((*tlist)*5)+2] = v ; listall[((*tlist)*5)+3] = u ; listall[((*tlist)*5)+4] = lbuv ; (*tlist)++ ; } } } } } /* * */ update1( long i , long *rel , long *tal , long *tpdc , long *processing_time , long *macpred , long *macsucc , long *jobpred , long *jobsucc , long finishing ) { long srel ; srel = rel[i] ; if (rel[jobpred[i]] +processing_time[jobpred[i]] > rel[macpred[i]] +processing_time[macpred[i]]) { rel[i] = rel[jobpred[i]] +processing_time[jobpred[i]] ; tpdc[i] = jobpred[i] ; } else { rel[i] = rel[macpred[i]] +processing_time[macpred[i]] ; tpdc[i] = macpred[i] ; } if (rel[i] < srel) { if ((jobsucc[i] != finishing) && (tpdc[jobsucc[i]] == i)) update1(jobsucc[i], rel, tal, tpdc, processing_time, macpred, macsucc, jobpred, jobsucc, finishing) ; if ((macsucc[i]!= finishing) && (tpdc[macsucc[i]] == i)) update1(macsucc[i], rel, tal, tpdc, processing_time, macpred, macsucc, jobpred, jobsucc, finishing) ; } } /* * */ CPAIRM( long FEASIBILITY_MODE , long MKSP_GUESS , long *actdeadline , long *actrelease , long fixed_arcs , long *u0 , long *v0 , long *found , long *over , long *type , long u , long boundary , long *which_machine , long *pdc , long *scs , long *macpred , long *macsucc , long *jobpred , long *jobsucc , long finishing , long *releases , long *tails , long *processing_time , long *fix ) { long v ; long lbuv ; long taboo ; long OK ; long cifin ; long they_are_not_fixed ; while ( u != boundary){ v = u ; u = pdc[u] ; if (u != 0) { OK = 1 ; if (which_machine[u] != which_machine[v]) OK = 0 ; if (which_jobg[u] == which_jobg[v]) OK = 0 ; if (((pdc[u] != jobpred[u]) && ( scs[v] != jobsucc[v]))) OK = 0 ; if ((releases[u] == 0) && (pdc[u] == 0) && (scs[v] == macsucc[v])) OK = 0 ; if ((tails [ v ] == 0) && (pdc[u] == macpred[u]) && (scs[v] == finishing)) OK = 0 ; cifin = jobpred[v] ; if (((releases[u]+processing_time[u]) < (releases[cifin]))) OK = 0 ; cifin = jobsucc[u] ; if (((tails[v]+processing_time[v]) < (tails[cifin]))) OK = 0 ; /* if ((tails [ v ] > 0) && (pdc[u] == macpred[u]) && (scs[v] == finishing)) { if ((jobsucc[u] == finishing) && (tails[u] > tails[v])) OK = 0 ; } */ if (OK) { taboo = 0 ; FIXING_TEST(u, v, &they_are_not_fixed, fixed_arcs, fix) ; if (!they_are_not_fixed) taboo = 1 ; if (!taboo) { CALCULATE_lbuv(FEASIBILITY_MODE, MKSP_GUESS, actdeadline, actrelease, u, v, &lbuv, releases, tails, processing_time, macpred, macsucc, jobpred, jobsucc, finishing) ; } if ((lbuv <= *over) && (taboo == 0)) { *over = lbuv ; *u0 = u ; *v0 = v ; *found = 1 ; *type = 0 ; } } } } } /* * */ void NNEIGH1( long FEASIBILITY_MODE , long MKSP_GUESS , long *actdeadline , long *actrelease , long fixed_arcs , long *u0 , long *v0 , long *found , long end1 , long sta1 , long *over , long *type , long *pdc , long *scs , long *which_machine , long *releases , long *tails , long *processing_time , long *macpred , long *macsucc , long *jobpred , long *jobsucc , long finishing , long *position , long oper , long *fix ) { long ifin ; long ip ; long endo ; long cifin ; long lbest ; long yes ; long yesi ; long OK ; long they_are_not_fixed ; void CALCULATE_lb1uv() ; ifin = end1 ; endo = 1 ; while (( ifin != sta1 ) && (ifin != 0)) { if (endo == 1) { ip = ifin ; endo = 0 ; } ifin = pdc[ifin] ; if (ifin != 0) { if ((which_machine[ifin] == which_machine[ip] )) { OK = 1 ; if (scs[ip] != jobsucc[ip]) OK = 0 ; if ((tails[ip] == 0) && (scs[ip] == finishing)) OK = 0 ; cifin = jobsucc[ifin] ; /* if ((tails [ ip ] > 0) && (pdc[ifin] == macpred[ifin]) && (scs[ip] == finishing)) { if ((jobsucc[ifin] == finishing) && (tails[ifin] > tails[ip])) OK = 0 ; } */ if (which_jobg[ifin] == which_jobg[ip]) OK = 0 ; if ((pdc[ip] != ifin) && (OK)) { if ((tails[cifin] + processing_time[cifin]) <= (processing_time[ip]+ tails[ip])) { FIXING_TEST(ifin, ip, &they_are_not_fixed, fixed_arcs, fix) ; if (they_are_not_fixed) { yes = 1 ; yesi = scs[ifin] ; while ((yesi != ip) && (yes)) { FIXING_TEST(ifin, yesi, &they_are_not_fixed, fixed_arcs, fix) ; if (!they_are_not_fixed) yes = 0 ; yesi = scs[yesi] ; } if (yes) { CALCULATE_lb1uv(FEASIBILITY_MODE, MKSP_GUESS, actdeadline, actrelease, ip, ifin, &lbest, pdc, scs, which_machine, releases, tails, processing_time, position, macpred, macsucc, jobpred, jobsucc, finishing, oper) ; if (lbest <= *over) { *u0 = ifin ; *v0 = ip ; *found = 1 ; *over = lbest ; *type = 1 ; } } } } } } else { endo = 1 ; } } } } /* * */ FORWARD( long FEASIBILITY_MODE , long MKSP_GUESS , long *actdeadline , long *actrelease , long *listall , long fixed_arcs , long end1 , long sta1 , long *tlist , long *pdc , long *scs , long *which_machine , long *releases , long *tails , long *processing_time , long *macpred , long *macsucc , long *jobpred , long *jobsucc , long finishing , long *position , long oper , long *fix ) { long ifin ; long ip ; long endo ; long cifin ; long lbest ; long OK ; long yes ; long yesi ; long they_are_not_fixed ; void CALCULATE_lb1uv() ; ifin = end1; endo = 1 ; while (ifin != sta1) { if (endo == 1) { ip = ifin ; endo = 0 ; } ifin = pdc[ifin] ; if (ifin != 0){ if (which_machine[ifin] == which_machine[ip] ) { OK = 1 ; if (scs[ip] != jobsucc[ip]) OK = 0 ; if ((tails[ip] == 0) && (scs[ip] == finishing)) OK = 0 ; cifin = jobsucc[ifin]; /* if ((tails [ ip ] > 0) && (pdc[ifin] == macpred[ifin]) && (scs[ip] == finishing)) { if ((jobsucc[ifin] == finishing) && (tails[ifin] > tails[ip])) OK = 0 ; } */ if (which_jobg[ifin] == which_jobg[ip]) OK = 0 ; if ((pdc[ip] != ifin) && (OK)) { if (((tails[cifin]+processing_time[cifin]) <= (processing_time[ip] + tails[ip]))) { FIXING_TEST(ifin, ip, &they_are_not_fixed, fixed_arcs, fix) ; if (they_are_not_fixed) { yes = 1 ; yesi = scs[ifin] ; while ((yesi != ip) && (yes)) { FIXING_TEST(ifin, yesi, &they_are_not_fixed, fixed_arcs, fix) ; if (!they_are_not_fixed) yes = 0 ; yesi = scs[yesi] ; } if (yes){ CALCULATE_lb1uv(FEASIBILITY_MODE, MKSP_GUESS, actdeadline, actrelease, ip, ifin, &lbest, pdc, scs, which_machine, releases, tails, processing_time, position, macpred, macsucc, jobpred, jobsucc, finishing, oper) ; listall[((*tlist)*5)+0] = 1 ; listall[((*tlist)*5)+1] = ifin ; listall[((*tlist)*5)+2] = ip ; listall[((*tlist)*5)+3] = macsucc[ifin] ; listall[((*tlist)*5)+4] = lbest ; (*tlist)++ ; } } } } } else { endo = 1 ; } } } } /* * backward move */ void NNEIGH2( long FEASIBILITY_MODE , long MKSP_GUESS , long *actdeadline , long *actrelease , long fixed_arcs , long *u0 , long *v0 , long *found , long end1 , long sta1 , long *over , long *type , long *pdc , long *scs , long *which_machine , long *releases , long *tails , long *processing_time , long *macpred , long *macsucc , long *jobpred , long *jobsucc , long finishing , long *position , long oper , long *fix ) { long ifin ; long ip ; long endo ; long cifin ; long lbest ; long yes ; long yesi ; long OK ; long they_are_not_fixed ; void CALCULATE_lb2uv() ; ifin = sta1 ; endo = 1 ; while ( ifin != end1) { if (endo == 1) { ip = ifin ; endo = 0 ; } ifin = scs[ifin] ; if (ifin != finishing) { if (which_machine[ifin] == which_machine[ip] ) { OK = 1 ; if ((releases[ip] == 0) && (pdc[ip] == 0)) OK = 0 ; cifin = jobpred[ifin] ; if (pdc[ip] != jobpred[ip]) OK = 0 ; if (which_jobg[ifin] == which_jobg[ip]) OK = 0 ; if ((scs[ip] != ifin) && (OK)) { if ((releases[cifin] + processing_time[cifin]) <= (releases[ip] + processing_time[ip])) { FIXING_TEST(ip, ifin, &they_are_not_fixed, fixed_arcs, fix) ; if (they_are_not_fixed){ yes = 1 ; yesi = pdc[ifin] ; while ((yesi != ip) && (yes)) { FIXING_TEST(yesi, ifin, &they_are_not_fixed, fixed_arcs, fix); if (!they_are_not_fixed) yes = 0 ; yesi = pdc[yesi] ; } if (yes) { CALCULATE_lb2uv(FEASIBILITY_MODE, MKSP_GUESS, actdeadline, actrelease, ip, ifin, &lbest, pdc, scs, which_machine, releases, tails, processing_time, position, macpred, macsucc, jobpred, jobsucc, oper, finishing) ; if (lbest < *over) { *u0 = ip ; *v0 = ifin; *found = 1 ; *over = lbest ; *type = 2 ; } } } } } } else { endo = 1 ; } } } } /* * backward move */ BACKWARD(long FEASIBILITY_MODE , long MKSP_GUESS , long *actdeadline , long *actrelease , long *listall , long fixed_arcs , long end1 , long sta1 , long *tlist , long *pdc , long *scs , long *which_machine , long *releases , long *tails , long *processing_time , long *macpred , long *macsucc , long *jobpred , long *jobsucc , long finishing , long *position , long oper , long *fix ) { long ifin ; long ip ; long endo ; long cifin ; long lbest ; long OK ; long yes ; long yesi ; long they_are_not_fixed ; void CALCULATE_lb2uv() ; ifin = sta1 ; endo = 1 ; while ( ifin != end1) { if (endo == 1) { ip = ifin ; endo = 0 ; } ifin = scs[ifin] ; if (ifin != finishing) { if (which_machine[ifin] == which_machine[ip] ) { OK = 1 ; if ((releases[ip] == 0) && (pdc[ip] == 0)) OK = 0 ; if (pdc[ip] != jobpred[ip]) OK = 0 ; if (which_jobg[ifin] == which_jobg[ip]) OK = 0 ; cifin = jobpred[ifin] ; if ((scs[ip] != ifin) && (OK)) { if (((releases[cifin]+processing_time[cifin]) <= (processing_time[ip] + releases[ip]))) { FIXING_TEST(ip, ifin, &they_are_not_fixed, fixed_arcs, fix) ; if (they_are_not_fixed) { yes = 1 ; yesi = pdc[ifin] ; while ((yesi != ip) && (yes)) { FIXING_TEST(yesi, ifin, &they_are_not_fixed, fixed_arcs, fix); if (!they_are_not_fixed) yes = 0 ; yesi = pdc[yesi] ; } if (yes) { CALCULATE_lb2uv(FEASIBILITY_MODE, MKSP_GUESS, actdeadline, actrelease, ip, ifin, &lbest, pdc, scs, which_machine, releases, tails, processing_time, position, macpred, macsucc, jobpred, jobsucc, oper, finishing) ; listall[((*tlist)*5)+0] = 2 ; listall[((*tlist)*5)+1] = ip ; listall[((*tlist)*5)+2] = ifin ; listall[((*tlist)*5)+3] = macpred[ifin] ; listall[((*tlist)*5)+4] = lbest ; (*tlist)++; } } } } } else { endo = 1 ; } } } } /* * */ void CALCULATE_lb1uv( long FEASIBILITY_MODE , long MKSP_GUESS , long *actdeadline , long *actrelease , long ip , long first , long *lbest , long *pdc , long *scs , long *which_machine , long *releases , long *tails , long *processing_time , long *position , long *macpred , long *macsucc , long *jobpred , long *jobsucc , long finishing , long oper ) { long i ; long job1 ; long joba ; long jobb ; long jobc ; long jobd ; long nelem ; long pos1 , pos2 , jobi ; long mach1 ; long True_Lower_Bound_Wanted , flag ; long *rel ; long *tal ; long *tpdc ; long **stack ; pos1 = position[first] ; pos2 = position[ip] ; flag = alocp((void ***) &stack,(pos2-pos1 + 5)) ; if (!flag) { printf("Memory problems calc ... \n"); exit(1) ; } for (i=0;i<(pos2-pos1+5);i++) { flag = aloci(&stack[i],4) ; } if (!flag) { printf("Memory problems calc ... \n"); exit(1) ; } flag = aloci(&rel,(oper+10)) * aloci(&tal,(oper+10)) * aloci(&tpdc,(oper+10)) ; if (!flag) { printf("Memory problems calc ... \n"); exit(1) ; } True_Lower_Bound_Wanted = 0 ; if (True_Lower_Bound_Wanted) { for (i=0;i<=oper+1;i++) { rel[i] = releases[i] ; tal[i] = tails[i] ; tpdc[i] = pdc[i] ; } } mach1 = which_machine[first] ; nelem = 0 ; for (i=pos1;i<=pos2-1;i++) { nelem++ ; jobi = machine_operations[mach1][i+1] ; stack[nelem][1] = jobi ; if (i != pos1) stack[nelem][2] = macpred[jobi] ; if (i != (pos2-1)) stack[nelem][3] = macsucc[jobi] ; rel[jobpred[jobi]] = releases[jobpred[jobi]] ; tal[jobsucc[jobi]] = tails[jobsucc[jobi]] ; rel[macpred[jobi]] = releases[macpred[jobi]] ; tal[macsucc[jobi]] = tails[macsucc[jobi]] ; } jobi = first ; rel[jobpred[jobi]] = releases[jobpred[jobi]] ; tal[jobsucc[jobi]] = tails[jobsucc[jobi]] ; rel[macpred[jobi]] = releases[macpred[jobi]] ; tal[macsucc[jobi]] = tails[macsucc[jobi]] ; stack[1][2] = macpred[first] ; stack[nelem][3] = first ; nelem++ ; stack[nelem][1] = first ; stack[nelem][2] = ip ; stack[nelem][3] = macsucc[ip] ; /* Calculate estimation of the release times */ for (i=1;i<=nelem;i++) { job1 = stack[i][1] ; jobb = stack[i][2] ; joba = jobpred[job1]; if ((rel[joba] + processing_time[joba]) > ( rel[jobb] + processing_time[jobb] + setup_oper[jobb][job1])) { rel[job1] = rel[joba] + processing_time[joba] ; tpdc[job1] = joba ; } else { rel[job1] = rel[jobb] + processing_time[jobb] + setup_oper[jobb][job1] ; tpdc[job1] = jobb ; } if (rel[job1] < actrelease[job1]) { rel[job1] = actrelease[job1] ; tpdc[job1] = 0 ; } if (True_Lower_Bound_Wanted) { /* if you want always to get the true lower bound then the variable True_Lower_Bound_wanted should be 1 */ if ((job1 == tpdc[jobsucc[job1]]) && (jobsucc[job1] != finishing)) update1(jobsucc[job1], rel, tal, tpdc, processing_time, macpred, macsucc, jobpred, jobsucc, finishing) ; } } /* Calculate estimation of the tails */ for (i=nelem;i>=1;i--) { job1 = stack[i][1] ; jobd = stack[i][3] ; jobc = jobsucc[job1] ; if ((tal[jobc] + processing_time[jobc]) > ( tal[jobd] + processing_time[jobd] + setup_oper[job1][jobd])) { tal[job1] = tal[jobc] + processing_time[jobc] ; } else { tal[job1] = tal[jobd] + processing_time[jobd] + setup_oper[job1][jobd]; } if (FEASIBILITY_MODE) { if ((MKSP_GUESS - actdeadline [ job1 ] ) > tal [ job1 ] ) { tal [ job1 ] = MKSP_GUESS - actdeadline [ job1 ] ; } } } /* Calculate the lower bound */ *lbest = 0 ; for (i=1;i<=nelem;i++) { job1 = stack[i][1] ; if ((rel[job1] + processing_time[job1] + tal[job1] ) > *lbest ) *lbest = rel[job1] + processing_time[job1] + tal[job1] ; } free((char *) rel) ; free((char *) tal) ; free((char *) tpdc) ; for (i=0;i<(pos2-pos1+5);i++) { free((char *) stack[i]) ; } free((char *) stack) ; } /* * */ void CALCULATE_lb2uv( long FEASIBILITY_MODE , long MKSP_GUESS , long *actdeadline , long *actrelease , long ip , long first , long *lbest , long *pdc , long *scs , long *which_machine , long *releases , long *tails , long *processing_time , long *position , long *macpred , long *macsucc , long *jobpred , long *jobsucc , long oper , long finishing ) { long i ; long job1 ; long joba ; long jobb ; long jobc ; long jobd ; long jobi ; long nelem ; long pos1 , pos2 ; long mach1 ; long True_Lower_Bound_Wanted , flag ; long *rel ; long *tal ; long *tscs ; long **stack ; pos1 = position[ip] ; pos2 = position[first] ; flag = alocp((void ***) &stack,(pos2-pos1 + 5)) ; if (!flag) { printf("Memory problems calc ... \n"); exit(1) ; } for (i=0;i<(pos2-pos1+5);i++) { flag = aloci(&stack[i],4) ; } if (!flag) { printf("Memory problems calc ... \n"); exit(1) ; } flag = aloci(&rel,(oper+10)) * aloci(&tal,(oper+10)) * aloci(&tscs,(oper+10)) ; if (!flag) { printf("Memory problems calc ... \n"); exit(1) ; } True_Lower_Bound_Wanted = 0 ; if (True_Lower_Bound_Wanted) { for (i=0;i<=oper+1;i++) { rel[i] = releases[i] ; tal[i] = tails[i] ; tscs[i] = scs[i] ; } } mach1 = which_machine[first] ; nelem = 1 ; for (i=pos1;i<=pos2-1;i++) { nelem++ ; jobi = machine_operations[mach1][i] ; stack[nelem][1] = jobi ; if (i != pos1) stack[nelem][2] = macpred[jobi] ; if (i != (pos2-1)) stack[nelem][3] = macsucc[jobi] ; rel[jobpred[jobi]] = releases[jobpred[jobi]] ; tal[jobsucc[jobi]] = tails[jobsucc[jobi]] ; rel[macpred[jobi]] = releases[macpred[jobi]] ; tal[macsucc[jobi]] = tails[macsucc[jobi]] ; } jobi = first ; rel[jobpred[jobi]] = releases[jobpred[jobi]] ; tal[jobsucc[jobi]] = tails[jobsucc[jobi]] ; rel[macpred[jobi]] = releases[macpred[jobi]] ; tal[macsucc[jobi]] = tails[macsucc[jobi]] ; stack[2][2] = first ; stack[nelem][3] = macsucc[first] ; stack[1][1] = first ; stack[1][2] = macpred[ip] ; stack[1][3] = ip ; /* Calculate estimation of the release times */ for (i=1;i<=nelem;i++) { job1 = stack[i][1] ; jobb = stack[i][2] ; joba = jobpred[job1] ; if ((rel[joba] + processing_time[joba]) > ( rel[jobb] + processing_time[jobb] + setup_oper[jobb][job1] )) { rel[job1] = rel[joba] + processing_time[joba] ; } else { rel[job1] = rel[jobb] + processing_time[jobb] + setup_oper[jobb][job1] ; } if (rel[job1] < actrelease[job1]) rel[job1] = actrelease[job1] ; } /* Calculate estimation of the tails */ for (i=nelem;i>=1;i--) { job1 = stack[i][1] ; jobd = stack[i][3] ; jobc = jobsucc[job1]; if ((tal[jobc] + processing_time[jobc]) > ( tal[jobd] + processing_time[jobd] + setup_oper[job1][jobd])) { tal[job1] = tal[jobc] + processing_time[jobc] ; tscs[job1] = jobc ; } else { tal[job1] = tal[jobd] + processing_time[jobd] + setup_oper[job1][jobd] ; tscs[job1] = jobd ; } if (True_Lower_Bound_Wanted) { /* if you want always to get the true lower bound then the variable True_Lower_Bound_wanted should be 1 */ if ((job1 == tscs[jobpred[job1]]) && (jobpred[job1] != 0)) updatet(jobpred[job1], rel, tal , tscs, processing_time, macpred, macsucc, jobpred, jobsucc) ; } if (FEASIBILITY_MODE) { if ((MKSP_GUESS - actdeadline [ job1 ] ) > tal [ job1 ] ) { tal [ job1 ] = MKSP_GUESS - actdeadline [ job1 ] ; } } } /* Calculate the lower bound */ *lbest = 0 ; for (i=1;i<=nelem;i++) { job1 = stack[i][1] ; if ((rel[job1] + processing_time[job1] + tal[job1] ) > *lbest ) *lbest = rel[job1] + processing_time[job1] + tal[job1] ; } free((char *) rel) ; free((char *) tal) ; free((char *) tscs) ; for (i=0;i<(pos2-pos1+5);i++) { free((char *) stack[i]) ; } free((char *) stack) ; } /* * */ updatet( long i , long *rel , long *tal , long *tscs , long *processing_time , long *macpred , long *macsucc , long *jobpred , long *jobsucc ) { long stal ; stal = tal[i] ; if ((tal[jobsucc[i]] +processing_time[jobsucc[i]]) > tal[macsucc[i]] +processing_time[macsucc[i]]) { tal[i] = tal[jobsucc[i]] +processing_time[jobsucc[i]] ; tscs[i] = jobsucc[i] ; } else { tal[i] = tal[macsucc[i]] +processing_time[macsucc[i]] ; tscs[i] = macsucc[i] ; } if (tal[i] < stal) { if ((jobpred[i] != 0) && (tscs[jobpred[i]] == i)) updatet(jobpred[i], rel, tal, tscs, processing_time, macpred, macsucc, jobpred, jobsucc) ; if ((macpred[i] != 0) && (tscs[macpred[i]] == i)) updatet(macpred[i], rel, tal, tscs, processing_time, macpred, macsucc, jobpred, jobsucc) ; } } /* * */ CALCULATE_lbuv( long FEASIBILITY_MODE , long MKSP_GUESS , long *actdeadline , long *actrelease , long u , long v , long *lbuv , long *releases , long *tails , long *processing_time , long *macpred , long *macsucc , long *jobpred , long *jobsucc , long finishing ) { long av , cv , bv , dv , au , cu , bu , du ; long r1u , r1v , q1u , q1v ; av = jobpred[v] ; cv = jobsucc[v] ; bv = macpred[v] ; dv = macsucc[v] ; au = jobpred[u] ; cu = jobsucc[u] ; bu = macpred[u] ; du = macsucc[u] ; r1v = releases[av] + processing_time[av] ; if (r1v < (releases[bu] + processing_time[bu] + setup_oper[bu][v]) ) { r1v = releases[bu] + processing_time[bu] + setup_oper[bu][v]; } q1u = tails[cu] + processing_time[cu] ; if (q1u < (tails[dv]+processing_time[dv] + setup_oper[u][dv])) { q1u = tails[dv] + processing_time[dv] +setup_oper[u][dv] ; } if (FEASIBILITY_MODE){ if ((MKSP_GUESS-actdeadline [ u ] ) > q1u) { q1u = MKSP_GUESS - actdeadline [ u ] ; } } q1v = tails[cv] + processing_time[cv] ; if (q1v < ( q1u + processing_time[u] + setup_oper[v][u])) { q1v = q1u + processing_time[u] + setup_oper[v][u] ; } if (FEASIBILITY_MODE) { if ((MKSP_GUESS-actdeadline [ v ] ) > q1v) { q1v = MKSP_GUESS - actdeadline [ v ] ; } } r1u = releases[au] + processing_time[au] ; if (r1u < ( r1v + processing_time[v] + setup_oper[v][u] ) ) { r1u = r1v + processing_time[v] +setup_oper[v][u] ; } *lbuv =r1v + processing_time[v] + q1v ; if ( *lbuv < r1u + processing_time[u] + q1u ){ *lbuv = r1u + processing_time[u] + q1u ; } } /* * */ void SWAP( long i , long j , long *which_machine , long *POS , long *position , long *machine_total , long *my_first , long *my_last , long *LIST , long *jobsucc , long *macsucc) { long pos1 , pos2 ; long mach1 ; long ko1 , ko2 ; mach1 = which_machine[i] ; pos1 = position[i] ; pos2 = position[j] ; machine_operations[mach1][pos1] = j ; machine_operations[mach1][pos2] = i ; ko1 = pos1 - 1 ; if (ko1 <= 0) ko1 = 1; ko2 = pos2 + 1 ; if (ko2 >= machine_total[mach1]) ko2 = machine_total[mach1] ; swift(i, j, LIST, POS, jobsucc, macsucc) ; *my_first = POS[j] ; *my_last = POS[i] ; } /* * */ MOVE_FORWARD( long i , long j , long *which_machine , long *POS , long *position , long *machine_total , long *my_first , long *my_last , long *LIST , long *jobsucc , long *macsucc ) { long i1 , u1 ; long pos1 , pos2 ; long mach1 ; long ko1 , ko2 , try ; mach1 = which_machine[i] ; pos1 = position[i] ; pos2 = position[j] ; /* successor of u before the interchange in the machine sequence */ try = machine_operations[mach1][(pos1+1)] ; for (i1=pos1;i1= machine_total[mach1]) ko2 = machine_total[mach1] ; *my_first = POS[try] ; *my_last = POS[i] ; } /* * */ MOVE_BACKWARD( long i , long j , long *which_machine , long *POS , long *position , long *machine_total , long *my_first , long *my_last , long *LIST , long *jobsucc , long *macsucc ) { long i1 , u1 ; long mach1 ; long pos1 , pos2 ; long ko1 , ko2 , try ; mach1 = which_machine[i] ; pos1 = position[i] ; pos2 = position[j] ; try = machine_operations[mach1][(pos2-1)] ; for (i1=pos2;i1>pos1;i1--) { u1 = machine_operations[mach1][i1-1] ; machine_operations[mach1][i1]=machine_operations[mach1][i1-1] ; swift(u1, j, LIST, POS, jobsucc, macsucc) ; } machine_operations[mach1][pos1] = j ; ko1 = pos1 - 1 ; if (ko1 <= 0) ko1 = 1 ; ko2 = pos2 + 1 ; if (ko2 >= machine_total[mach1]) ko2 = machine_total[mach1] ; *my_first = POS[j] ; *my_last = POS[try] ; } /* * */ FIXING_TEST( long u , long v , long *they_are_not_fixed , long fixed_arcs , long *fix ) { long i ; *they_are_not_fixed = 1 ; for (i = 0 ; i < fixed_arcs ; i++) { if ((fix[(i*2)] == u) && (fix[((i*2) + 1)] == v)) { *they_are_not_fixed = 0 ; return ; } } /* * new test for fixed arcs by carlier's propositions */ /* for (i=0;i< new_fixed_arcs;i++) { if ((fixed_carlier[i][0] == u) && (fixed_carlier[i][1] == v)) { *they_are_not_fixed = 0 ; return; } } */ /* * If you want to apply tabu search replace the previous * procedure with this one */ /* new test to incorporate tabu search */ /* #ifdef TABU_MODE new_tabu = TABU_SIZE ; if (fixed_arcs < TABU_SIZE) new_tabu = 0 ; for (i = fixed_arcs ; i >= (fixed_arcs - new_tabu) ; i--) { if ((fix[(i*2)] == u) && (fix[((i*2) + 1)] == v)) { *they_are_not_fixed = 0 ; return ; } } #endif */ } /* * */ SELECT_RANDOMLY_WITH_WEIGHTS( long *solution_number , long *keep_makespans , long *machine_sched , long *machine_total , long *position , long *machine_stored , long oper , long m ) { long i , j , SELECTED ; long kk , ll ; long my_number ; long flag ; double y , aa , bb , tweight , cweight , cbefore ; long *the_order ; double *weights ; double random_number() ; flag = aloci(&the_order,MAXMACHINES) * alocd(&weights,MAXMACHINES) ; if (!flag) { printf("Memory problems - Select ... \n") ; exit(1) ; } my_number = *solution_number ; SORT_KEEP_MAKESPANS(my_number, the_order, keep_makespans) ; aa = 1.0 ; bb = 1.0 ; for (i=1;i<=*solution_number;i++) { j = the_order[i] ; /* printf("j = %ld , mksp = %ld \n",j,keep_makespans[j]) ; */ aa = 2.0 * aa ; bb = 3.0 * bb ; weights[j] = (1.0 / aa) ; } tweight = 0.0 ; for (i=1;i<=*solution_number;i++) tweight = tweight + weights[i] ; for (i=1;i<=*solution_number;i++) { j = the_order[i] ; weights[j] = (weights[j] / tweight) ; } tweight = 0.0 ; for (i=1;i<=*solution_number;i++) tweight = tweight + weights[i] ; /* num = rand() ; y = num / RAND_MAX ; */ y = random_number() ; /* printf("%f %f tweight = %f \n",dseed,y,tweight) ; */ y = y * tweight ; cweight = 0.0 ; SELECTED = 0 ; for (i=1;i<=*solution_number;i++) { cbefore = cweight ; cweight = cweight + weights[i] ; /* printf("y %f , [%f, %f] \n",y,cbefore,cweight) ; */ if ((cbefore <= y) && (y <= cweight)) { SELECTED = i ; i = *solution_number + 100 ; } } /* printf("solut = %ld , SELECTED = %ld \n",*solution_number,SELECTED) ; */ if (SELECTED == 0) {printf("Error in selection \n") ; exit(1) ; } /* printf("Makespan %ld \n",keep_makespans[SELECTED]) ;*/ kk = 0 ; for (i=1;i<=m;i++) { for (j=1;j<=machine_total[i];j++) { machine_operations[i][j] = machine_stored[((SELECTED-1)*oper) + kk] ; kk++ ; } } /* * delete this selection and merge the array machine_stored */ kk = (SELECTED * oper ) ; ll = (SELECTED - 1)*oper ; for (i = SELECTED ; i < *solution_number ; i++) { for (j=0; j < oper; j++) { machine_stored [ ll ] = machine_stored [ kk ] ; kk++ ; ll++ ; } } for (i=SELECTED ; i < *solution_number ; i++) keep_makespans [ i ] = keep_makespans [ i + 1 ] ; *solution_number = *solution_number - 1 ; free((char *) the_order) ; free((char *) weights) ; } /* * */ void MODIFY_SOLUTION( long mksp , long depth , long sequenced_machines , long *improvement , long *best_schedule , long *machine_total , long m , long *UB ) { if (mksp < *UB) { *improvement = 1 ; *UB = mksp ; /* printf("Improvement = %ld , improving directions \n",*UB,impr_dire) ; */ HOLD_SOLUTION(best_schedule, machine_total, m) ; } } /* * */ doublecheck( long *machine_sched , long *POS , long *operations , long *machine_total , long m , long my_jobs ) { long i , j , u , v ; for (i=1;i<=my_jobs;i++) { for (j=1;j= POS[v]) printf("Error on job positions %ld %ld ... %ld %ld %ld \n", u,v,i,POS[u],POS[v]) ; } } for (i=1;i<=m;i++) { if (machine_sched[i] == 1) { for (j=1;j= POS[v]) printf("Error on machine positions %ld %ld ... %ld %ld %ld \n", u,v,i,POS[u],POS[v]) ; } } } } /* * store the current best schedule */ HOLD_SOLUTION( long *best_schedule , long *machine_total , long m ) { long i,j ; long k ; k = 0 ; for (i=1;i<=m;i++) { for (j=1;j<=machine_total[i];j++) { best_schedule [ k ] = machine_operations[i][j] ; k++ ; } } } /* * */ STORE_IMPROVED_SOLUTION( long m , long *improved_schedule , long *machine_total , long oper ) { long i,j ; long k ; k = 0 ; for (i=1;i<=m;i++){ for (j=1;j<=machine_total[i];j++) { improved_schedule [ k ] = machine_operations[i][j] ; k++ ; } } } /* * */ STORE_SOLUTION_INDEX( long mksp , long *INDEX , long *solution_number , long *keep_makespans , long *iterbest , long *machine_total , long m , long *machine_stored , long oper ) { long i,j ; long kk ; long tsolutions ; long tmak ; long MAXIMUM_KEPT_SOLUTIONS ; (*solution_number)++ ; MAXIMUM_KEPT_SOLUTIONS = 10 ; if (*solution_number > MAXIMUM_KEPT_SOLUTIONS) { *solution_number = MAXIMUM_KEPT_SOLUTIONS ; } else { *INDEX = *solution_number ; } kk = 0 ; for (i=1;i<=m;i++) { for (j=1;j<=machine_total[i];j++) { machine_stored[((*INDEX-1)*oper)+kk] = machine_operations[i][j] ; kk++ ; } } keep_makespans[*INDEX] = mksp ; tsolutions = *solution_number ; tmak = 0 ; for (i=1;i<=tsolutions;i++) if (keep_makespans[i] > tmak) { tmak = keep_makespans[i] ; *INDEX = i ; } *iterbest = tmak ; if (*solution_number < MAXIMUM_KEPT_SOLUTIONS) *iterbest = ((long) RAND_MAXI) ; } /* * */ RESTORE_HOLD_SOLUTION( long *best_schedule , long *machine_total , long m ) { long i , j ; long k ; k = 0 ; for (i=1;i<=m;i++) { for (j=1;j<=machine_total[i];j++) { machine_operations[i][j] = best_schedule [ k ] ; k++ ; } } } /* * */ void EXPL_NEIG( long FEASIBILITY_MODE , long MKSP_GUESS , long *actdeadline , long *actrelease , long fixed_arcs , long *u0 , long *v0 , long *type , long *found , long depth , long end1 , long sta1 , long *pdc , long *scs , long *which_machine , long *releases , long *tails , long *processing_time , long *macpred , long *macsucc , long *jobpred , long *jobsucc , long finishing , long *position , long oper , long *fix ) { long over ; void NNEIGH1() ; void NNEIGH2() ; *found = 0 ; *u0 = 0 ; *v0 = 0 ; over = ((long) RAND_MAXI) ; NNEIGH1(FEASIBILITY_MODE, MKSP_GUESS, actdeadline, actrelease, fixed_arcs, u0, v0, found, end1, sta1, &over, type, pdc, scs, which_machine, releases, tails, processing_time, macpred, macsucc, jobpred, jobsucc, finishing, position, oper, fix); NNEIGH2(FEASIBILITY_MODE, MKSP_GUESS, actdeadline, actrelease, fixed_arcs, u0, v0, found, end1, sta1, &over, type, pdc, scs, which_machine, releases, tails, processing_time, macpred, macsucc, jobpred, jobsucc, finishing, position, oper, fix) ; CPAIRM(FEASIBILITY_MODE, MKSP_GUESS, actdeadline, actrelease, fixed_arcs, u0, v0, found, &over, type, end1, sta1, which_machine, pdc, scs, macpred, macsucc, jobpred, jobsucc, finishing, releases, tails, processing_time, fix); /* printf("bound = %ld , type = %ld \n",over,*type) ; */ } /* #define ALKIS_TEST */ /* * node() generates nodes of the neighborhood tree */ void node( long iteration , long *machine_stored , long fixed_arcs , long u , long v , long v1 , long ctype , long makespan_before , long depth , long depth_in_improvement , long MKSP_GUESS , long sequenced_machines , long *INDEX , long *status , long *iterbest_low , long *improvement , long *solution_number , long depthnew , long maxdepth , long *keep_makespans , long *best_schedule , long *improved_schedule , long *iterbest , long *machine_sched , long *actrelease , long *releases , long *tails , long *moddeadline , long *actdeadline , long *processing_time , long *operations , long *pdc , long *scs , long *LIST , long *POS , long *fix , long *machine_total , long *position , long *jobpred , long *jobsucc , long *macpred , long *macsucc , long finishing , long oper , long m , long *which_machine , long my_jobs , long *UB , long FEASIBILITY_MODE ) { long i , i1 , i2 , j2 , ij , j , av , v01 , cu ; long kk ; long makespan_after ; long type , u0 , v0 , found , lbr , rbr ; long REL_BEFORE , TAIL_BEFORE ; long REL_BEFORE_u ; long succ_u ; long temp0 , temp1 , temp2 , temp3 , temp4 , posi , maxi ; long tlist_inside ; long MY_DEPTH ; long u_next , v_next , v1_next , type_next ; long ALPHA , ALPHA1 , IMBROS ; long old_rel, old_tail ; long tlist , WIP , FLOWTI , jji ; long my_first , my_last ; long *labelled_list ; long the_first , the_last , flag ; long *critical_oper ; long *releases_stored ; long *tails_stored ; long *pdc_stored; long *scs_stored ; long *LIST_stored ; long *node_schedule; long *CURRENT_LIST ; long *listall ; long calculations() ; void MODIFY_SOLUTION() ; void EXPL_NEIG() ; void SWAP() ; /* for (i=1;i<=*solution_number;i++) printf("%ld-",keep_makespans[i]) ; printf("\n") ; */ flag = aloci(&critical_oper,(oper+10)) * aloci(&releases_stored,(oper+10)) * aloci(&tails_stored,(oper+10)) * aloci(&pdc_stored,(oper+10)) * aloci(&scs_stored,(oper+10)) * aloci(&LIST_stored,(oper+10)) * aloci(&labelled_list,(oper+10)) * aloci(&node_schedule,(oper+10)) * aloci(&CURRENT_LIST,(5*MAXOPER+10)) * aloci(&listall,(5*MAXOPER+10)) ; if (!flag) { printf("Memory problem node() ... \n") ; exit(1) ; } KAPPA = 4 ; if (my_jobs > m) KAPPA = 5 ; lbr = 0 ; rbr = 0 ; if (!u) { makespan_after = makespan_before ; goto START ; } av = jobpred[v]; cu = jobsucc[u] ; REL_BEFORE = releases[v] ; REL_BEFORE_u = releases[u] ; succ_u = macsucc[u] ; old_rel = releases [ succ_u ] ; old_tail = tails [ succ_u ] ; TAIL_BEFORE = tails[u] ; v01 = 0 ; if ((ctype == 0) || (ctype == 2)) { if ((releases[av] + processing_time[av]) > releases[u]) lbr = 1 ; if (FEASIBILITY_MODE) { if (actrelease[v] > releases[u]) rbr = 1 ; } } if ((ctype == 0) || (ctype == 1)) { if ((tails[cu] + processing_time[cu]) > tails[v]) rbr = 1 ; if (FEASIBILITY_MODE) { if ((MKSP_GUESS - actdeadline[u]) > tails[v]) rbr = 1 ; } } if (!ctype) { my_adjacent = my_adjacent + 1.0 ; my_moves = my_moves + 1.0 ; SWAP(u, v, which_machine, POS, position, machine_total, &my_first, &my_last, LIST, jobsucc, macsucc) ; } if (ctype == 1) { my_forward = my_forward + 1.0 ; my_moves = my_moves + 1.0 ; v1 = macsucc[u]; MOVE_FORWARD(u, v, which_machine, POS, position, machine_total, &my_first, &my_last, LIST, jobsucc, macsucc) ; } if (ctype == 2) { my_backward = my_backward + 1.0 ; my_moves = my_moves + 1.0 ; v1 = macpred[v]; MOVE_BACKWARD(u, v, which_machine, POS, position, machine_total, &my_first, &my_last, LIST, jobsucc, macsucc) ; } SEQUENCE_MACHINE_STANDARD(which_machine[v], machine_sched, machine_total, position, m, finishing, macpred, macsucc) ; // printf("MKSP_GUESS %ld - feasibility_mode = %ld depth = %ld\n",MKSP_GUESS, FEASIBILITY_MODE, // depth) ; makespan_after = LONGEST_PATH(m, my_jobs, oper, finishing, jobpred, jobsucc, macpred, macsucc, MKSP_GUESS, machine_sched, actrelease, releases, tails, moddeadline, actdeadline, processing_time, operations, pdc, scs, LIST, POS, machine_total, labelled_list, FEASIBILITY_MODE); // printf("Makespan before - Makespan after = %ld - %ld , depth = %ld\n", // makespan_before , makespan_after, depth) ; /* calculations(m, my_jobs, 0 , // my_first finishing, // my_last MKSP_GUESS, actrelease, actdeadline , releases, processing_time, tails, moddeadline, pdc, scs, LIST, POS, operations, macpred, macsucc, jobpred, jobsucc, finishing, oper, FEASIBILITY_MODE) ; */ if (sequenced_machines == m) { // calculate WIP WIP = 0 ; for (i=1;i<=m;i++) { for (j=1;j<=machine_total[i];j++) { jji = machine_operations[i][j] ; WIP = WIP + releases[jji] - releases[jobpred[jji]] - processing_time[jobpred[jji]] ; } } if (WIP < BEST_WIP) { BEST_WIP = WIP ; BEST_MKSP_WIP = makespan_after ; } FLOWTI = 0 ; for (i=1;i<=my_jobs;i++) { jji= job_operations[i][operations[i]] ; FLOWTI = FLOWTI + releases[jji] + processing_time[jji] ; } if (FLOWTI < BEST_FLOWTIME) { BEST_FLOWTIME = FLOWTI ; BEST_MKSP_FLOW = makespan_after ; } // printf("Wip = %ld ,Makespan = %ld \n",WIP, makespan_after) ; } fix[(fixed_arcs*2)] = v ; fix[((fixed_arcs*2)+1)] = u ; fixed_arcs++ ; if ((ctype == 1) || (ctype == 0) ) { if (releases[v] > (REL_BEFORE - processing_time[u])) { lbr = 1 ; } } if ((ctype == 2) || (ctype == 0)) { if (tails[u] > (TAIL_BEFORE - processing_time[v])) { rbr = 1 ; } } if (makespan_before < makespan_after) { non_improving = non_improving + 1.0 ; if (lbr) moves_lbr = moves_lbr + 1.0 ; if (rbr) moves_rbr = moves_rbr + 1.0 ; if (ctype == 1) non_imp_f = non_imp_f + 1.0 ; if (ctype == 2) non_imp_b = non_imp_b + 1.0 ; } else { improving_moves = improving_moves + 1.0 ; } START: if ((ctype > 0) && (makespan_after >= makespan_before )) { av = v ; cu = u ; } if (makespan_after < *UB) { /* * status =1 means that there is an improvement in the upper bound */ /* * this is the new idea of Balas * develop the neighborhood from the root node when you * have an improvement of the upper bound */ /*#ifdef BALAS_NEW_IDEA if (sequenced_machines == m) { depth_in_improvement = 0 ; fixed_arcs = 0 ; } #endif */ *status = 1; *improvement = 1 ; *iterbest = makespan_after ; STORE_IMPROVED_SOLUTION(m, improved_schedule, machine_total, oper) ; } if (depth >= depthnew) { if (*status >= 3) { *solution_number = 0 ; *iterbest = ((long) RAND_MAXI) ; } if ((*status >= 2) && (makespan_after <= *iterbest)) { /* * status = 2 means that the level that you need has been * reached and you can start storing solutions. */ *status = 2 ; STORE_SOLUTION_INDEX(makespan_after, INDEX, solution_number, keep_makespans, iterbest, machine_total, m, machine_stored, oper) ; } } else { if (*status >= 3) { /* * status =3 means that we are in the first neighborhood tree * and the level has not been reached then * we select the best node (makespan) * to start the second neighborhood tree. */ if (makespan_after <= *iterbest_low ) { *iterbest_low = makespan_after ; if (iteration == 1) { *status = 3 ; } STORE_IMPROVED_SOLUTION(m, improved_schedule, machine_total, oper) ; } } } MODIFY_SOLUTION(makespan_after, depth, sequenced_machines, improvement, best_schedule, machine_total, m, UB) ; if (depth >= maxdepth) goto returni ; if (depth_in_improvement == 0) ALPHA1 = KAPPA ; if (depth_in_improvement == 1) ALPHA1 = 2 ; /* modification alkis KAPPA / 2 ; */ if (depth_in_improvement >= 2) { goto guideposts ; } if (ALPHA1 <=1) { ALPHA1 = 1 ; goto guideposts ; } MY_DEPTH = fixed_arcs ; kk = 0 ; for (i=1;i<=m;i++) { for (j=1;j<=machine_total[i];j++) { node_schedule[kk] = machine_operations[i][j] ; kk++ ; } } for (i=0;i<=(oper+1);i++) { LIST_stored[i] = LIST[i] ; releases_stored[i] = releases[i] ; tails_stored[i] = tails[i] ; pdc_stored[i] = pdc[i] ; scs_stored[i] = scs[i] ; } lbr = 1 ; rbr = 1 ; if ((makespan_after <= makespan_before ) || (lbr && rbr)) { the_first = pdc [ finishing ] ; the_last = scs [ 0 ] ; } else { if (lbr) { the_first = v ; the_last = scs [ 0 ] ; trials = trials + 1.0 ; } if (rbr) { the_first = pdc [ finishing ] ; the_last = u ; trials = trials + 1.0 ; } } tlist = 0 ; FORWARD(FEASIBILITY_MODE, MKSP_GUESS, actdeadline, actrelease, listall, fixed_arcs, the_first, the_last, &tlist, pdc, scs, which_machine, releases, tails, processing_time, macpred, macsucc, jobpred, jobsucc, finishing, position, oper, fix) ; BACKWARD(FEASIBILITY_MODE, MKSP_GUESS, actdeadline, actrelease, listall, fixed_arcs, the_first, the_last, &tlist, pdc, scs, which_machine, releases, tails, processing_time, macpred, macsucc, jobpred, jobsucc, finishing, position, oper, fix) ; CRITICAL(FEASIBILITY_MODE, MKSP_GUESS, actdeadline, actrelease, listall, fixed_arcs, the_first, the_last, &tlist, which_machine, pdc, scs, macpred, macsucc, jobpred, jobsucc, finishing, releases, tails, processing_time, fix) ; for (i=0;i < tlist;i++) { maxi = ((long) RAND_MAXI) ; for (j=i;j< tlist;j++) { if (listall[(j*5)+4] < maxi) { maxi = listall[(j*5)+4] ; posi = j ; } } temp0 = listall[(i*5)+0] ; temp1 = listall[(i*5)+1] ; temp2 = listall[(i*5)+2] ; temp3 = listall[(i*5)+3] ; temp4 = listall[(i*5)+4] ; listall[(i*5)+0] = listall[(posi*5)+0] ; listall[(i*5)+1] = listall[(posi*5)+1] ; listall[(i*5)+2] = listall[(posi*5)+2] ; listall[(i*5)+3] = listall[(posi*5)+3] ; listall[(i*5)+4] = listall[(posi*5)+4] ; listall[(posi*5)+0] = temp0 ; listall[(posi*5)+1] = temp1 ; listall[(posi*5)+2] = temp2 ; listall[(posi*5)+3] = temp3 ; listall[(posi*5)+4] = temp4 ; } IMBROS = 0 ; for (i=0 ; i < tlist;i++) { if (listall[(i*5)+4] < makespan_after) IMBROS++ ; CURRENT_LIST[(i*5)+0] = listall[(i*5)+0] ; CURRENT_LIST[(i*5)+1] = listall[(i*5)+1] ; CURRENT_LIST[(i*5)+2] = listall[(i*5)+2] ; CURRENT_LIST[(i*5)+3] = listall[(i*5)+3] ; CURRENT_LIST[(i*5)+4] = listall[(i*5)+4] ; } ALPHA = ALPHA1 ; tlist_inside = tlist ; if (tlist_inside > ALPHA) tlist_inside = ALPHA ; /* printf("depth %ld , fixed_arcs = %ld \n", depth_in_improvement,fixed_arcs) ; */ for (i = 0;i < tlist_inside;i++){ for (ij=0;ij 0))) { SELECT_RANDOMLY_WITH_WEIGHTS(&solution_number, keep_makespans, machine_sched, machine_total, position, machine_stored, oper, m) ; } SEQUENCE_FIXED_MACHINES(machine_sched, machine_total, position, m, finishing, macpred, macsucc) ; /* for (i=1;i<=m;i++) { for (j=1;j<=machine_total[i];j++) { printf("%ld-",machine_operations[i][j]) ; } printf("\n") ; } */ } endi: #ifdef ALL_RESULTS STOPTIME(4) ; #endif RESTORE_HOLD_SOLUTION(best_schedule, machine_total, m) ; SEQUENCE_FIXED_MACHINES(machine_sched, machine_total, position, m, finishing, macpred, macsucc) ; mksp = LONGEST_PATH(m, my_jobs, oper, finishing, jobpred, jobsucc, macpred, macsucc, MKSP_GUESS, machine_sched, actrelease, releases, tails, moddeadline, actdeadline, processing_time, operations, pdc, scs, LIST, POS, machine_total, labelled_list, FEASIBILITY_MODE) ; repeato = 0 ; if ((FEASIBILITY_MODE) && (repeato == 1)) { if (UB <= MKSP_GUESS) { guess_modified++ ; MKSP_GUESS = mksp - 1 ; /* printf("max iter = %ld , MKSP_GUESS = %ld , Fea = %ld\n", max_iter,MKSP_GUESS,FEASIBILITY_MODE) ; */ goto starti ; } } free((char *) machine_stored) ; free((char *) best_schedule) ; free((char *) improved_schedule) ; free((char *) fix) ; free((char *) labelled_list) ; free((char *) keep_makespans) ; }