Seite - 37 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 66 πmax. The smallest errors, average errors, largest errors for the tested series of the instances are presented in the last rowsofTable2. Table2.Computational results for randomlygenerated instanceswithasingleblock(class1). n δ(%) Δ(%) Δmid−p (%) PerOB(πk,T) Δmid−p/Δ Δmax/Δ CPU-Time(s) 1 2 3 4 5 6 7 8 100 1 0.08715 0.197231 1.6 2.263114 1.27022 0.046798 100 5 0.305088 0.317777 1.856768 1.041589 1.014261 0.031587 100 10 0.498286 0.500731 1.916064 1.001077 1.000278 0.033953 500 1 0.095548 0.208343 1.6 2.18052 1.0385 0.218393 500 5 0.273933 0.319028 1.909091 1.164623 1.017235 0.2146 500 10 0.469146 0.486097 1.948988 1.036133 1.006977 0.206222 1000 1 0.093147 0.21632 1.666667 2.322344 1.090832 0.542316 1000 5 0.264971 0.315261 1.909091 1.189795 1.030789 0.542938 1000 10 0.472471 0.494142 1.952143 1.045866 1.000832 0.544089 5000 1 0.095824 0.217874 1.666667 2.273683 1.006018 7.162931 5000 5 0.264395 0.319645 1.909091 1.208965 1.002336 7.132647 5000 10 0.451069 0.481421 1.952381 1.06729 1.00641 7.137556 10,000 1 0.095715 0.217456 1.666667 2.271905 1.003433 25.52557 10,000 5 0.26198 0.316855 1.909091 1.209463 1.003251 25.5448 10,000 10 0.454655 0.486105 1.952381 1.069175 1.003809 25.50313 Minimum 0.08715 0.197231 1.6 1.001077 1.000278 0.031587 Average 0.278892 0.339619 1.827673 1.489703 1.033012 6.692502 Maximum 0.498286 0.500731 1.952381 2.322344 1,27022 25.5448 In the secondpart of our experiments, Algorithm3was applied to the randomly generated instances fromotherhardclasses2–7of theproblem1|pLi ≤ pi≤ pUi |∑Ci.Werandomlygenerated non-fixed jobs J1, J2, . . . , Js,whichbelongtoallblocksB1,B2, . . .,Bmof therandomlygeneratedn−s fixed jobs. The lower bound pLi and theupper bound p U i on the feasible values of pi∈R1+ of the processing timesof thefixed jobs, pi∈ [pLi ,pUi ],weregeneratedas follows.Wedeterminedaboundof blocks [b˜Li , b˜ U i ] forgeneratingthecoresof theblocks [b L i ,b U i ]⊆ [b˜Li , b˜Ui ]andforgeneratingthesegments [pLi ,p U i ] for theprocessing times of |Bi| jobs fromall blocksBi, i ∈ {1,2,3}, [bLi ,bUi ]⊆ [pLi ,pUi ]⊆ [b˜Li , b˜ U i ]. Each instance inclass2hasfixed jobs Ji∈Jwithratherclosedcenters (pLi +pUi )/2andlarge differencebetweensegment lengths pUi −pLi . Each instance inclass3or inclass4hasasinglenon-fixed job Jv,whoseboundsaredetermined as follows: pLJv ≤ b˜L1 ≤ b˜U1 < b˜L2 ≤ b˜U2 < b˜L3 ≤ b˜U3 ≤ pUJv. Classes3and4of thesolvedinstancesdiffer onefromanotherbythenumbersofnon-fixed jobsandthedistribution lawsusedforchoosingthe factualprocessingtimesof the jobsJ . Each instance fromclasses5and6has twonon-fixed jobs. In each instance fromclasses2,3,5,6and7, forgeneratingthefactualprocessingtimes for the jobsJ , thenumbersof thedistributionlawwererandomlychosenfromtheset{1,2,3}, andtheyare indicated incolumn4 inTable3. In the instancesof class7, thecoresof theblocksweredetermined inorder togeneratedifferentnumbersofnon-fixed jobs indifferent instances. Thenumbersofnon-fixed jobs were randomlychosen fromtheset{2,3,. . . ,8}. Numbersnof the jobsarepresented incolumn1. InTable 3, column2 represents thenumber |B|of blocks in the solved instance and column3 the number of non-fixed jobs. The distribution lawsused for determining the factual job processing timesare indicated incolumn4inTable3. Eachsolvedseriescontained10 instanceswith thesame combinationofnandtheotherparameters. Theobtainedsmallest, averageandlargestvaluesofΔ, Δmid−p, Δmid−p Δ and Δmax Δ for each series of the tested instances arepresented in columns5, 6, 8 and 9 inTable3at theendofseries. Column7presents theaveragerelativeperimeterof theoptimality boxOB(πk,T) for thepermutationπkwith theminimalvalueofF(πk,T). Column10presents the averageCPU-timeofAlgorithm3for thesolvedinstances inseconds. 37