#include #include #include "sbd.h" #include "sb.h" #include "aloca.h" #include "sbtools.h" #include "sodl.h" #include "longest.h" long machine_idle[MAXMACHINES] ; long idle[MAXMACHINES][2*MAXJOBIS+2] ; long c_t ; /* * Shifting bottleneck procedure - SB_GLS1 */ SB_GLS1( long *which_job, long MY_RUN , long *feasible_problems , double *SB_GLS1_bound , double *SB_GLS1_cpu , long *LB , long *my_seq_machines , long m , long my_jobs , long finishing , long *macsucc , long *macpred , long *jobsucc , long *jobpred , long *which_machine , long oper , long *tphase_I , long *sphase_I , long *sphase_II , long depthnew , long maxdepth , 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 *position , long *machine_total , long deadlines , long *Upper_Bound , long *introd , long *bottleneck_order , long *lateness ) { long OKEY, OKEY1, my_lateness ; long i, j ,kk ; long MKSP_GUESS , sequenced_machines , bottleneck_machine ; long jj , jj1 , bmksp , FEASIBILITY_MODE , mksp ; long one_machine_problem , negative_number ; long flag , ii , jji ; long tproci ; long *best_order ; long *labelled_list ; long *critical ; long *responsible; long FLOWTIME , WIP_MACHINE , WIP ; long LONGEST_PATH() ; long deleted[MAXMACHINES] ; long check_feasibility() ; long FIND_LATENESS() ; void GLS() ; void act_deadl() ; flag = aloci(&best_order,MAXOPER) * aloci(&labelled_list,MAXOPER) * aloci(&critical,MAXMACHINES) * aloci(&responsible,MAXMACHINES) ; /* * STARTTIME(1) ; */ // printf("In SBGLS1 ... \n") ; MKSP_GUESS = 0 ; for (i=1;i<=oper;i++) { // printf("Deadline = %ld\n",actdeadline[i]) ; if (actdeadline[i] > MKSP_GUESS) MKSP_GUESS = actdeadline[i] ; } *Upper_Bound = ((long) RAND_MAXI) ; 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, 1); FEASIBILITY_MODE = 0 ; sequenced_machines= *my_seq_machines ; Total_sequenced_machines = 0 ; // printf("Current makespan = %ld , sequenced_machines = %ld \n", // mksp,sequenced_machines) ; negative_number = 0 ; for (i=0;i<=finishing;i++) { if (moddeadline [ i ] < 0) { negative_number = 1; } } if (negative_number) { /* * if you have negative numbers then solve the bottleneck * problem as miminization of maximum lateness */ /* MKSP_GUESS = mksp ; */ act_deadl(&MKSP_GUESS, actdeadline, oper) ; FEASIBILITY_MODE = 1; 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, 1) ; } BEST_WIP = ((long) RAND_MAXI) ; BEST_FLOWTIME = ((long) RAND_MAXI) ; while ( sequenced_machines < m ) { if (deadlines) { one_machine_problem = 1 ; } else { one_machine_problem = 0 ; } if (FEASIBILITY_MODE) { one_machine_problem = 0 ; } init_makespan = 0 ; if (LONGRUN == 0 ) { FIND_BOTTLENECK(one_machine_problem, m, &bottleneck_machine, &bmksp, machine_sched, actrelease, releases, processing_time, tails, moddeadline, best_order, machine_total, which_machine, position, oper, jobsucc, macsucc, finishing, labelled_list, jobpred, macpred) ; } if (LONGRUN == 1) { FIND_RANDOMIZED_BOTTLENECK(one_machine_problem, m, &bottleneck_machine, &bmksp, machine_sched, actrelease, releases, processing_time, tails, moddeadline, best_order, machine_total, which_machine, position, oper, jobsucc, macsucc, deleted, finishing, labelled_list, jobpred, macpred) ; } // printf("Sequence machine %ld \n",bottleneck_machine) ; SEQUENCE_MACHINE(finishing, macsucc, macpred, bottleneck_machine, machine_sched, best_order, position, machine_total) ; bottleneck_order[ bottleneck_machine ] = m - sequenced_machines ; sequenced_machines++ ; Total_sequenced_machines++ ; introd [ sequenced_machines ] = bottleneck_machine ; if (sequenced_machines == 1) *LB = bmksp ; if ((FEASIBILITY_MODE) && (sequenced_machines==1)) *LB = 0 ; // printf("Bottleneck machine = %ld , makespan = %ld \n",bottleneck_machine,bmksp) ; fflush(stdout) ; 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, 1); // printf("Bottleneck makespan = %ld , Makespan after intro %ld \n",bmksp,mksp) ; /* MKSP_GUESS = mksp ; */ if (deadlines) { FEASIBILITY_MODE = 1 ; } else { FEASIBILITY_MODE = 0 ; } SB_GLS2(j, which_job, SB_GLS1_bound, SB_GLS1_cpu, LB, m, my_jobs, finishing, macsucc, macpred, jobsucc, jobpred, which_machine, oper, tphase_I, sphase_I, sphase_II, depthnew, maxdepth, machine_sched, actrelease, releases, tails, moddeadline, actdeadline, processing_time, operations, pdc, scs, LIST, POS, position, machine_total, deadlines, Upper_Bound, my_seq_machines, introd, bottleneck_order, lateness) ; 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, 1) ; // printf("Makespan after reoptimization: %ld\n",mksp) ; if (sequenced_machines == m) { // printf("Makespan= %ld\n",mksp) ; // calculate WIP WIP = 0 ; tproci = 0 ; for (i=1;i<=m;i++) { WIP_MACHINE = 0 ; for (j=1;j<=machine_total[i];j++) { jji = machine_operations[i][j] ; WIP = WIP + releases[jji] - releases[jobpred[jji]] - processing_time[jobpred[jji]] ; tproci = tproci + processing_time[jji] ; WIP_MACHINE = WIP_MACHINE + releases[jji] - releases[jobpred[jji]] - processing_time[jobpred[jji]] ; } // printf("MAchine = %ld , WIP = %ld\n",i,WIP_MACHINE) ; } // printf("Wip = %ld ,Makespan = %ld \n",WIP, mksp) ; // printf("Utilization rate = %f \n", // (((double) (tproci)) / ((double) (m*mksp)))) ; // printf("Total Processing time = %ld\n",tproci) ; FLOWTIME = 0 ; for (i=1;i<=my_jobs;i++) { ii = job_operations[i][operations[i]] ; FLOWTIME = FLOWTIME + releases[ii] + processing_time[ii] ; } // printf("Flowtime = %ld \n",FLOWTIME) ; for (i=1;i<=m;i++){ critical[i] = 0 ; if (machine_sched[i] == 1) { for (j=1;j mksp) { printf("Error in FIND_CRITICAL_MACHINE() \n") ; exit(1) ; } if ((releases[ii] + processing_time[ii]+setup_oper[ii][jj]+ processing_time[jj]+tails[jj]) == mksp) { critical[i] = 1 ; } } } // printf("Machine = %ld , Critical = %ld \n",i,critical[i]) ; } // printf("Schedule with best Flowtime = %ld has makespan = %ld\n",BEST_FLOWTIME,BEST_MKSP_FLOW) ; // printf("Schedule with best WIP = %ld has makespan = %ld \n",BEST_WIP,BEST_MKSP_WIP) ; } FEASIBILITY_MODE = 0 ; /* reset feasibility mode */ /* if (deadlines){ feasibeal = check_feasibility(m, responsible, actrelease, releases, processing_time, actdeadline, pdc, which_machine, machine_total) ; if (feasibeal <= 0) { negative_number = 0 ; for (i=0;i<=finishing;i++) { if (moddeadline [ i ] < 0) { negative_number = 1; } } if (negative_number) { MKSP_GUESS = mksp ; act_deadl(&MKSP_GUESS, actdeadline, oper) ; FEASIBILITY_MODE = 1; 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, 1) ; } } } */ } /* 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, 0); if (deadlines){ feasibeal = check_feasibility(m, responsible, actrelease, releases, processing_time, actdeadline, pdc, which_machine, machine_total) ; if (feasibeal <= 0) { *tphase_I = *tphase_I + 1 ; act_deadl(&MKSP_GUESS, actdeadline, oper) ; } } */ 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, 1); if (deadlines) { my_lateness = FIND_LATENESS(m, actdeadline, releases, processing_time, machine_total) ; } OKEY = 0 ; if (!deadlines) { *Upper_Bound = mksp ; OKEY = 1 ; } else { *lateness = my_lateness ; *Upper_Bound = mksp ; OKEY = 1 ; } if (OKEY) { kk = 0 ; for (i=1;i<=m;i++) { for (j=1;j<=machine_total[i];j++) { BEST_SCHEDULE[kk] = machine_operations[i][j] ; kk++ ; } } } OKEY1 = 0 ; if (!deadlines) { if (mksp < UB_global) { UB_global = mksp ; OKEY1 = 1 ; } } else { if (lateness_global > 0) { if (*lateness < lateness_global) { lateness_global = *lateness ; UB_global = mksp ; OKEY1 = 1 ; } else { if (*lateness = lateness_global) { if (mksp < UB_global) { UB_global = mksp ; OKEY1 = 1 ; } } } } else { if ((mksp < UB_global) && (*lateness == 0)) { OKEY1 = 1 ; UB_global = mksp ; } } } if (OKEY1) { for (j=1;j<=oper;j++) { best_solution[j] = releases[j] ; best_tails[j] = tails[j] ; } kk = 0 ; for (i=1;i<=m;i++) { machine_idle[i] = 0 ; c_t = 0 ; for (j=1;j<=machine_total[i];j++) { BEST_SCHEDULE_global[kk] = machine_operations[i][j] ; ii = machine_operations[i][j] ; if (releases[ii] != c_t) { (machine_idle[i])++ ; idle[i][(2*machine_idle[i]) - 1] = c_t ; idle[i][(2*machine_idle[i])] = releases[ii] ; } c_t = releases[ii]+processing_time[ii] ; if ((j==machine_total[i]) && (c_t != mksp)) { (machine_idle[i])++ ; idle[i][(2*machine_idle[i]) - 1] = c_t ; idle[i][(2*machine_idle[i])] = mksp ; } kk++ ; } } for (i=1;i<=m;i++) best_intro [ i ] = introd [ i ] ; } if ((deadlines) && ( *lateness <=0)){ feasible_problems[MY_RUN] = feasible_problems[MY_RUN] + 1 ; } /* STOPTIME(1) ; CURRENT_TIME = (((double) USERTIME(1)) / 1000.0) ; */ /* for (i=0;i position[fixed_carlier[i][1]]) { printf("Wrong sequencing. \n") ; } } */ times(&cpu); //qqq tiMer2 = cpu.tms_utime; //qqq CPUtiMe = (double) (tiMer2 - tiMer1) / (double) HZ; //qqq printf("SBD_GLS1: Makespan=%ld, Max Lateness=%ld\n", *Upper_Bound,*lateness) ; if (*Upper_Bound < BESTGMAKESPAN) BESTGMAKESPAN = *Upper_Bound ; if (*lateness < BESTGLATENESS) BESTGLATENESS = *lateness ; printf("@ %3d: %ld %ld %ld %ld %.2f (#: jobs, machs, span, late, CPU)\n", _n_+1, my_jobs, m, *Upper_Bound, *lateness, CPUtiMe); //qqq fflush(stdout) ; /* if (*Upper_Bound == *LB) printf("Optimality proved \n") ; */ jj=0 ; jj1 = 1 ; /* printf("Upper Bound %ld \n",*Upper_Bound) ; for (j=1;j<=oper;j++) { printf("%5ld ",best_solution[j]) ; jj=jj+1 ; if (jj == (operations[jj1])) { jj = 0 ; jj1 = jj1+1 ; printf("\n") ; } } */ kk=0 ; fprintf(output_file,"%ld \n",lateness_global) ; for (i=1;i<=m;i++) { fprintf(output_file,"%ld %ld\n",i,machine_total[i]) ; for (j=1;j<=machine_total[i];j++) { fprintf(output_file,"%ld %ld %ld\n",which_job[BEST_SCHEDULE[kk]], best_solution[BEST_SCHEDULE[kk]] , ((int) (best_solution[BEST_SCHEDULE[kk]] + processing_time[BEST_SCHEDULE[kk]])) ) ; kk++ ; } } SB_GLS1_bound [ MY_RUN ] = ((double) *Upper_Bound) ; /* SB_GLS1_cpu [ MY_RUN ] = (((double) USERTIME(1)) / 1000.0) ; */ *my_seq_machines = sequenced_machines ; free((char *) best_order) ; free((char *) labelled_list) ; free((char *) critical) ; free((char *) responsible) ; } /* * SB_GLS2() */ SB_GLS2( long MY_RUN , long *which_job, double *SB_GLS2_bound , double *SB_GLS2_cpu , long *LB , long m , long my_jobs , long finishing , long *macsucc , long *macpred , long *jobsucc , long *jobpred , long *which_machine , long oper , long *tphase_I , long *sphase_I , long *sphase_II , long depthnew , long maxdepth , 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 *position , long *machine_total , long deadlines , long *Upper_Bound , long *my_seq_machines , long *introd , long *bottleneck_order , long *lateness ) { long i , j , ij ; long OKEY , reoptimized_machine ; long solve_one_machine ; long FIND_LATENESS() ; long check_feasibility() ; long bmksp ; long my_total , theta ; long mksp ; long jobs ; long optimal_makespan ; long MKSP_GUESS ; long sequenced_machines ; long total_repeat , make_infeasible , make_total , standard_feasible ; double critical_diff ; double critical_non_diff ; double non_critical_diff ; double non_critical_non_diff ; long flag ; long *labelled_list ; long *best_order ; long *node_schedule ; long *STORED_SCHEDULE ; long *critical ; long *responsible ; long *best_schedule ; void GLS() ; long LONGEST_PATH() ; long mksp_before , mksp_start ; long impr ; long trials; flag = aloci(&best_schedule,MAXOPER) ; MKSP_GUESS = 0 ; for (i=1;i<=oper;i++) { if (actdeadline[i] > MKSP_GUESS) MKSP_GUESS = actdeadline[i] ; } flag = aloci(&best_order,MAXOPER) * aloci(&labelled_list,MAXOPER) * aloci(&node_schedule,MAXOPER) * aloci(&STORED_SCHEDULE,MAXOPER) * aloci(&critical,MAXMACHINES) * aloci(&responsible,MAXMACHINES) ; *Upper_Bound = 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, 1) ; UB_global = *Upper_Bound ; for (j=1;j<=oper;j++) { best_solution[j] = releases[j] ; best_tails[j] = tails[j] ; } /* STARTTIME(1) ; */ sequenced_machines = *my_seq_machines ; impr = 1 ; trials = 0 ; while (impr) { trials++ ; 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, 1) ; FIND_CRITICAL_MACHINES( 1 , m , critical , machine_sched , releases , processing_time , tails , machine_total , mksp , pdc , which_machine , finishing ) ; impr = 0 ; for (i=1;i<=Total_sequenced_machines;i++) { reoptimized_machine = introd[i] ; mksp_before = 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, 1) ; if (i==1) mksp_start = mksp_before ; FIND_CRITICAL_MACHINES( 0 , m , critical , machine_sched , releases , processing_time , tails , machine_total , mksp_before , pdc , which_machine , finishing ) ; HOLD_SOLUTION(best_schedule, machine_total, m) ; total_reopt++ ; // printf("Reoptimize machine = %ld\n",reoptimized_machine) ; DELETE_MACHINE(reoptimized_machine, machine_sched, pdc, scs, machine_total, 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, 1) ; if (deadlines) { solve_one_machine = 1 ; } else { solve_one_machine = 0 ; } bmksp = 0 ; init_makespan = 1 ; STORE_SOLVE_PROBLEMS(reoptimized_machine, &jobs , actrelease, releases, processing_time, tails, moddeadline, machine_total, which_machine, position, oper, jobsucc, macsucc, finishing, labelled_list, jobpred, macpred, &optimal_makespan, solve_one_machine, &bmksp, 0) ; init_makespan = 0 ; for (ij=1;ij<=machine_total[reoptimized_machine];ij++) best_order[ij] = order[ij] ; SEQUENCE_MACHINE(finishing, macsucc, macpred, reoptimized_machine, machine_sched, best_order, position, machine_total) ; // printf("After reoptimization ... \n") ; 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, 1) ; if (mksp < mksp_start) { // printf("From %ld improve to %ld\n",mksp_before,mksp) ; impr = 1; if (sequenced_machines < m) { if (trials >=3) impr = 0 ; } } if (mksp > mksp_before) { // printf("Not improving --- restore ... \n") ; RESTORE_HOLD_SOLUTION(best_schedule, machine_total, m) ; SEQUENCE_FIXED_MACHINES(machine_sched, machine_total, position, m, finishing, macpred, macsucc) ; /* printf("Error because of the delays .... before %ld after %ld \n", mksp_before, mksp) ; */ impr =0 ; } *Upper_Bound = 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, 1) ; UB_global = *Upper_Bound ; for (j=1;j<=oper;j++) { best_solution[j] = releases[j] ; best_tails[j] = tails[j] ; } } } // theta = 10 ; *Upper_Bound = 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, 1) ; mksp_before = *Upper_Bound; //printf("Upper Bound before GLS = %ld ", *Upper_Bound) ; my_total = 0 ; for (i=1;i<=m;i++) { if (machine_sched[i]) { my_total= my_total+ machine_total[i] ; } } if (LONGRUN == 0) { theta= 2 * (((long) ( log(((double) (my_total))) / log(2) ) ) +1); } else { theta= 4 * (((long) ( log(((double) (my_total))) / log(2) ) ) +1); if (m == sequenced_machines) { theta= 10 * (((long) ( log(((double) (my_total))) / log(2) ) ) +1); } } GLS(m, my_jobs, finishing, oper, macpred, macsucc, jobpred, jobsucc, theta, MKSP_GUESS, sequenced_machines, depthnew, maxdepth, LB, machine_sched, actrelease, releases, tails, moddeadline, actdeadline, processing_time, operations, pdc, scs, LIST, POS, machine_total, position, which_machine, 1, 1) ; *Upper_Bound = 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, 1) ; //printf("- after GLS = %ld \n", *Upper_Bound) ; // UB_global = *Upper_Bound ; if (mksp_before < *Upper_Bound ) { printf("Error in GLS \n") ; } critical_diff = 0.0 ; critical_non_diff = 0.0 ; non_critical_diff = 0.0 ; non_critical_non_diff = 0.0 ; OKEY = 1 ; standard_feasible = 0 ; make_total = 0 ; make_infeasible = 0 ; total_repeat = 0 ; 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, 1) ; /* printf(" GLS = %ld \n",mksp) ; */ /* * if deadlines are present check the feasibility of the solution * if the solution is not feasible then restore the previous solutuion */ free((char *) best_order) ; free((char *) labelled_list) ; free((char *) node_schedule) ; free((char *) STORED_SCHEDULE) ; free((char *) critical) ; free((char *) responsible) ; }