Seite - 62 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 43 Step4. Compute thenewnumberof just-in-time jobs (nJIT’). IfnJIT’<nJIT (thenewsolution isworse thanthepreviousone), returnboththe lastoperationof JE andtheoperationsof the following jobs to theirpreviouspositions, set Jinitial = J[initial] +1andgoto Step2. Else (thenewsolution isbetter thanorequal to thepreviousone), keep thenewschedule, set Jinitial = J[E] +1andgotoStep2. Algorithm1.Pseudo-codeof timingadjustmentprocedure. Thefirst fourheuristicsproposedareadaptationsof theNEHalgorithm’s insertionmethodand aregiven inAlgorithms2–5.H1andH2employtheEDDruleas the initialorderwhileH3andH4 consider theMSTrule. Another feature is thatH2andH4improveonH1andH3, respectively,by usingneighborhoodsearch in thepartial sequence. Twotypesofneighborhoodsearchareemployed, insertionandpermutation, in thesameway as [20].Givenasequence (orapartial sequence)ofn jobs, its insertionneighborhoodconsistsofall (n−1)2 sequencesobtainedby removinga job fromitsplaceandrelocating it to anotherposition. Thepermutationneighborhoodiscomposedbyalln(n−1)/2sequencesobtainedbypermutingthe positionsof two jobs (seeExample1). Table 2 summarizes the main procedures used in each one of the constructive heuristics. Example1. Consider the initial sequencewith four jobs: {J3, J2, J1, J4}. The insertionneighborhood results in (n−1)2=9sequences: - Initially, inserting thefirst job J3: {J2, J3, J1, J4}, {J2, J1, J3, J4}, {J2, J1, J4, J3}; - Then, inserting thesecond job J2 only in thepositionsnotconsideredyet: {J3, J1, J2, J4}, {J3, J1, J4, J2}; forexample, it isnotnecessary to insert J2 in thefirstpositionbecause thesequenceresulting wasalreadylisted;and - Next, the third job J1 is insertedand, lastly, the fourthone J4: {J1, J3, J2, J4}, {J3, J2, J4, J1}, {J4, J3, J2, J1}, {J3, J4, J2, J1}. Starting again from the initial sequence {J3, J2, J1, J4} of the same example, the permutation neighborhoodresults inn(n−1)/2=6sequences: - First, thefirst two jobsarepermuted: {J2, J3, J1, J4}; thenthefirstandthird jobs: {J1, J2, J3, J4}; and thefirstandfourth jobs: {J4, J2, J1, J3}; - Next, from the initial sequence, the secondand third arepermutated: {J3, J1, J2, J4}; and the secondandfourth: {J3, J4, J1, J2}; and - Lastly, fromthe initial sequence, the thirdandfourth jobsarepermutated: {J3, J2, J4, J1}. HeuristicH1 Step1. Order jobsaccordingto theEDDrule (in thecaseofa tie,use the lower∑pjk). Step2. For thefirst two jobs,apply the timingadjustmentprocedure tofindthebestpartial sequence (betweenthese twopossibilities)with the lowernJIT. Step3. Forh=3ton,do: Keepingtherelativepositionsof the jobsof thepartial sequence, insert thehth jobof theorder definedinStep1 inallpossiblepositionsandapply the timingadjustmentprocedure ineach insertion; consider thenewpartial sequencewith thebestnJIT (in the caseof a tie, use the upperposition). Algorithm2.Pseudo-codeofheuristicH1. HeuristicH2 Step1. Order jobsbytheEDDrule (in thecaseofa tie,use the lower∑pjk). 62