Seite - 68 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 43 Table4.Overallperformancerankings (RPD)ofproposedheuristics inrelation toEMforGroup1and to thebest foundsolutionforGroup2. Group1 H6 H5 H2 H1 H4 H3 H9 H8 H10 H7 0.2 0.4 1.1 1.2 3.7 7.0 9.6 16.2 21.1 41.7 Group2 H6 H5 H2 H1 H4 H3 H9 H10 H8 H7 0.2 0.3 0.6 2.4 7.0 11.9 31.4 61.4 68.1 76.6 Theresults fromH6weresimilar to those fromH5whichrankedsecondforoverallperformance with RPDs of 0.4% inGroup 1 and 0.3% inGroup 2, as shown in Table 4. Both these heuristics consideredtheEDDruleas the initialorderanditerativelyplacedthefirst tardy jobat theendof the sequence.However,H6alsoemployedinsertionandpermutationneighborhoodsearches. Therefore, it canbeseenthat,althoughthis improvementphaseprovidedbetterperformance,H6hadalready producedverygoodresultsbefore theneighborhoodsearches (explainedbythebehaviorofH5). Followingtherankings,H2andH1werethirdandfourth, respectively,andbothexhibitedsimilar behaviorbyconsideringtheEDDruleas the initialorderandthenemployingthe insertionmethod toconstruct thesequence. Thedifferencebetweenthemis thatH2employsneighborhoodsearches beforeattemptingto insert thenewjob in thepartial sequence. Inaddition, itmaybenoted inTable4 that therankings forGroups1and2werealmost thesame, with thesoleexceptionof the inversionbetweenheuristicsH8andH10 ineighthandninthplaces. Anotherobservation is that, in thefiveworstmethods, thedeviations inGroup1weremuchlower thanthose inGroup2which indicatedthat there isagreaterdispersionofsolutionquality formedium andlarge instances,ascanbeseen inFigure2. TheworstmethodwasH7which considered theMSTrule as the initial order and iteratively placed thefirst tardy jobat the endof the sequence. Although it is very similar toH5, as theonly differencebetweenthemwas in their initialorders (theEDDrulewasused inH5), thediscrepancies in their resultswerequitesignificant. Thisdemonstratedthat,of the twooptionsusedfor the initial rule, theEDDwasalwaysmoreadvantageous thantheMST,aswasobvious foreverypairofheuristics whichwereonlydifferentiatedbytheserules, that is,H1andH3,H2andH4,H5andH7,H6andH8, andH9andH10. Tables5–8providedetailedaverageresults for the instancesaccordingto thegroupandsize for eachheuristic consideringdifferentnumbersof jobsandmachines. As thenumberof jobsgrows, the fourbestmethods,H6,H5,H2andH1,hadrelativelystable performances forGroups1 (Table5) andGroup2 (Table6),withvery lowRPDvalues (below1.5). TheexceptionwasH1forGroup2(Table6),whichhaddecreasingrelativedeviationsrangingfrom 3.9%with15 jobs to0.6%with100. TheotherheuristicshadincreasingRPDvalueswith increasing numbersof jobs, exceptH7andH8forGroup2whichhaddecreasingvalues for instanceswithupto 100 jobs. Furthermore,H3showedaslightdecrease in instanceswith15 to50 jobs,andanincrease in thosewith80and100. Table5.Comparisonofperformances (RPD)ofheuristicsbynumberof jobs forGroup1. n H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 5 1.0 1.1 5.4 1.8 0.4 0.2 29.1 5.5 5.7 12.7 6 1.2 0.9 7.4 3.4 0.4 0.1 35.8 9.4 7.3 17.7 7 1.2 1.2 6.4 3.4 0.4 0.2 43.9 16.2 8.9 20.0 8 1.5 1.0 7.8 4.8 0.3 0.3 49.3 21.8 11.6 25.3 10 1.2 1.1 8.3 4.9 0.4 0.3 50.6 28.3 14.5 29.8 68