Seite - 65 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 43 Table2.Compositionofheuristic’s structure. Heuristic InitialOrdering NeighborhoodSearch EDD MST Insertion Permutation Fwd/Bwd NEH-based H1 x H2 x x x H3 x H4 x x x Hodgson-based H5 x H6 x x x H7 x H8 x x x Other H9 x x H10 x x 5.ComputationalExperimentsandResults In thissection,wedescribe thecomputationalexperimentsconductedtostudythebehaviorof themathematicalmodelpresented inSection3andtheheuristicsdescribedinSection4. Thecodes for the heuristicswere implemented in theDelphi programming environment, themathematical modelwaswritten in thesyntaxof theAMPLmodeling languageandthe instancessolvedwith the branch-and-cutalgorithmincludedin the IBM-CPLEX12.6.1.0.All testswereconductedonaPentium Dual-Corewitha2.0GHzprocessor,3.0GBRAMandWindowsOperatingSystem. Atotalof15,600instancesweregenerated. TheyareseparatedintoGroup1ofsmall instancesand Group2ofmediumandlargeonesasdescribed inSection5.1. Thecomputational studywasdivided in twoparts: Experiment 1 andExperiment 2. Section 5.2presents the comparative results of the proceduresdescribed inSection4 (Experiment1). Thequalityof theheuristics solutions is reinforced whentheyarecomparedto thebest solutionobtainedbysolvingthe instancesof themathematical modelwithCPLEX,asdescribedinSection5.3 (Experiment2). Thecomputationalefficiencyof the solution’sstrategies, computedin termsofCPUtime, isdiscussed inSection5.4. 5.1. ProblemInstances The instanceswereseparated into twogroups,withGroup1consistingofsmall instancesand Group2ofmediumandlargeones. Ineachgroup, the instancesaredividedintoclassesdefinedbythe numberof jobs (n),numberofmachines (m) andscenariosofduedates,with100 instancesrandomly generatedforeachclass toreduce thesamplingerror. Theprocessingtimesweregenerated inthe intervalU[1,99], as in themostproductionscheduling scenarios foundinthe literature (e.g., [21,22]). InGroup1, theparametersweren∈ {5, 6, 7, 8, 10}and m∈ {2, 3, 5} and, inGroup2,n∈ {15, 20, 30, 50, 80, 100} andm∈ {5, 10, 15, 20}. Thesevalueswere chosentocoverasignificant rangeof instancesofvarioussizes. Thegenerationofduedates followedthemethodusedby[23],withauniformdistribution in the interval [P(1−T−R/2),P(1−T+R/2)],whereT andR are the tardiness factor of jobs and dispersionrangeofduedates, respectively,andP the lowerboundfor themakespanwhich isdefined as inTaillard[24]: P=max { max 1≤k≤m { n ∑ j=1 pjk+min j k−1 ∑ q=1 pjq+min j m ∑ q=k+1 pjq } ,max j m ∑ k=1 pjk } (13) Thefollowingscenariosrepresent theconfigurationsobtainedbyvaryingthevaluesofTandR: • Scenario1: lowtardiness factor (T=0.2)andsmallduedaterange(R=0.6); • Scenario2: lowtardiness factor (T=0.2)andlargeduedaterange(R=1.2); • Scenario3: hightardiness factor (T=0.4)andsmallduedaterange(R=0.6); and 65