Page - 17 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 18 Table6.Computational results for the large-size instances. Instance GIH2 GIH-F n e m TECH CTH2 (s) TECF CTF (s) R 500 1.2 250.5 43,909.1 53.0 43,909.1 0.219 242.0 1.5 315.0 38,637.8 52.2 38,637.9 0.187 279.1 2.0 417.0 34,417.5 56.3 34,417.5 0.082 686.6 3.0 628.5 28,948.1 56.9 28,948.0 0.093 611.8 1000 1.2 504.0 87,500.3 244.2 87,500.3 1.802 135.5 1.5 628.5 77,598.3 230.3 77,597.0 0.873 263.8 2.0 840.0 69,199.2 294.1 69,199.2 0.432 680.8 3.0 1256.5 57,923.1 250.7 57,923.1 0.485 516.9 2000 1.2 1002.5 176,681.2 3910.8 176,680.7 15.701 249.1 1.5 1255.5 155,205.3 3114.3 155,206.2 6.503 478.9 2.0 1669.0 137,774.1 4316.2 137,774.1 3.346 1290.0 3.0 2501.7 115,661.0 1785.8 115,661.0 3.574 499.7 3000 1.2 1511.7 263,511.1 19,136.9 263,511.6 46.551 411.1 1.5 1880.0 231,954.6 14,429.7 231,954.9 25.560 564.5 2.0 2483.3 205,368.8 19,759.8 205,368.8 11.219 1761.3 3.0 3780.0 173,630.6 6571.9 173,630.6 12.432 528.6 4000 1.2 1991.7 352,975.8 59,016.2 352,977.0 107.610 548.4 1.5 2511.7 306,983.3 43,971.5 306,983.3 66.669 659.5 2.0 3335.0 275,694.8 60,539.8 275,694.8 26.281 2303.6 3.0 4986.7 231,148.4 17,014.0 231,148.4 29.728 572.3 5000 1.2 2498.3 438,717.9 136,314.9 438,718.6 168.581 808.6 1.5 3131.1 386,546.1 101,071.7 386,548.1 106.764 946.7 2.0 4161.1 341,504.3 139,122.7 341,504.3 50.931 2731.6 3.0 6257.8 291,685.7 51,471.0 291,685.7 58.821 875.0 Rule1: If ti≤maxk∈A{Ik}andkk=argmink∈A{ti≤ Ik},whereargmink∈A{ti≤ Ik}denotes the minimal indexk for ti≤ Ik, then job icanbedirectly inserted into theoff-peakperiodkkandthe jobno longer traversesall thenon-fullperiods. Rule2: If ti≤mink′′∈Γ { Ik′′ } ,maxk∈A{Ik}>0ormaxk′∈B{Ik′}>0, then job inolonger traverses on-peakperiods. Asmentioned above,when there are no jobs that need to traverse non-full on-peakperiods, the time complexity ofGIH-F isO(n2m) andGIH isO(n2m2). This implies thatGIH-F ism times faster thanGIH, theoretically, and the experimentaldataof the small-size instances inTable 5 can verify thisconclusion. FromTable5,wecansee thatRandmarealmost thesameorderofmagnitude. In addition, all the small-size instances canbe solvedwithin0.02 susingGIH-F.Byand large, the computationtimeincreasesslightlywithn,andparameterehasnosignificanteffectonthecomputation time,which indicates that thealgorithmisquitestable. Inaddition, it canbeseenfromTable5 that the smaller the parameter e (i.e., the shorter themakespan), the higher the total electricity cost. Therefore, inaspecific instance, thedecision-makerscanobtainasetofParetosolutionsbyadjusting themakespan,andtheycanchooseasolutionaccordingtoactualneeds.What ismore, it isamazing to see that our algorithmnotonlygreatly improves computation speedbut also further improves theaccuracy. Table6showsthatthenumberofperiodsincreasesquicklywiththenumberof jobs. Sincethetime complexityofGIHisO(n2m2), it’s runtimewill risesharply. Toensure thefeasibilityof thecontrast tests,weaddtworules (i.e.,Rule1andRule2) to improvethecomputationalspeedofGIHwithout changingthecomputationalaccuracy. Intuitively, theCTF is significantly less thanCTH2, whichmeans that the designed filtering mechanism is efficient in dealing with large-scale instances. Specially, as n = 5000 and e = 2.0, ouralgorithmcansolvearandomlygenerated instancewithin1minandmaintain thesameaccuracy asGIH2, while GIH2 takes nearly 39 h, let aloneGIH.Note thatwhen e is set as 3.0, the given makespanisveryabundantandthereisnojobprocessedwithinanon-peakperiodinourexperimental 17