Seite - 188 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 76 Table5.Roundedperformancedegradationandranking. Criteria Strategy Rand BC PESS OPTI PHEFT OHEFT Montage Cmax 3.189 0.010 0.009 0.039 0.005 0.011 cpw 0.209 0.173 0.100 0.196 0.050 0.093 cps 0.001 0.305 0.320 0.348 0.302 0.306 Mean 1.133 0.163 0.143 0.194 0.119 0.137 Rank 6 4 3 5 1 2 Ligo Cmax 0.044 0.043 0.012 0.012 0.001 0.002 cpw 0.580 0.542 0.059 0.059 0.002 0.013 cps 0.040 0.040 0.012 0.013 0.002 0.002 Mean 0.221 0.208 0.028 0.028 0.002 0.005 Rank 6 5 3 4 1 2 All test cases Cmax 1.616 0.027 0.011 0.025 0.003 0.006 cpw 0.394 0.357 0.079 0.128 0.026 0.053 cps 0.020 0.173 0.166 0.180 0.152 0.154 Mean 0.677 0.186 0.085 0.111 0.060 0.071 Rank 6 5 3 4 1 2 6.2. PerformanceProfile In theprevious section,wepresented theaverageperformancedegradationsof the strategies over threemetricsandtest cases.Now,weanalyzeresults inmoredetail. Oursamplingdatawere averagedovera largescale.However, thecontributionofeachexperimentvarieddependingonits variabilityoruncertainty [30–32]. Toanalyze theprobabilityofobtainingresultswithacertainquality andtheir contributorsonaverage,wepresent theperformanceprofilesof thestrategies.Measures of resultdeviationsprovideuseful informationforstrategiesanalysisandinterpretationof thedata generatedbythebenchmarkingprocess. Theperformanceprofileδ(τ)pτ isanon-decreasing,piecewiseconstant functionthatpresents the probability thataratioγ iswithina factorτof thebest ratio [33]. The functionδ(τ) is thecumulative distributionfunction. Strategieswith largerprobabilitiesδ(τ) forsmallerτwillbepreferred. Figure5showstheperformanceprofilesof thestrategiesaccordingtototalcompletiontime, inthe intervalτ=[1. . .1.2], toprovideobjective informationforanalysisofa test set. (a) (b) 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1 1.021.04 1.06 1.08 1.1 1.12 1.141.16 1.18 1.2 ߬ Rand BC PESS OPTI PHEFT OHEFT 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1 1.02 1.04 1.06 1.08 1.1 1.12 1.14 1.16 1.18 1.2 ߬ Rand BC PESS OPTI PHEFT OHEFT Figure5.Cmaxperformanceprofile,τ=[1. . .1.2]. (a)Montage; (b)Ligo. Figure5adisplaysresults forMontageworkflows. PHEFThadthehighestprobabilityofbeing thebetter strategy. Theprobability that itwas thewinneronagivenproblemwithin factorsof1.02of thebest solutionwasclose to0.9. Ifwechose tobewithinafactorof1.1as thescopeofour interest, 188