第5期 张文学等：基于约束满足的板坯设计模型与求解方法 ·645· 按最小自由度优先策略从订单和板坯中选取可 法，本文给出以下两个参照算法 分配订单-板坯对(，)：若不存在(i,j),则为 (1)问题P的下界算法(lower algorithm,LA): 0新增一块板坯S,令j=j六 根据定理1，将变量x:的取值范围放宽，变为连续变 Step3(值选择：订单重量分配) 量，即不考虑订单的最小分配重量限制，则可求出问 针对已选取的(，)，按最大可行量分配策 题的下界.当然，该算法所得结果只是一个下界，并 略为x赋值；并更新0、S、mP和c分· 不一定是可行解 Step4(终止条件) (2)降序最佳适应(best fit deceasing,.BFD)算 重复Step2到Step3,直到O'=⑦：输出结果并 法：先对订单按g:%W(%为取余运算)的值降序排 终止算法.[算法结束] 序，当该值相同时按δ：降序排序；再对每个板坯进 上述CSMSQ算法是一个循环求解的过程，下面 行标记，若己经有订单被分配到该板坯则标记为1， 的定理3表明这个循环求解过程一定是收敛的 否则标记为0：接着对每个订单，检查所有标记为1 定理3 CSMSQ算法在有限步骤内收敛. 的板坯，分配到最适合该订单的板坯中，如果没有该 证明对给定的订单集合O,其总订单重量 板坯，则开启标记为0的板坯，并将该订单分配到新 开启的板坯，直到分配完所有订单.BFD算法是针 三8，为固定值根据最大可行量分配策略，在 对装箱问题行之有效的经典算法☒ CSMSQ算法的每一次循环中，订单的未分配总重量 4.2实验结果与分析 三L都以离散值p,9-8}的形式单调递减 为了评价本文提出的CSMSQ算法的有效性，根 据钢铁企业的实际生产情况，按如下方式生成实验 因此，由CSMSQ算法的终止条件O'=☑可知，其一 数据：订单重量g:∈090,300]，单位为t,其中 定在有限步骤内收敛.证毕] U[a,b]表示在区间[a,b]上的均匀分布；板坯的固 4数据实验 定重量W=28t:订单的最小分配重量为10t每一 组实验独立运行30次，记录板坯数量平均值和运行 4.1参照算法 时间平均值.实验中采用Microsoft Visual VC++ 由于目前还未能找到针对客户订单的规格需求 6.0实现算法.实验环境为Pentium4/1GHz/ 为固定值，且订单有最小分配重量限制的板坯设计 512MB/Windows XP Professional..实验结果如表1 问题的相关文献与算法，因此为了评价CSMSQ算 所示 表1实验结果 Table 1 Experimental results LA CSMSO BFD 订单数 C CT/s CC PRD/ CT/s CB PRD/% CT/s 50 357 0.01300 360 0.84 0.01143 372 4.20 0.04458 75 531 0.02133 537 1.13 0.02133 569 7.16 0.06746 100 705 0.03280 714 1.28 0.03436 753 6.81 0.06804 125 879 0.05153 891 1.37 0.05103 950 8.08 0.09903 150 1054 0.07083 1069 1.42 0.07083 1159 9.96 0.07950 175 1230 0.09583 1248 1.46 0.09686 1374 11.71 0.12493 200 1403 0.12446 1424 1.50 0.12236 1572 12.05 0.14012 注：C、C和CB分别为算法LA、CSMSQ和BFD所得板坯数：PRDC=100%×(Ce-C)/C,PRDB=100%×(CB-CL)/CL.CT是算法所 用计算时间，s 从表1的实验结果中可以得到以下几点：(1) 下界(LA的结果)的偏差很小，在上述实验中不超 针对板坯设计问题特点开发的CSMSQ算法得到的 过1.5%.这表明本文提出的关于变量选择的最小 解，无论在板坯数上还是在相对稳定性上，都明显优 自由度优先策略、关于值选择的最大可行量分配策 于BFD算法.而且随着问题规模的增大，其优势更 略有效地利用了问题的特点.(3)CSMSQ算法具有 加显著.(2)CSMSQ算法得到的板坯数量与问题的 很高的计算效率（在上述实验中，计算时间都小于第 5 期 张文学等: 基于约束满足的板坯设计模型与求解方法 按最小自由度优先策略从订单和板坯中选取可 分配订单--板坯对( i * ，j * ) ; 若不存在( i * ，j * ) ，则为 Oi* 新增一块板坯 Sj'，令 j * = j'． Step 3 ( 值选择: 订单重量分配) 针对已选取的( i * ，j * ) ，按最大可行量分配策 略为 xi* j* 赋值; 并更新 O'、S'、m、pi* 和 cj* ． Step 4 ( 终止条件) 重复 Step 2 到 Step 3，直到 O' = ; 输出结果并 终止算法． ［算法结束］ 上述 CSMSQ 算法是一个循环求解的过程，下面 的定理 3 表明这个循环求解过程一定是收敛的． 定理 3 CSMSQ 算法在有限步骤内收敛． 证明 对给定的订单集合 O，其总订单重量 ∑ n i = 1 gi 为固 定 值． 根据最大可行量分配策略，在 CSMSQ 算法的每一次循环中，订单的未分配总重量 ∑ n i = 1 pi 都以离散值{ pi，cj ，pi － δi} 的形式单调递减． 因此，由 CSMSQ 算法的终止条件 O' = 可知，其一 定在有限步骤内收敛． ［证毕］ 4 数据实验 4. 1 参照算法 由于目前还未能找到针对客户订单的规格需求 为固定值，且订单有最小分配重量限制的板坯设计 问题的相关文献与算法，因此为了评价 CSMSQ 算 法，本文给出以下两个参照算法． ( 1) 问题 P 的下界算法( lower algorithm，LA) : 根据定理 1，将变量 xij的取值范围放宽，变为连续变 量，即不考虑订单的最小分配重量限制，则可求出问 题的下界． 当然，该算法所得结果只是一个下界，并 不一定是可行解． ( 2) 降序最佳适应( best fit deceasing，BFD) 算 法: 先对订单按 gi% W( % 为取余运算) 的值降序排 序，当该值相同时按 δi 降序排序; 再对每个板坯进 行标记，若已经有订单被分配到该板坯则标记为 1， 否则标记为 0; 接着对每个订单，检查所有标记为 1 的板坯，分配到最适合该订单的板坯中，如果没有该 板坯，则开启标记为 0 的板坯，并将该订单分配到新 开启的板坯，直到分配完所有订单． BFD 算法是针 对装箱问题行之有效的经典算法［12］． 4. 2 实验结果与分析 为了评价本文提出的 CSMSQ 算法的有效性，根 据钢铁企业的实际生产情况，按如下方式生成实验 数据: 订 单 重 量 gi ∈ U［90，300］，单 位 为 t，其 中 U［a，b］表示在区间［a，b］上的均匀分布; 板坯的固 定重量 W = 28 t; 订单的最小分配重量为 10 t． 每一 组实验独立运行 30 次，记录板坯数量平均值和运行 时间平均值． 实验中采用 Microsoft Visual VC + + 6. 0 实 现 算 法． 实 验 环 境 为 Pentium4 /1 GHz/ 512 MB /Windows XP Professional． 实验结果如表 1 所示． 表 1 实验结果 Table 1 Experimental results 订单数 LA CSMSQ BFD CL CT /s CC PRDC /% CT /s CB PRDB /% CT /s 50 357 0. 013 00 360 0. 84 0. 011 43 372 4. 20 0. 044 58 75 531 0. 021 33 537 1. 13 0. 021 33 569 7. 16 0. 067 46 100 705 0. 032 80 714 1. 28 0. 034 36 753 6. 81 0. 068 04 125 879 0. 051 53 891 1. 37 0. 051 03 950 8. 08 0. 099 03 150 1 054 0. 070 83 1 069 1. 42 0. 070 83 1 159 9. 96 0. 079 50 175 1 230 0. 095 83 1 248 1. 46 0. 096 86 1 374 11. 71 0. 124 93 200 1 403 0. 124 46 1 424 1. 50 0. 122 36 1 572 12. 05 0. 140 12 注: CL、CC 和 CB 分别为算法 LA、CSMSQ 和 BFD 所得板坯数; PRDC = 100% × ( CC － CL ) /CL，PRDB = 100% × ( CB － CL ) /CL ． CT 是算法所 用计算时间，s． 从表 1 的实验结果中可以得到以下几点: ( 1) 针对板坯设计问题特点开发的 CSMSQ 算法得到的 解，无论在板坯数上还是在相对稳定性上，都明显优 于 BFD 算法． 而且随着问题规模的增大，其优势更 加显著． ( 2) CSMSQ 算法得到的板坯数量与问题的 下界( LA 的结果) 的偏差很小，在上述实验中不超 过 1. 5% ． 这表明本文提出的关于变量选择的最小 自由度优先策略、关于值选择的最大可行量分配策 略有效地利用了问题的特点． ( 3) CSMSQ 算法具有 很高的计算效率( 在上述实验中，计算时间都小于 ·645·