Page - 36 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 66 classesofharderproblems,wherethe jobpermutationπk∈SconstructedbyAlgorithm3outperforms themid-pointpermutationπmid−pandthepermutationπmax constructedbyAlgorithmMAX-OPTBOX derived in [15].AlgorithmMAX-OPTBOXandAlgorithm3werecodedinC#andtestedonaPCwith IntelCore (TM)2Quad,2.5GHz,4.00GBRAM.Forall tested instances, inequalities pLi < p U i hold forall jobs Ji∈J . Table2presents computational results for randomlygenerated instancesof the problem1|pLi ≤ pi≤ pUi |∑Ciwithn∈{100,500,1000,5000,10,000}. Thesegmentsof thepossible processingtimeshavebeenrandomlygeneratedsimilar to that in [15]. An integer centerCof thesegment [pLi ,p U i ]wasgeneratedusingauniformdistribution in the range [1,100]. ThelowerboundpLi ofthepossibleprocessingtimepiwasdeterminedusingtheequality pLi =C ·(1− δ100).Hereafter,δdenotes themaximal relativeerrorof theprocessingtimes pidueto the givensegments [pLi ,p U i ]. Theupperbound p U i wasdeterminedusingtheequality p U i =C ·(1+ δ100). Then, foreach job Ji∈J , thepoint piwasgeneratedusingauniformdistributionintherange [pLi ,pUi ]. In order to generate instances,where all jobsJ belong to a single block, the segments [pLi ,pUi ]of thepossibleprocessingtimesweremodifiedas follows: [p˜Li , p˜ U i ]= [p L i +p−pi, pUi +p−pi],where p=maxni=1pi. Since the inclusion p ∈ [p˜Li , p˜Ui ]holds, each constructed instance contains a single block, |B|=1. Themaximumabsoluteerrorof theuncertainprocessingtimes pi, Ji∈J , isequal to maxni=1(p U i −pLi ), andthemaximumrelativeerrorof theuncertainprocessingtimes pi, Ji∈J , isnot greater than2δ%.Wesaythat these instancesbelongtoclass1. Similarlyas in [15], threedistribution lawswereused inourexperiments todetermine the factual processingtimesof the jobs. (Weremindthat if inequality pLi < p U i holds, thenthe factualprocessing timeof the job Jibecomesknownaftercompletingthe job Ji.)Wecall theuniformdistributionas the distribution lawwithnumber1, thegammadistributionwith theparametersα=9andβ=2as the distribution lawwithnumber2andthegammadistributionwith theparametersα=4andβ=2as thedistribution lawwithnumber3. Ineach instanceofclass1, forgeneratingthe factualprocessing times fordifferent jobsof thesetJ , thenumberof thedistribution lawwasrandomlychosenfromthe set{1,2,3}.Wesolved15seriesof therandomlygenerated instances fromclass1. Eachseriescontains 10 instanceswith thesamecombinationofnandδ. In theconductedexperiments,weansweredthequestionofhowlarge theobtainedrelativeerror Δ= γkp∗−γtp∗ γtp∗ ·100%of thevalueγkp∗ of theobjective functionγ=∑ni=1Ciwasfor thepermutationπk withtheminimalvalueofF(πk,T)withrespect to theactuallyoptimalobjective functionvalueγtp∗ calculatedfor the factualprocessingtimes p∗=(p∗1,p ∗ 2, . . . ,p ∗ n)∈T.Wealsoansweredthequestion ofhowsmall theobtainedrelativeerrorΔof thevalueγkp∗ of theobjective function∑Ciwasfor the permutationπkwiththeminimalvalueofF(πk,T).WecomparedtherelativeerrorΔwiththerelative errorΔmid−pof thevalueγmp∗ of theobjective function∑Ci for thepermutationπmid−pobtainedfor determining the jobprocessing times using themid-points of the given segments. We compared the relative errorΔwith the relative errorΔmax of the value of the objective function∑Ci for the permutationπmax constructedbyAlgorithmMAX-OPTBOXderivedin [15]. Thenumbernof jobs in the instance isgiven incolumn1inTable2. Thehalfof themaximum possible errors δ of the randomprocessing times (inpercentage) is given in column2. Column3 gives the average errorΔ for the permutation πk with theminimal value of F(πk,T). Column 4 presents theaverageerrorΔmid−pobtainedfor themid-pointpermutationsπmid−p,whereall jobsare orderedaccordingto increasingmid-pointsof their segments.Column5presents theaveragerelative perimeterof theoptimalityboxOB(πk,T) for thepermutationπkwith theminimalvalueofF(πk,T). Column6presents therelationΔmid−p/Δ. Column7presents therelationΔmax/Δ. Column8presents theaverageCPU-timeofAlgorithm3for thesolvedinstances inseconds. Thecomputationalexperimentsshowedthat forall solvedexamplesofclass1, thepermutations πkwiththeminimalvaluesofF(πk,T) for theiroptimalityboxesgeneratedgoodobjective function valuesγkp∗,whicharesmallerthanthoseobtainedforthepermutationsπmid−pandforthepermutations 36