第6期 王伟玲等：基于正逆序策略求解Job Shop的遗传调度算法 817 果，其中MFBAn的运行环境为2.4GH1GRAM 指出的是，加粗数值表示对应算例己达到目前已知 P℃HGA的运行环境为L.33 GHz AMD Thundebird 的最优值，且文献[6并没有给出算例L31~LA35 PCPT-JSP-PSO的运行环境为16O0MHzC值得 的实验结果，在此用VA示意 表2 FBGTGA算法Benchmarks实测结果 Table2 Results of FBGIGA a Forithm on Bendmak Probkms 规模 CGA算法测试结果 MFBAnta HGAI PT-JSP-PSO 2 算例 OPt m %dev时间/sCam %dew时间/sCmm dev 时间/ 。C %dew时间/s F106 6X6 5 55000046 55000 时 000 3 55 000 107 FTio 10×10 930 930 000 43 930 000 6 930 000 292 930 000 406 F20 20X5 1165 1165 000 5.5 1165 000 235 1166 000 204 1165 000 449 L01 10X5 666 666 000 1.4 666 000 6 66 000 37 666 000 168 LA02 10X5 655 655 000 3.7 655 000 655 000 51 655 000 168 LA03 10X5 59 597 000 68 597 000 37 597 000 39 597 000 168 L04 10X5 5 000 9.4 590 000 38 000 590 000 168 LA05 10X5 9 92 000 45 593 000 36 59g 000 593 000 168 L06 15X5 000 32 926 000 926 000 926 000 304 L07 15X5 g90 000 13.9 890 000 102 890 000 890 000 304 LA08 15X5 000 5.7 0 00 000 863 000 L09 15X5 951 时 000 5.1 os 0 物 000 951 000 吃 LAIO 15X5 000 32 0 000 9 958 000 LAL 20X5 1229 1222 000 51 1222 % 122 000 19 1222 000 450 LAI2 20X5 1039 1039 000 45 1039 000 235 1039 000 201 1039 000 450 LAI3 20x5 1150 1150 000 5.6 1150 00 235 1150 000 189 1150 000 450 LA14 20x5 1292 1292 000 1292 0 238 1292 000 187 1292 000 450 LAI5 20X5 1207 1207 000 1207 000 236 120m 000 187 1207 000 450 1A16 10X10 945 945 000 947 021 161 945 000 232 945 000 412 IAIZ 10X10 784 心 000 保 000 160 浅 000 216 784 000 412 1A18 10×10 848 848 000 848 000 000 219 848 000 412 LA1910X10 842 842 000 848 071 162 000 235 842 000 412 LA20 10X10 902 902 000 12.7 907 0 161 055 235 907 055 412 IA21 15X10 1046 1051 048 56 1063 63 902 1046 000 602 1060 134 763 LA22 15X10 927 938 119 63 944 1 83 900 935 086 629 935 086 763 LA23 15X10 1032 1032 000 13 1032 898 1032 000 1032 000 763 1A24 15X×10 935 948 139 62 940 053 193 578 944 096 763 LA25 15X10 97 072 58 989 123 904 98%6 092 609 984 072 763 LA26 20X10 1216 1218 016 3 1220 033 8763 016 1388 1218 016 1165 LA27 20×10 1235 1238 024 1240 040 8558 1256 170 1251 1258 186 1165 LA28 20×10 1216 1218 016 87 1247 255 8559 1232 132 1267 1218 016 1165 LA29 20×10 1152 1185 286 9%6 1162 087 8560 1196 1350 1184 278 1165 LA30 20X10 1355 1355 000 1365 074 8560 135$ 000 1260 1355 000 1165 LA31 30X10 1784 1784 000 478 N/A N/A N/ 1784 000 3745 1784 000 2353 L32 30X10 1850 1850 000 463 NA N/A N/A 18s0 000 3741 1850 000 2353 LA33 30X10 1719 1719 000 485 N/A N/A N/A 1719 0 00 3637 1719 000 2353 1A34 30×10 1721 1721 000 496 N/A N/A N/A 1721 000 3615 1721 000 2353 LA3530X10 1888 1888 000 583 NA N/A N/A 1888 000 3716 1888 Q00 2353 LA36 15X15 1268 1270 016 385 1300 252 12618 1279 087 1826 1278 079 1401 LA37 15X15 1397 1404 050 274 1439 301 12614 1408 079 1860 1410 093 1401 LA38 15X15 1196 1198 017 286 1224 234 12620 1219 192 1859 1221 209 1401 LA39 15X15 1233 1245 097 293 1262 235 12619 1246 105 1869 1251 1.46 1401 IA40 15X15 1222 1228 049 386 1250 229 126位4 1241 155 2185 1229 057 1401 平均值 024123 060 2832 044 1009 038 877第 6期 王伟玲等:基于正逆序策略求解 JobShop的遗传调度算法 果, 其中 MFBAnt的运行环境为 2.4 GHz/1 GRAM PC, HGA的运行环境为 1.33 GHzAMDThunderbird PC, PT-JSP-PSO的运行环境为 1 600 MHzPC.值得 指出的是, 加粗数值表示对应算例已达到目前已知 的最优值, 且文献 [ 6] 并没有给出算例 LA31 ～ LA35 的实验结果, 在此用 N/A示意 . 表 2 FBGTGA算法 Benchmark实测结果 Table2 ResultsofFBGTGAalgorithmonBenchmarkproblems 算例 规模 n×m Opt. CGA算法测试结果 MFBAnt[ 6] HGA[ 11] PT-JSP-PSO[ 12] C＊ max %dev 时间 /s C＊ max %dev 时间 /s C＊ max %dev 时间 /s C＊ max %dev 时间/s FT06 6×6 55 55 0.00 0.46 55 0.00 34 55 0.00 13 55 0.00 107 FT10 10×10 930 930 0.00 4.3 930 0.00 162 930 0.00 292 930 0.00 406 FT20 20×5 1 165 1 165 0.00 5.5 1 165 0.00 235 1 165 0.00 204 1 165 0.00 449 LA01 10×5 666 666 0.00 1.4 666 0.00 36 666 0.00 37 666 0.00 168 LA02 10×5 655 655 0.00 3.7 655 0.00 36 655 0.00 51 655 0.00 168 LA03 10×5 597 597 0.00 6.8 597 0.00 37 597 0.00 39 597 0.00 168 LA04 10×5 590 590 0.00 9.4 590 0.00 38 590 0.00 42 590 0.00 168 LA05 10×5 593 593 0.00 4.5 593 0.00 36 593 0.00 32 593 0.00 168 LA06 15×5 926 926 0.00 3.2 926 0.00 101 926 0.00 99 926 0.00 304 LA07 15×5 890 890 0.00 13.9 890 0.00 102 890 0.00 86 890 0.00 304 LA08 15×5 863 863 0.00 5.7 863 0.00 101 863 0.00 99 863 0.00 304 LA09 15×5 951 951 0.00 5.1 951 0.00 103 951 0.00 94 951 0.00 304 LA10 15×5 958 958 0.00 3.2 958 0.00 102 958 0.00 91 958 0.00 304 LA11 20×5 1 222 1 222 0.00 5.1 1 222 0.00 236 1 222 0.00 197 1 222 0.00 450 LA12 20×5 1 039 1 039 0.00 4.5 1 039 0.00 235 1 039 0.00 201 1 039 0.00 450 LA13 20×5 1 150 1 150 0.00 5.6 1 150 0.00 235 1 150 0.00 189 1 150 0.00 450 LA14 20×5 1 292 1 292 0.00 8.3 1 292 0.00 238 1 292 0.00 187 1 292 0.00 450 LA15 20×5 1 207 1 207 0.00 5.3 1 207 0.00 236 1 207 0.00 187 1 207 0.00 450 LA16 10×10 945 945 0.00 5.4 947 0.21 161 945 0.00 232 945 0.00 412 LA17 10×10 784 784 0.00 6.8 784 0.00 160 784 0.00 216 784 0.00 412 LA18 10×10 848 848 0.00 7.2 848 0.00 162 848 0.00 219 848 0.00 412 LA19 10×10 842 842 0.00 4.6 848 0.71 162 842 0.00 235 842 0.00 412 LA20 10×10 902 902 0.00 12.7 907 0.55 161 907 0.55 235 907 0.55 412 LA21 15×10 1 046 1 051 0.48 56 1 063 1.63 902 1 046 0.00 602 1 060 1.34 763 LA22 15×10 927 938 1.19 63 944 1.83 900 935 0.86 629 935 0.86 763 LA23 15×10 1 032 1 032 0.00 13 1 032 0.00 898 1 032 0.00 594 1 032 0.00 763 LA24 15×10 935 948 1.39 62 940 0.53 905 953 1.93 578 944 0.96 763 LA25 15×10 977 984 0.72 58 989 1.23 904 986 0.92 609 984 0.72 763 LA26 20×10 1 216 1 218 0.16 73 1 220 0.33 8 763 1 218 0.16 1 388 1 218 0.16 1 165 LA27 20×10 1 235 1 238 0.24 79 1 240 0.40 8 558 1 256 1.70 1 251 1 258 1.86 1 165 LA28 20×10 1 216 1 218 0.16 87 1 247 2.55 8 559 1 232 1.32 1 267 1 218 0.16 1 165 LA29 20×10 1 152 1 185 2.86 96 1 162 0.87 8 560 1 196 3.82 1 350 1 184 2.78 1 165 LA30 20×10 1 355 1 355 0.00 95 1 365 0.74 8 560 1 355 0.00 1 260 1 355 0.00 1 165 LA31 30×10 1 784 1 784 0.00 478 N/A N/A N/A 1 784 0.00 3 745 1 784 0.00 2 353 LA32 30×10 1 850 1 850 0.00 463 N/A N/A N/A 1 850 0.00 3 741 1 850 0.00 2 353 LA33 30×10 1 719 1 719 0.00 485 N/A N/A N/A 1 719 0.00 3 637 1 719 0.00 2353 LA34 30×10 1 721 1 721 0.00 496 N/A N/A N/A 1 721 0.00 3 615 1 721 0.00 2 353 LA35 30×10 1 888 1 888 0.00 583 N/A N/A N/A 1 888 0.00 3716 1 888 0.00 2 353 LA36 15×15 1 268 1 270 0.16 385 1 300 2.52 12 618 1 279 0.87 1 826 1 278 0.79 1 401 LA37 15×15 1 397 1 404 0.50 274 1 439 3.01 12 614 1 408 0.79 1 860 1 410 0.93 1 401 LA38 15×15 1 196 1 198 0.17 286 1 224 2.34 12 620 1 219 1.92 1 859 1 221 2.09 1 401 LA39 15×15 1 233 1 245 0.97 293 1 262 2.35 12 619 1 246 1.05 1 869 1251 1.46 1 401 LA40 15×15 1 222 1 228 0.49 386 1 250 2.29 12 624 1 241 1.55 2 185 1 229 0.57 1 401 平均值 0.24 123 0.60 2 832 0.44 1 009 0.38 877 · 817·