Seite - 91 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 68 25.6 25.8 26 26.2 26.4 26.6 16,890 16,970 17,050 17,130 17,210 ܧop (kW) Figure23.Pareto front forsixmachinesperstage. Figure21showsthesolutionspace(twoobjectives)fortwomachinesperstage.Thistwo-dimensional solutionspacerepresentsa feasiblesetof solutions that satisfy theproblemconstraints. ThePareto frontcoversawiderangeofEop from6856to7178kW,whileCmax is in therangeof96.64 to97.48h. Figure22showsthesolutionspace for fourmachinesperstage. ThePareto frontcoversEop from 12,242 to12,559kW,whileCmax is in therangeof43.98 to44.8h. Finally,Figure23showsthesolution space for6machinesperstage.Eop ranges from16,899 to17,221kW,whileCmax is in therangeof25.66 to26.66h. AlthoughthePareto frontsareofgoodquality, it isobservedthatmanyof thegeneratedsolutions arequite far fromit. Therefore,asingleexecutionof thealgorithmcanproducesignificantlydifferent results. Theselectionof thesolutions includedin thePareto frontdependsonthepreferenceof the decisionmaker. 7.3. BranchandBoundAnalysis ABranchandBoundalgorithm(B&B) isanexactmethodforfindinganoptimalsolutiontoan NP-hardproblem. It isanenumerative techniquethatcanbeappliedtoawideclassofcombinatorial optimizationproblems. Thesolutionsearchingprocess is representedbyabranchingtree. Eachnode in the treecorresponds toasubproblem,which isdefinedbyasubsequenceof tasks thatareplacedat thebeginningof thecompletesequence. This subsequence iscalledpartial sequence (PS).Thesetof tasksnot includedinPS iscalledNPS. Whenanode is branched, oneormorenodes aregeneratedbyaddinga task aheadof thepartial sequenceassociatedwith thenodebeingbranched. Toavoidfull enumerationofall taskpermutations, the lower boundof the value of the objective functions is calculated in each step for eachpartial schedule. In thecaseof ties, thealgorithmselectsanodewith the lowest lowerbound. The B&B algorithm was run on a PC with an Intel Core i3 CPU and 4 GB of RAM. TheprogramminglanguageusedtoencodethealgorithmwasR.Thealgorithmlastedapproximately 12days,3h. A comparison of the B&B algorithm concerning the Pareto front is shown in Figure 21 as a lowest leftpoint. TheB&Bresult is consideredas thebest result thatcouldbeobtained,knownas the globaloptimum. Table17showstherelativedegradationofourbi-objectivealgorithmover theB&Bbest solutions. Resultsareobtainedbyaveraging30experiments.Wesee that theresults foreachobjectivearenot morethan3.44%worst forCmax and2.94%forEop. Table18showsthecomputationtimesforobtaining thePareto frontsolutions. Accordingto theresultscomparison,weconcludethat theproposedbi-objectivealgorithmcan producesatisfactoryresultsclose toaglobaloptimuminshortcomputational time. 91