Seite - 66 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 43 • Scenario4: hightardiness factor (T=0.4)andlargeduedaterange(R=1.2). Usingtheseparameters, 6000 instancesweregenerated inGroup1,dividedin60classes. That is, five levelsofnumberof jobs, three levelsofnumberofmachines, four scenariosand100 instances perclass (5×3×4×100=6000). ForGroup2,9600 instancesweregenerated,dividedin96classes, six levelsofnumberof jobs, four levelsofnumberofmachines, fourscenariosand100 instancesper class (6×4×4×100=9600). Atotalof15,600 instancesweregeneratedandtheirparametersare summarized inTable3. Table3.Parameters forgenerationof the instances. Group1 Group2 Numberof jobs 5,6,7,8,10 15,20,30,50,80,100 Numberofmachines 2,3,5 5,10,15,20 Scenarioconfigurations Scenario1:T=0.2andR=0.6; Scenario2:T=0.2andR=1.2; Scenario3:T=0.4andR=0.6; Scenario4:T=0.4andR=1.2 Numberof instancesperclass 100 100 Numberof instancespergroup 6000 9600 Totalnumberof instancessolved 15,600 5.2. Experiment1: RelativeComparisonof theProposedHeuristics In thisfirstpartof theresultsevaluation,arelativecomparisonof theproposedheuristicswas conducted. Themostcommonmeasureused in the literature tocompare theperformancesof solution methods is therelativepercentagedeviation(RPD) (e.g., [22,25]),which,adaptedto themaximization problemaddressed, is calculatedas: RPD=( nbestJIT−nhJIT nbestJIT )100, (14) wherenbestJIT is thebestsolutionfoundandn h JIT theheuristicsolutionevaluated. Thelowerisamethod’s RPD, thebetter is itsperformance,withaRPDofzero indicatingthat themethodprovidedthebest solutionfound(orachievedatie). Tocompare theheuristicsperformances forGroup1’s instances, thesolutionofanenumeration method (EM), basedon [25],wasusedas a reference (see thepseudo-code inAlgorithm12). It is important tonote that theEMprovidesareferencesolutionto theproblemand,althoughit listedn! possiblepermutations (sequences)of jobs, itdoesnotwarrantanoptimalsolutionsince theschedule iscomposedbysequencingandtiming. That is, for thesamesequence, it ispossible tofindseveral scheduleswithdifferentstarting times foreachoperation, therebyresulting inmanypossibilities for thesamenumberof just-in-time jobs,ascanbeseen inFigure1. 66