Page - 16 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 18 4.2. RandomlyGenerated InstancesStudies In these tests,weutilize twosetsof randomlygenerated instances toevaluate theperformanceof theproposedalgorithm. For thefirst setof small-size instances, therangeof jobs is [20,100]. For the secondsetof large-size instances, thenumberof jobs is set as500, 1000, 2000, 3000, 4000, and5000. Theprocessing time ti is randomlygeneratedfromauniformdistribution(30,210)minandthepower consumptionperhourpi is randomlygenerated in (30,100)kW.Tomeasure theeffectof theproposed algorithm,parameter e is setas e=1.2,1.5,2,3. Foreachgroupofn (n≤2000)and e, 10 randominstancesaregenerated, thentheaveragevalues of10testsarecalculatedandrecorded.Whenthenumberof jobs issetas3000,4000,and5000,GIHhas torunformore than4h(the longest isnearly twodays) tofindafeasiblesolution. Thus, considering thefeasibilityof theexperiment,only3randominstancesaregeneratedinsuchagroupoftests.All the averagevaluesarerecordedinTables5and6.Meanwhile, forthelarge-sizeinstances,weaddtworules toGIHtoreduce thecomputationtimewithoutchangingthecomputationalaccuracy. The improved algorithmisnamedGIH2. Table5.Computational results for thesmall-size instances. Instance GIH GIH-F n e m TECH CTH (s) TECF CTF (s) G (%) R 20 1.2 12.0 1634.1 0.034 1632.5 0.002 −0.10% 17.0 1.5 15.0 1370.1 0.037 1370.1 0.002 0.00% 18.5 2.0 19.0 1295.7 0.041 1295.1 0.002 −0.05% 20.5 3.0 28.5 1168.0 0.056 1168.0 0.001 0.00% 56.0 30 1.2 18.0 2414.6 0.064 2415.7 0.002 0.05% 32.0 1.5 20.0 2274.6 0.065 2274.1 0.002 −0.02% 32.5 2.0 28.5 2005.0 0.083 2005.0 0.002 0.00% 41.5 3.0 39.5 1741.0 0.119 1741.0 0.002 0.00% 59.5 40 1.2 23.0 3342.1 0.096 3342.0 0.004 0.00% 24.0 1.5 28.0 2900.1 0.109 2899.3 0.003 −0.03% 36.3 2.0 36.0 2775.6 0.143 2775.0 0.003 −0.02% 47.7 3.0 52.0 2380.3 0.194 2380.3 0.002 0.00% 97.0 50 1.2 27.5 4242.5 0.137 4242.4 0.005 0.00% 27.4 1.5 34.0 3733.0 0.164 3732.6 0.003 −0.01% 54.7 2.0 43.0 3243.8 0.212 3243.2 0.004 −0.02% 53.0 3.0 64.5 2940.6 0.315 2940.6 0.003 0.00% 105.0 60 1.2 34.0 4820.8 0.204 4819.7 0.006 −0.02% 34.0 1.5 40.0 4536.5 0.224 4536.3 0.004 0.00% 56.0 2.0 52.0 4029.0 0.293 4028.9 0.004 0.00% 73.3 3.0 78.0 3544.1 0.464 3544.1 0.004 0.00% 116.0 70 1.2 37.5 6133.5 0.249 6132.2 0.007 −0.02% 35.6 1.5 46.0 5416.3 0.303 5416.2 0.007 0.00% 43.3 2.0 61.0 4676.0 0.413 4675.8 0.004 0.00% 103.3 3.0 90.0 4024.9 0.643 4024.9 0.005 0.00% 128.6 80 1.2 43.0 7073.1 0.321 7072.9 0.009 0.00% 35.7 1.5 53.0 6049.6 0.401 6049.6 0.006 0.00% 66.8 2.0 68.5 5348.1 0.554 5348.1 0.007 0.00% 79.1 3.0 101.5 4514.4 0.868 4514.3 0.005 0.00% 173.6 90 1.2 48.0 8128.5 0.399 8128.4 0.009 0.00% 44.3 1.5 58.0 6772.5 0.501 6772.4 0.011 0.00% 45.5 2.0 77.5 6172.7 0.697 6172.6 0.008 0.00% 87.1 3.0 104.1 5228.2 1.196 5228.2 0.009 0.00% 132.9 100 1.2 53.5 8623.5 0.509 8622.9 0.017 −0.01% 29.9 1.5 64.0 7607.1 0.614 7607.0 0.011 0.00% 55.8 2.0 86.5 6896.8 0.927 6896.8 0.014 0.00% 66.2 3.0 128.0 5815.2 1.482 5815.1 0.009 0.00% 164.7 16