Seite - 67 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 43 Figure1. Exampleofdifferent scheduleswith the samesequenceof jobs: (a) only J3 is just-in-time; (b) J2 and J1 are just-in-time;and(c) J2 and J3 are just-in-time. Therefore, theEMenumeratesallpossiblesequences,but it is impractical toprobeallpossible schedules,especially formediumandlargescale instances.Giventhat, theEMwasnotappliedfor Group2’s instances,andthebest solutionfoundbytheheuristicsH1–H10wasconsideredasreference for the instances in thisgroup. EnumerationMethod Step1.Enumerate then! possiblesequencesandconsider theonewith thebestnJIT. Step2.Apply the timingadjustmentprocedure. Algorithm12.Pseudo-codeof theenumerationmethod. Figure 2 graphically presents the results, with 95% confidence intervals of the averageRPD obtainedbyeachheuristicmethodforbothGroups1and2. The95%confidence intervalmeans that theresults (RPD)of95casesamong100arewithin thedisplayedrange. Theglobalanalysisof results revealedthatH6clearlyoutperformedtheotherheuristics,witha RPDof0.2%forbothGroups1and2(ascanbeseen inTable4)which indicates that itprovidedthe bestorveryclose to thebest solutions formanycases. Figure2.Comparisonofperformancesofheuristicsbygroupwith95%confidence intervalofaverage RPD: (a) relatedtoEMforGroup1;and(b) relatedto thebestH1–H10solutionforGroup2. 67