116 工程科学学报，第37卷，第1期 Step4.2若∫(x)=∫(x),按照EDD规则和钢 (2)变邻域搜索算法(VNS-I).与VNS-Ⅱ算法 种升序规则对当前解x进行处理，并计算，(x)和 相同，也用变邻域搜索算法优化设备调整时间，但采用 (x):若2(x)>6(x)或2(x)≤5(x)∧3(x)>f3 随机的方式来对轧制单元排序，达到优化拖期生产惩 (x),则令=x,否则转Step5; 罚和钢种跳跃惩罚的目的 Step4.3若f(x)<f(x),则转Step5; 考虑到影响算法的主要因素为算法的参数以及问 Step5判断终止条件. 题的规模，并经过前期大量数据实验验证，将VNS一I Step5.l令i=i+l,若i>MaxIter,则转Step5.2, 和VNS-Ⅱ算法的参数均设置为：最大寻优次数Max- 否则返回执行Step3; Iter=200;在局部搜索中2opt算子和or-opt算子被选 Step5.2算法停止，输出历史最优解x,作为最 择的概率均设为0.5；模拟退火接收准则中初始温度 终解 T。=l0,每隔n,=MaxIter/10后更新温度，退火系数 3数据实验 a=0.95. 实验数据设置如下：G=6,41=15min,t2= 3.1实验数据与环境 20 min,=10 min. 为了验证本文提出的模型和算法，现以某钢铁厂 本文算法采用Microsoft Visual Ci#编程实现，实验 热轧圆钢生产线的10组实际生产数据为算例进行仿 环境为Core i5/2.50GHz/2GB/Windows7 Ultimate. 真实验.将本文提出的算法记为VNS-Ⅱ算法，为进一 3.2实验结果与分析 步考察算法的求解性能，实验中将其与以下两种算法 针对每个算例分别用三种算法运行10次后取平 比较. 均值，得到的实验结果如表1所示，其中m和n分别代 (1)约束满足算法(CSP).根据文中给出的变量 表轧制规格数和轧制单元数，和分别表示设备 选择规则和值选择规则，选择变量后从变量的值域中 调整时间、拖期生产惩罚和钢种跳跃惩罚的优化值，运 寻找一组满足约束的值赋给变量，然后进行约束传播. 行时间是指VNS-Ⅱ算法的求解时间. 表1实验结果 Table 1 Experimental results 运行 CSP/min VNS-1/min VNS-I/min 算例 m n 时间/s f f左 公 万 f 5 f3 15 60 8.5 1670 16.5 406 1595 23.8 562 1595 10.7 286 2 20 50 10.3 1945 30.0 396 1835 56.7 424 1825 24.3 214 3 25 80 15.8 2110 38.3 460 2000 47.9 540 2000 28.8 283 30 105 23.2 2440 47.2 560 2260 55.0 674 2260 15.7 374 36 245 55.4 2590 124.7 580 2325 140.5 780 2320 104.4 469 6 40 360 63.3 2840 150.5 1176 2515 178.0 1434 2500 96.0 645 > 420 76.5 2906 267.0 1461 2716 311.3 1752 2716 152.5 1074 吃 580 92.0 3149 303.9 1878 2889 388.6 1904 2889 264.8 1342 9 55 675 117.0 3328 385.0 1957 3108 460.4 2136 3108 356.5 1675 10 60 800 142.6 3798 516.6 2156 3508 577.9 2318 3503 486.9 1994 为进一步说明VSⅡ算法的有效性和收敛性，选 取算例5（问题规模为36×245）的计算结果进行展示. 2650 2600 图1给出了设备调整时间随迭代次数的变化曲线. 2550 由上述实验结果可以得到以下结论： 2500 2450 (1)针对不同的问题规模，VNS-Ⅱ算法得到的解 2400 的质量都要优于约束满足问题算法和VNSH算法. 一 2350 始2300 方面，VNS-Ⅱ算法是以约束满足问题算法得到的解作 2250 2200 为初始解进行优化，而约束满足问题算法在求解过程 215 020305080100150180200250300 中采用贪婪策略来优化三个优化指标，容易陷入局部 送代次数 最优解，VNS-Ⅱ算法能够在此基础上利用变邻域搜索 图1设备调整时间变化曲线 算法的特性对解进行优化改善，得到更好的解：另一方 Fig.1 Graph for setup time工程科学学报，第 37 卷，第 1 期 Step4. 2 若 f1 ( xb ) = f1 ( x) ，按照 EDD 规则和钢 种升序规则对当前解 x 进行处理，并计算 f2 ( x) 和 f3 ( x) ; 若 f2 ( xb ) ＞ f2 ( x) 或 f2 ( xb ) ≤f2 ( x) ∧f3 ( xb ) ＞ f3 ( x) ，则令 xb = x，否则转 Step5; Step4. 3 若 f1 ( xb ) ＜ f1 ( x) ，则转 Step5; Step5 判断终止条件． Step5. 1 令 i = i + 1，若 i ＞ MaxIter，则转 Step5. 2， 否则返回执行 Step3; Step5. 2 算法停止，输出历史最优解 xb 作为最 终解． 3 数据实验 3. 1 实验数据与环境 为了验证本文提出的模型和算法，现以某钢铁厂 热轧圆钢生产线的 10 组实际生产数据为算例进行仿 真实验． 将本文提出的算法记为 VNS--II 算法，为进一 步考察算法的求解性能，实验中将其与以下两种算法 比较． ( 1) 约束满足算法( CSP) ． 根据文中给出的变量 选择规则和值选择规则，选择变量后从变量的值域中 寻找一组满足约束的值赋给变量，然后进行约束传播． ( 2) 变邻域搜索算法( VNS--I) ． 与 VNS--II 算法 相同，也用变邻域搜索算法优化设备调整时间，但采用 随机的方式来对轧制单元排序，达到优化拖期生产惩 罚和钢种跳跃惩罚的目的． 考虑到影响算法的主要因素为算法的参数以及问 题的规模，并经过前期大量数据实验验证，将 VNS--I 和 VNS--II 算法的参数均设置为: 最大寻优次数 Max￾Iter = 200; 在局部搜索中 2-opt 算子和 or-opt 算子被选 择的概率均设为 0. 5; 模拟退火接收准则中初始温度 T0 = 10，每隔 nT = MaxIter /10 后更新温度，退火系 数 α = 0. 95． 实验数据设置如下: Gmax = 6，t1 = 15 min，t2 = 20 min，t3 = 10 min． 本文算法采用 Microsoft Visual C#编程实现，实验 环境为 Core i5 /2. 50GHz /2GB /Windows 7 Ultimate． 3. 2 实验结果与分析 针对每个算例分别用三种算法运行 10 次后取平 均值，得到的实验结果如表 1 所示，其中 m 和 n 分别代 表轧制规格数和轧制单元数，f1、f2 和 f3 分别表示设备 调整时间、拖期生产惩罚和钢种跳跃惩罚的优化值，运 行时间是指 VNS--II 算法的求解时间． 表 1 实验结果 Table 1 Experimental results 算例 m n 运行 时间/ s CSP /min VNS--I /min VNS--II /min f1 f2 f3 f1 f2 f3 f1 f2 f3 1 15 60 8. 5 1670 16. 5 406 1595 23. 8 562 1595 10. 7 286 2 20 50 10. 3 1945 30. 0 396 1835 56. 7 424 1825 24. 3 214 3 25 80 15. 8 2110 38. 3 460 2000 47. 9 540 2000 28. 8 283 4 30 105 23. 2 2440 47. 2 560 2260 55. 0 674 2260 15. 7 374 5 36 245 55. 4 2590 124. 7 580 2325 140. 5 780 2320 104. 4 469 6 40 360 63. 3 2840 150. 5 1176 2515 178. 0 1434 2500 96. 0 645 7 45 420 76. 5 2906 267. 0 1461 2716 311. 3 1752 2716 152. 5 1074 8 50 580 92. 0 3149 303. 9 1878 2889 388. 6 1904 2889 264. 8 1342 9 55 675 117. 0 3328 385. 0 1957 3108 460. 4 2136 3108 356. 5 1675 10 60 800 142. 6 3798 516. 6 2156 3508 577. 9 2318 3503 486. 9 1994 为进一步说明 VNS--II 算法的有效性和收敛性，选 取算例 5( 问题规模为 36 × 245) 的计算结果进行展示． 图 1 给出了设备调整时间随迭代次数的变化曲线． 由上述实验结果可以得到以下结论: ( 1) 针对不同的问题规模，VNS--II 算法得到的解 的质量都要优于约束满足问题算法和 VNS--I 算法． 一 方面，VNS--II 算法是以约束满足问题算法得到的解作 为初始解进行优化，而约束满足问题算法在求解过程 中采用贪婪策略来优化三个优化指标，容易陷入局部 最优解，VNS--II 算法能够在此基础上利用变邻域搜索 算法的特性对解进行优化改善，得到更好的解; 另一方 图 1 设备调整时间变化曲线 Fig． 1 Graph for setup time · 611 ·