Page - 64 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 43 Steps2–4.Thesameas inheuristicH5. Algorithm8.Pseudo-codeofheuristicH7. HeuristicH8 Step1.Order jobsbytheMSTrule (tie-breakbythe lower∑pjk). Steps2–5. Thesameas inheuristicH6. Algorithm9.Pseudo-codeofheuristicH8. For the last two heuristics, H9 (Algorithm 10) uses the EDD rule as the initial order and H10 (Algorithm 11) the MST rule, both adopting a different form of neighborhood search, the forward/backwardprocedure. Thenewprocedure re-insert one job at a time in the last position inasequencebyconsideringthebest solutionfoundsofar,andtheniterativelyre-insert the last job inall otherpositions retaining theonewith thebestnJIT. This corresponds toadiverseway to test neighborsolutions (seeExample2). Example 2. Consider again the sequence: {J3, J2, J1, J4}. For position h=1, the first job J3 is replaced in the last position; if the newsolution is improved, thenewsequence is kept (andalso thevalueofh=1),otherwise, thepreviousone is recovered(andthehis incremented). Thus, if the currentsequence is {J2, J1, J4, J3}, thenthenewfirst job J2 is replacedinthe lastpositionandthetest is repeated for {J1, J4, J3, J2}. Consideringnowthat thenewsolution isnotbetter than theprevious one, thesequence iskept {J2, J1, J4, J3}andh=h+1=2. In thenextstep, thesecond job(i.e., theone in thehthposition) is replaced in the lastpositionandthe test is redone. This forwardprocedure is repeateduntil the (n−1)thposition. Then,abackwardprocedure isapplied, reinserting the last job in allpreviouspositions,andsoon. HeuristicH9 Step1. Order jobsbytheEDDrule (in thecaseofa tie,use the lower∑pjk). Step2. Apply the timingadjustmentprocedure. Step3. Seth=1.Whileh<n,do (fromposition1 ton−1): Forwardprocedure: replace the hth jobdefined inStep1 in the last positionof thepartial sequenceandapplythetimingadjustmentprocedure. If thenewnJIT isbetterthantheprevious one,keepthenewschedule (andthehvalue);otherwise,gobackto thepreviousoneandset h=h+1. Step4. Seth=n.Whileh>1,do(fromthe lastpositionto thesecond): Backwardprocedure:Replace thehth job inall thepreviouspositionsandapplythetiming adjustmentprocedureconsidering thebest solution found. If anewbest solution is found, keepthenewschedule (andthehvalue);otherwise,goback to theprevioussolutionandseth =h−1. Step5. STOP. Algorithm10.Pseudo-codeofheuristicH9. HeuristicH10 Step1.Order jobsbytheMSTrule (in thecaseofa tie,use the lower∑pjk). Steps2–5. Thesameas inheuristicH9. Algorithm11.Pseudo-codeofheuristicH10. 64