#include #include #include "sbtools.h" #include "sbd.h" #include "phases.h" /* * */ long check_feasibility( long m , long *responsible , long *actrelease , long *releases , long *processing_time , long *actdeadline , long *pdc , long *which_machine , long *machine_total ) { long i ; long j ; long jobis ; long u ; long feasibeal ; feasibeal = 1 ; for (i=1;i<=m;i++) { responsible[i] = 0 ; } for (i=1;i<=m;i++) { for (j=1;j<=machine_total[i];j++) { jobis = machine_operations[i][j] ; if ((releases[jobis] + processing_time[jobis] ) > actdeadline[jobis]) { feasibeal = 0 ; /* * find responsible machines */ u = jobis ; while (u != 0) { if (pdc[u] != 0) { if (which_machine[u] == which_machine[pdc[u]]){ responsible[which_machine[u]] = 1 ; } } u = pdc[u] ; } } } } return(feasibeal) ; } /* * if you want to apply phase I then set phase_I = 1 ; * otherwise set phase_I = 0 */ void act_deadl( long *my_act , long *actdeadline , long oper ) { long i ; *my_act = 0 ; for (i=1;i<=oper;i++) if (*my_act < actdeadline[i]) *my_act = actdeadline[i] ; } /* * */ phase_I_and_II( long m , long oper , long my_jobs , long finishing , long *macpred , long *macsucc , long *jobpred , long *jobsucc , long *which_machine , long phase_I , long sequenced_machines , long depthnew , long maxdepth , long *responsible , long *LB , 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 *machine_total , long *position ) { long i , j ; long feasibeal ; long start_seq ; long yes_deleted ; long the_iter ; long how_many_times ; long MKSP_GUESS ; long bottleneck_machine ; long bmksp ; long my_sequenced_machines ; long my_sequence[MAXMACHINES][MAXJOBIS] ; long machine_status[MAXMACHINES] ; long orig_resp [ MAXMACHINES ] ; long deleted [ MAXMACHINES ] ; long best_order [ MAXOPER ] ; long labelled_list [ MAXOPER ] ; long mksp , FEASIBILITY_MODE ; void act_deadl() ; void GLS() ; long LONGEST_PATH() ; long check_feasibility() ; /* * */ my_sequenced_machines = sequenced_machines ; for (i=1;i<=m;i++){ machine_status[i] = machine_sched[i] ; for (j=1;j<=machine_total[i];j++) { my_sequence[i][j] = machine_operations[i][j] ; } } for (i=1 ; i <= m ; i++) orig_resp [ i ] = responsible[i] ; how_many_times = 0 ; start_again: yes_deleted = 0 ; for (i=1;i<=m;i++) { deleted[i] = 0 ; if (orig_resp[i]) { DELETE_MACHINE(i, machine_sched, pdc, scs, machine_total, finishing, macpred, macsucc) ; deleted[i] = 1 ; yes_deleted++ ; } } start_seq = sequenced_machines ; sequenced_machines = sequenced_machines - yes_deleted ; if (phase_I) { FEASIBILITY_MODE = 0 ; } else { FEASIBILITY_MODE = 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, FEASIBILITY_MODE); how_many_times++ ; while ( sequenced_machines < start_seq ) { if (phase_I) { FEASIBILITY_MODE = 0 ; } else { FEASIBILITY_MODE = 1 ; act_deadl(&MKSP_GUESS, actdeadline, oper) ; } if (phase_I) { FIND_RANDOMIZED_BOTTLENECK(1, 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) ; } else { FIND_BOTTLENECK_DELETION(0, 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) ; } SEQUENCE_MACHINE(finishing, macsucc, macpred, bottleneck_machine, machine_sched, best_order, position, machine_total); sequenced_machines++ ; 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); if (phase_I) { feasibeal = check_feasibility(m, responsible, actrelease, releases, processing_time, actdeadline, pdc, which_machine, machine_total) ; if (feasibeal <= 0) { sequenced_machines = my_sequenced_machines ; for (i=1;i<=m;i++){ machine_sched[i] = machine_status[i] ; for (j=1;j<=machine_total[i];j++) { machine_operations[i][j] = my_sequence[i][j] ; } } 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); if (how_many_times < 3) { goto start_again;} else { return ;} } } if (FEASIBILITY_MODE == 0) { MKSP_GUESS = mksp ; } else { act_deadl(&MKSP_GUESS, actdeadline, oper) ; } starti: if (sequenced_machines >= 1 ) { the_iter = 2 * (((long) (log(((double) ( sequenced_machines*my_jobs)))))+1 ) ; FEASIBILITY_MODE = 1 ; if (sequenced_machines > 1) GLS(m, my_jobs, finishing, oper, macpred, macsucc, jobpred, jobsucc, the_iter, 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, FEASIBILITY_MODE, 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, FEASIBILITY_MODE); } } }