Seite - 69 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 43 Table6.Comparisonofperformances (RPD)ofheuristicsbynumberof jobs forGroup2. n H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 15 3.9 1.5 10.9 6.4 0.7 0.4 59.6 41.3 26.2 40.1 20 3.6 1.1 9.4 6.2 0.5 0.4 69.4 55.7 28.3 47.5 30 3.3 0.7 8.9 6.7 0.3 0.2 77.7 69.0 30.5 57.5 50 2.1 0.3 8.5 6.7 0.3 0.1 84.6 79.6 33.4 69.3 80 1.0 0.1 8.8 7.3 0.1 0.1 89.4 86.3 34.8 76.3 100 0.6 0.0 25.1 8.7 0.2 0.1 78.9 76.6 35.1 77.6 In termsof thenumbersofmachines,ascanbeseen inTables7and8, theresults indicate, ineach group,highstabilitywithrelativelysmallvariations in theirRPDamplitudes. Thismaysuggest that thenumberofmachineswasnotarelevant factor inperformances for theproblemaddressed. Table7.Comparisonofperformances (RPD)ofheuristicsbynumberofmachines forGroup1. m H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 2 0.3 0.5 7.1 3.7 0.2 0.1 42.2 16.5 7.5 20.8 3 0.9 0.8 7.4 3.7 0.3 0.1 42.3 16.7 9.6 21.3 5 2.4 1.9 6.7 3.5 0.7 0.5 40.7 15.5 11.8 21.1 Table8.Comparisonofperformances (RPD)ofheuristicsbynumberofmachines forGroup2. m H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 5 0.5 0.3 12.2 7.2 0.2 0.1 78.0 69.8 28.6 61.8 10 2.1 0.7 13.0 7.1 0.4 0.2 75.9 68.0 30.7 61.3 15 3.1 0.6 11.0 7.1 0.3 0.2 76.9 68.2 32.5 61.3 20 3.9 0.8 11.6 6.6 0.5 0.3 75.5 66.4 33.7 61.1 Table9presentseachgroup’sdeviations for the fourdefinedscenarios,varyingthevaluesofT andRduedatefactors. Theseresultswereconsistentwiththoseobtainedfromthepreviousanalysesof rankingmethods,withH6presenting thebest result followedbyH5. Theresultsofdifferent scenarios suggest thatvariations in the tardiness factorandduedaterangedidnotexertanyrelevant influence. It is interesting tonote the twotopheuristics,H6andH5,obtained identical results forbothgroups in Scenarios2and4characterizedbytheirwideduedateranges. That is,whenthe intervalbetweendue dateswas large,neighborhoodsearchesdidnotprovide improvements. Table9.Performances (RPD)ofheuristicsbygroupandscenario inrelation toEMforGroup1andto thebest foundsolutionforGroup2. Scenario H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 Group1 1 0.9 0.8 8.7 4.6 0.4 0.3 42.2 16.5 10.0 20.8 2 1.0 0.7 4.7 2.2 0.2 0.2 45.7 19.2 4.3 20.0 3 1.9 1.7 9.3 5.1 0.8 0.5 39.3 14.7 15.0 22.1 4 1.0 1.0 5.5 2.7 0.1 0.1 39.8 14.5 9.2 21.5 Group2 1 1.7 0.7 15.0 8.9 0.4 0.2 76.3 68.1 39.4 61.6 2 1.6 0.5 7.8 4.5 0.1 0.1 78.6 71.3 13.8 62.0 3 3.7 1.0 15.2 9.4 0.7 0.4 75.1 65.4 43.0 60.9 4 2.5 0.3 9.7 5.3 0.1 0.1 76.3 67.6 29.3 61.0 5.3. Experiment2:Qualityof theHeuristicSolutions inRelation to theOptimalSolution In thesecondpartof thecomputationalexperimentation, thequalityofeachheuristic solution wasmeasuredby theRPDin relation to theoptimal solutionprovidedbysolving the instancesof mathematicalmodelbyCPLEX.TheRPDiscalculatedbyExpression(14),wherenbestJIT is theoptimal solutiongivenbyCPLEX. 69