Seite - 187 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 76 A small percentage of degradation indicates that the performance of a strategy for a given metric is close to theperformanceof thebest performing strategy for the samemetric. Therefore, smalldegradationsrepresentbetter results. We observed that Randwas the strategywith theworstmakespan, with up to 318 percent performancedegradationcomparedwith thebest-obtainedresult. PHEFTstrategyhadasmallpercent ofdegradation,almost inallmetricsandtest cases.Wesawthat cpshadlessvariationcomparedwith Cmax and cpw. Ityieldedto lesser impactontheoverall score. ThemakespanofPHEFTandOHEFT werenear the lowervalues. Becauseourmodel isasimplifiedrepresentationofasystem,wecanconcludethat thesestrategies mighthavesimilarefficiency inrealDSP-clusterenvironmentswhenconsideringtheabovemetrics. However, thereexistdifferencesbetweenPESSandOPTI, comparing cpw. InPESSstrategy, thecritical path completion timedidnot growsignificantly. Therefore, tasks in the critical path experienced smallwaiting times. Resultsalsoshowedthat forall strategies, smallmeancriticalpathwaiting time degradationcorrespondedtosmallmeancriticalpathslowdown. BCandRandstrategieshadrankingsof5and6. Theiraveragedegradationswerewithin67% and18%of thebest results.WhilePESSandOPTIhadrankingsof3and4,withaveragedegradations within8%and11%. PHEFTandOHEFTshowedthebest results. Theirdegradationswerewithin6%and7%,with rankingsof1and2. (a) ܥ௠ ௔ ௫ (b) ܿ݌ ݓ (c) ܿ݌ ݏ 0% 1% 1% 2% 2% 3% 3% 4% 4% 5% 5% Cluster1 Cluster2 Cluster3 Rand BC PESS OPTI PHEFT OHEFT 0% 5% 10% 15% 20% 25% Cluster1 Cluster2 Cluster3 Rand BC PESS OPTI PHEFT OHEFT 0% 5% 10% 15% 20% 25% Cluster1 Cluster2 Cluster3 Rand BC PESS OPTI PHEFT OHEFT Figure4.Performancedegradation. 187