Seite - 63 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 43 Step2. For thefirst two jobs,apply the timingadjustmentprocedure tofindthebestpartial sequence (betweenthese twopossibilities)with the lowernJIT. Step3. Forh=3ton,do: Addthehth joboforderdefinedinStep1 in the lastpositionof thepartial sequence; Considering the insertionneighborhoodwith (h− 1)2partial sequences andapplying the timingadjustmentprocedure,determine thatwith thebestnJIT; Fromthebest solutionobtainedsofar, consideringthepermutationneighborhoodwithh(h− 1)/2partial sequencesandapplying the timingadjustmentprocedure,determine thatwith the bestnJIT. Algorithm3.Pseudo-codeofheuristicH2. HeuristicH3 Step1.Order jobsbytheMSTrule (in thecaseofa tie,use the lower∑pjk). Steps2and3. Thesameas inheuristicH1. Algorithm4.Pseudo-codeofheuristicH3. HeuristicH4 Step1.Order jobsbytheMSTrule (in thecaseofa tie,use the lower∑pjk). Steps2and3. Thesameas inheuristicH2. Algorithm5.Pseudo-codeofheuristicH4. Thenext fourheuristics,H5,H6,H7andH8,employ ideas fromtheclassicHodgson’salgorithm whichprovides theoptimal solution forminimizing thenumberof tardy jobs ina single-machine problem.TheyarepresentedinAlgorithms6–9.Again, thefirst twoconsider theEDDruleandthe last twotheMST. Inaddition,H6andH8are improvedversionsofH5andH7, respectively,whichuse neighborhoodsearchmethodsat theendofexecution. HeuristicH5 Step1. Order jobsbytheEDDrule (in thecaseofa tie,use the lower∑pjk). Step2. Apply the timingadjustmentprocedure. Step3. Identify thefirst tardy job in thesequence (JT). If therearenotardy jobs,STOP. Step4. Replace/Place job JTas thefinal in thesequenceandgotoStep2. Algorithm6.Pseudo-codeofheuristicH5. HeuristicH6 Step1. Order jobsbytheEDDrule (in thecaseofa tie,use the lower∑pjk). Step2. Apply the timingadjustmentprocedure. Step3. Identify thefirst tardy job in thesequence (JT). If therearenotardy jobs,STOP. Step4. Replace job JT as thefinal in thesequence. Step5. Considering the insertionneighborhoodwith (h− 1)2partial sequences andapplying the timingadjustmentprocedure,determine thatwith thebestnJIT; and From the best solution obtained so far, considering the permutation neighborhoodwith h(h−1)/2partial sequencesandapplyingthetimingadjustmentprocedure,determinethat with thebestnJIT. Algorithm7.Pseudo-codeofheuristicH6. HeuristicH7 Step1.Order jobsbytheMSTrule (in thecaseofa tie,use the lower∑pjk). 63