·640 工程科学学报，第39卷，第4期 表4随机数据仿真实验测试结果 Table 4 Simulation test results in random data 下界 HAGS算法 BFD算法 订单数量 圆坯重量： 圆坯使用数量 圆坯使用数量 偏离率/% 圆坯使用数量 偏离率/% > 9.55 9.75 2.09 10.3 7.85 乎 8.45 8.65 2.37 8.65 2.37 10 9 7.65 7.75 1.31 7.9 3.27 10 6.95 7 0.72 7.1 2.16 1 19.5 19.85 1.79 20.3 4.1 20 乐 17 17.2 1.18 17.5 2.94 9 15.15 15.3 0.99 15.8 4.29 10 13.8 13.9 0.72 14 1.45 44.8 45.8 2.23 45.9 2.46 50 39.4 39.55 0.38 40.05 1.65 9 35.15 35.55 1.14 35.6 1.28 10 31.65 32 1.11 32.3 2.05 > 84.8 87.33 2.98 93.62 10.4 100 8 74.2 75.5 1.75 80.15 8.02 9 65.95 66.83 1.33 71.29 8.1 10 59.36 61 2.76 65.87 10.97 > 168.9 172.76 2.29 181.2 7.28 200 乎 147.8 149.77 1.34 157.23 6.39 9 131.37 134.6 2.46 140.98 7.32 10 118.23 121.3 2.6 127.1 7.5 > 423.9 435.31 2.69 448.65 5.84 500 370.9 377.32 1.73 387.98 4.6 9 329.71 333.18 1.05 343.72 4.25 10 296.74 301.5 1.6 308.63 4.01 注：HAGS偏离率(%)=(HAGS算法圆坯使用数量-下界圆坯使用数量)/下界圆坯使用数量×10O%:BFD偏离率(%)=(BFD算法圆 坯使用数量-下界圆坯使用数量)/下界圆坯使用数量×100% 从表4可以得到以下结论. 120 (1)总的来看，贪婪策略的启发式算法求得的圆 100 一HAGS算法 坯数量均低于降序最佳适应算法，说明贪婪策略的启 -·BFD算法 80 发式算法明显优于降序最佳适应算法，且随着问题规 模的增大，其优势更加明显. 60 (2)尽管当问题规模增大时，贪婪策略的启发式 算法结果与问题下界差值增大，但是其偏离下界的百 20 分比却维持在较低水平（低于3%），说明贪婪策略的 启发式算法一直保持较好的求解效果，且在圆坯数量 0050100i150200250300350400450500 订单数量 较少时效果更好 在算法运行时间方面，由于贪婪策略的启发式算 图4贪婪策略的启发式算法与降序最佳适应算法运行时间对 比图 法的复杂度要明显高于降序最佳适应算法.随着订单 Fig.4 Comparison between HAGS and BFD in operating time 数量的增加，贪婪策略的启发式算法的运行时间明显 增加，而降序最佳适应算法的运行时间保持稳定，算法 4 结论 运行时间对比结果如图4所示：随着订单数量的增加， 贪婪策略的启发式算法的运行时间大致呈线性递增， 无缝钢管坯料设计问题是从无缝钢管生产过程中 而降序最佳适应算法的运行时间维持在10s以下.虽 提取的实际问题，与热轧板材的板坯设计和一维装箱 然在算法运行效率方面较降序最佳适应算法略差，但 问题均有相似性.但是，由于订单在圆坯中有最小分 是，作为离线求解算法，贪婪策略的启发式算法可以满 配支数的限制，坯料设计成为与上述问题存在本质区 足实际生产需求 别的新工业工程问题.本文给出了无缝钢管坯料设计工程科学学报，第 39 卷，第 4 期 表 4 随机数据仿真实验测试结果 Table 4 Simulation test results in random data 订单数量 圆坯重量/t 下界 HAGS 算法 BFD 算法 圆坯使用数量 圆坯使用数量 偏离率/% 圆坯使用数量 偏离率/% 7 9. 55 9. 75 2. 09 10. 3 7. 85 10 8 8. 45 8. 65 2. 37 8. 65 2. 37 9 7. 65 7. 75 1. 31 7. 9 3. 27 10 6. 95 7 0. 72 7. 1 2. 16 20 7 19. 5 19. 85 1. 79 20. 3 4. 1 8 17 17. 2 1. 18 17. 5 2. 94 9 15. 15 15. 3 0. 99 15. 8 4. 29 10 13. 8 13. 9 0. 72 14 1. 45 50 7 44. 8 45. 8 2. 23 45. 9 2. 46 8 39. 4 39. 55 0. 38 40. 05 1. 65 9 35. 15 35. 55 1. 14 35. 6 1. 28 10 31. 65 32 1. 11 32. 3 2. 05 100 7 84. 8 87. 33 2. 98 93. 62 10. 4 8 74. 2 75. 5 1. 75 80. 15 8. 02 9 65. 95 66. 83 1. 33 71. 29 8. 1 10 59. 36 61 2. 76 65. 87 10. 97 200 7 168. 9 172. 76 2. 29 181. 2 7. 28 8 147. 8 149. 77 1. 34 157. 23 6. 39 9 131. 37 134. 6 2. 46 140. 98 7. 32 10 118. 23 121. 3 2. 6 127. 1 7. 5 500 7 423. 9 435. 31 2. 69 448. 65 5. 84 8 370. 9 377. 32 1. 73 387. 98 4. 6 9 329. 71 333. 18 1. 05 343. 72 4. 25 10 296. 74 301. 5 1. 6 308. 63 4. 01 注: HAGS 偏离率( % ) = ( HAGS 算法圆坯使用数量 － 下界圆坯使用数量) /下界圆坯使用数量 × 100% ; BFD 偏离率( % ) = ( BFD 算法圆 坯使用数量 － 下界圆坯使用数量) /下界圆坯使用数量 × 100% ． 从表 4 可以得到以下结论． ( 1) 总的来看，贪婪策略的启发式算法求得的圆 坯数量均低于降序最佳适应算法，说明贪婪策略的启 发式算法明显优于降序最佳适应算法，且随着问题规 模的增大，其优势更加明显． ( 2) 尽管当问题规模增大时，贪婪策略的启发式 算法结果与问题下界差值增大，但是其偏离下界的百 分比却维持在较低水平( 低于 3% ) ，说明贪婪策略的 启发式算法一直保持较好的求解效果，且在圆坯数量 较少时效果更好． 在算法运行时间方面，由于贪婪策略的启发式算 法的复杂度要明显高于降序最佳适应算法． 随着订单 数量的增加，贪婪策略的启发式算法的运行时间明显 增加，而降序最佳适应算法的运行时间保持稳定，算法 运行时间对比结果如图 4 所示: 随着订单数量的增加， 贪婪策略的启发式算法的运行时间大致呈线性递增， 而降序最佳适应算法的运行时间维持在 10 s 以下． 虽 然在算法运行效率方面较降序最佳适应算法略差，但 是，作为离线求解算法，贪婪策略的启发式算法可以满 足实际生产需求． 图 4 贪婪策略的启发式算法与降序最佳适应算法运行时间对 比图 Fig． 4 Comparison between HAGS and BFD in operating time 4 结论 无缝钢管坯料设计问题是从无缝钢管生产过程中 提取的实际问题，与热轧板材的板坯设计和一维装箱 问题均有相似性． 但是，由于订单在圆坯中有最小分 配支数的限制，坯料设计成为与上述问题存在本质区 别的新工业工程问题． 本文给出了无缝钢管坯料设计 · 046 ·