Seite - 71 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 43 For22 instances,no integersolutionwasfoundor themodelprovidedasolutionwithzerovalue. In mostcases, theheuristic solutionsweremuchbetter thanthe lowerboundgivenbyCPLEX, leadingto verynegativeRPD,ascanbeobservedinTable11. Table11.Overallperformance (averageRPD)ofheuristics inrelation to lowerboundgivenbyCPLEX bynumberof jobs for instancesofGroup2. n H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 15 6.5 1.0 10.3 6.9 1.0 1.0 56.7 41.1 28.2 36.8 20 −5.0 −6.5 4.0 −2.8 −8.8 −8.8 66.5 49.6 23.1 41.1 30 −49.0 −52.5 −38.0 −40.1 −52.0 −52.0 68.4 57.2 −7.4 38.5 80 −1080.2 −1082.0 −1001.7 −1032.6 −1082.0 −1082.0 −13.5 −93.2 −764.4 −251.9 100 −1276.7 −1276.7 −990.8 −1159.3 −1276.7 −1276.7 −460.6 −518.8 −865.0 −276.1 Themorenegative is theRPDofaheuristic, thebetter is its result inrelationto the lowerbound. It couldbenotedthateventheworstheuristic (H7)providedresults thatwerebetter thanthe lower boundgivenbyCPLEX.Theseresultsconfirmallprevious inferences. Thecoincidenceof theresults forH5andH6isremarkable, suggestingthatneighborhoodsearchesdonot improvethesolutionof mediumandlarge instances. 5.4. ComputationalEfficiency Thecomparisonofcomputationalefficiency, i.e., theaverageconsumptionofCPUtimemeasured inmilliseconds(ms),ofeachheuristic forGroups1and2, theenumerationmethodandCPLEXfor Group1areshowninTable12. Table12.Computationalefficiency(averageCPUtimes inmilliseconds). SolutionMethod Group1 Group2 H1 0.08 67.99 H2 0.33 7895.49 H3 0.03 72.55 H4 0.32 7820.17 H5 0.01 1.21 H6 0.13 391.51 H7 0.01 1.28 H8 0.12 190.49 H9 0.06 79.02 H10 0.05 56.29 EM 1483.65 – Model 199,882.99 – Asexpected, theEMandCPLEXconsumedmuchmoreCPUtimethantheheuristics. For the small instances (Group1), thecomputational timesofall theheuristicswerealmostzeroand, for the mediumandlargeones (Group2),H2andH4tookthe longest times,nearly8sonaverage,which wererelativelyhighcomparedwith thoseofothermethodsbutdoesnotprecludetheiruse.Allother heuristics requiredfar less timethanonesecondwhichdemonstratedtheviabilityofusingthemin practice. It isworthnoting thatH5,whichrankedsecondwithasolutionqualityveryclose to that ofH6, consumed less thanahalf secondonaverage for large instances, thereby indicating itshigh computationalefficiency. Finally, inanoverallanalysisof theresultsandthesolutionapproachesproposedinthispaper (exactandheuristic), theapplicabilityof thedevelopedheuristicswere justifiedanddemonstrated in terms of both solution quality (an average of 0.6%deviation from the optimumwith the best heuristicH6)andcomputationalefficiency(anaverageof0.4s for large instancesalsowithH6). The 71