Page - 70 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 43 Theoptimalityof theCPLEXsolutionwasprovenfor the6000 instancesofGroup1. Theanalysis ofquality theheuristics’ results inrelation to thoseoptimalsolutions,using95%confidence intervals of theaverageRPDs, isdepicted inFigure3. Figure3. Comparisonsofperformancesofheuristics in relation to thoseofmodel (95%confidence intervalsofaverageRPD). It is remarkable that thevaluesofgraphs inFigure2a (Group1)andFigure3areverysimilar. Table10presents rankingsof thesolutionqualityof theheuristics, i.e., thevaluesof theRPDof the optimalsolutions. Table10.Overallperformancerankings (averageRPD)ofheuristics inrelation tooptimalsolutionfor instances inGroup1. H6 H5 H2 H1 H4 H3 H9 H8 H10 H7 RPD 0.6 0.8 1.4 1.6 4.0 7.4 10.0 16.6 21.4 41.9 Table10showsthesamerankingandvaluesveryclosetotheonespresentedinTable4forrelative comparisonsofGroup1,whichvalidatedandreinforcedtheresults fromthepreviousanalyses. It is important tohighlight theexcellentperformanceof thebestheuristic (H6) thathadadeviationfrom theoptimalsolutionof just0.6%whichmeant that itprovidedanear-optimalsolution. Of the6000 instancesoptimallysolved,H6reachedtheoptimalsolution in5830cases (97.2%of instances)and, in theother170 instances, thedifferencebetweenits resultandtheoptimalsolution wasonlyone just-in-timejobin168casesandtwojust-in-timejobs intwoothercases. It isalsorelevant toemphasize that theaveragerunningtimesofH6were0.1msand0.39s for the instances inGroups1 and2, respectively. Accordingto thepreviouscomparativeanalysis, theresults forH5andH6wereverycloseand H2andH1alsoachievedsignificantperformances. Thisconfirmedthat theEDDwasbetter thanthe MSTrule for the instancesconsideredandtheprocedurebasedonHodgson’sapproach(usedinH6 andH5)outperformedthe insertionmethodofNEH(applied inH2andH1). Similarly, inall casesof eachpairofheuristics, thosewhichappliedaneighborhoodsearchproducedimprovedresults. Another interestingobservation is that theenumerationmethod,asexplained inSection5.3,did notguarantee theoptimalsolution in thecaseofaflowshopwith just-in-time jobs.Of the instances optimallysolved, thedeviations fromtheenumerationmethodwereonaverage0.4%,asexpected, withanaveragerunningtimeof1.48s. TheaveragerunningtimeofCPLEXwas199.88s (3.33min). Giventhedifficulties toproveoptimality, forGroup2,onlyone instanceperclasswassolvedby CPLEXwith theCPUtimewas limitedto3600s. Thus,96mediumandlarge instanceswereexecuted. 70