·638· 工程科学学报，第39卷，第4期 坯i寸包含的订单重新分配到圆坯i中，假设其使用 2.3算法的收敛性 重量变为为u、u如果满足条件min{u,u}<min 上述贪婪策略的启发式算法是一个循环求解的过 {,w},那么，用新的分配方案代替旧的分配方案：否 程，定理2表明这个循环求解过程一定是收敛的，即算 则，保持圆坯i、分配方案不变 法在循环了有限次数后，一定能够得到问题的可行解。 根据订单重分配准则，令i、表示按圆坯使用重量 【定理2】贪婪策略的启发式算法在有限步骤内 排序后的圆坯顺序号，则贪婪策略的启发式算法第二 收敛 阶段步骤描述如下 证明：对于任意两支圆坯i,设其在重分配前后 输入第一阶段初始分配方案 的圆坯使用重量分别为u,、u,和u、u根据贪婪策略 Stepl 如果分配方案满足条件 (C- 的启发式算法中的订单重分配准则可知，在每一次循 环中，均有Max{uu}≥Max{u,u}.为此，定义变量 会(，小<C转至输出：否则，转至sp2 n= ∑∑1以-4，由上述结论可知，在每一次循环 Step2删除圆坯使用重量为0的圆坯序号，将剩 中，η以离散的形式单调递增.由圆坯的重量上限为C 余圆坯按照圆坯使用重量降序排序，重新对剩余圆坯 进行编号，得到新的圆坯使用数量m的值.令i=1,转 可知：ijeB,4,-“,≤C,故n=∑∑1叫-u,l存 至Step3. 在上界值 Step3令j=m,转至Step4. 综上所述，在贪婪策略的启发式算法中，)= Step4若i<j,转至Step5;否则，转至Step6. Step5对圆坯i寸执行订单重分配准则.如果圆 ,I山-u:以离散的形式单调递增且有上界.所 坯i寸分配方案保持不变，令j=j-1转至Step4:否则， 以，贪婪策略的启发式算法在有限步骤内收敛.定理 转至Step2 得证 Step6若i=m-1,转至输出；否则，令i=i+1, 3算法测试 转至Step2. 输出输出订单一圆坯分配方案，算法终止 为验证贪婪策略的启发式算法的有效性和稳定 在算法第二阶段中，最坏情况下，排序的复杂度为 性，采用实际生产数据和仿真数据两组试验分别对算 0(mlog m),订单重分配的复杂度为0(mn).因此， 法进行测试.整体算法采用Microsoft Visual Studio C# 第二阶段的计算复杂度为O(mn). 2008编程实现，测试环境为Inter®Core(TM)i5- 综合算法第一阶段，贪婪策略的启发式算法的复 3470CPU/3.2 GHz/4 G/Windows 7 Professional. 3.1实际生产数据试验 杂度不超过0(m2n). 又因为m≤ 提取某钢铁企业一段时期内的相同钢种的订单， 根据实际生产中的最小生产重量为1.351的要求，求 :为常量，因此，贪婪策略的启 得每个订单的最小分配支数，汇总订单生产信息如表 发式算法的复杂度不超过0(n). 2所示. 表2订单基本信息汇总 Table 2 Order summary 订单编号 钢管重量： 钢管支数 最小分配支数 订单编号 钢管重量八 钢管支数 最小分配支数 01 0.188 32 11 0.353 27 4 02 0.217 28 7 12 0.359 16 4 03 0.239 之 6 13 0.365 21 04 0.245 12 6 14 0.410 16 4 05 0.251 24 6 15 0.416 9 4 06 0.256 21 6 16 0.456 8 3 07 0.296 20 17 0.467 3 08 0.302 28 18 0.473 3 09 0.308 9 19 0.502 12 3 10 0.348 9 20 0.513 3工程科学学报，第 39 卷，第 4 期 坯 i、j 包含的订单重新分配到圆坯 i、j 中，假设其使用 重量变为为 u'i、u'j ． 如果满足条件 min { u'i，u'j} ＜ min { ui，uj } ，那么，用新的分配方案代替旧的分配方案; 否 则，保持圆坯 i、j 分配方案不变． 根据订单重分配准则，令 i、j 表示按圆坯使用重量 排序后的圆坯顺序号，则贪婪策略的启发式算法第二 阶段步骤描述如下． 输入 第一阶段初始分配方案． Step1 如果分配方案满足条件 ∑ m b = ( 1 C － ∑ n o = 1 ( wo xob ) ) ＜ C，转至输出; 否则，转至 Step2． Step2 删除圆坯使用重量为 0 的圆坯序号，将剩 余圆坯按照圆坯使用重量降序排序，重新对剩余圆坯 进行编号，得到新的圆坯使用数量 m 的值． 令 i = 1，转 至 Step3． Step3 令 j = m，转至 Step4． Step4 若 i ＜ j，转至 Step5; 否则，转至 Step6． Step5 对圆坯 i、j 执行订单重分配准则． 如果圆 坯 i、j 分配方案保持不变，令 j = j － 1 转至 Step4; 否则， 转至 Step2． Step6 若 i = m － 1，转至输出; 否则，令 i = i + 1， 转至 Step2． 输出 输出订单—圆坯分配方案，算法终止． 在算法第二阶段中，最坏情况下，排序的复杂度为 O( mlog m) ，订单重分配的复杂度为 O( m2 n) ． 因此， 第二阶段的计算复杂度为 O( m2 n) ． 综合算法第一阶段，贪婪策略的启发式算法的复 杂度不超过 O( m2 n) ． 又因为 m≤ ∑ n o = 1 Co Cmin o ≤nMax Co Cmin o ，且 Max Co Cmin o 为常量，因此，贪婪策略的启 发式算法的复杂度不超过 O( n3 ) ． 2. 3 算法的收敛性 上述贪婪策略的启发式算法是一个循环求解的过 程，定理 2 表明这个循环求解过程一定是收敛的，即算 法在循环了有限次数后，一定能够得到问题的可行解． 【定理 2】贪婪策略的启发式算法在有限步骤内 收敛． 证明: 对于任意两支圆坯 i、j，设其在重分配前后 的圆坯使用重量分别为 ui、uj 和 u'i、u'j ． 根据贪婪策略 的启发式算法中的订单重分配准则可知，在每一次循 环中，均有 Max{ u'i，u'j } ≥Max{ ui，uj } ． 为此，定义变量 η = ∑ m i = 1 ∑ m j ＞ i | uj － ui | ，由上述结论可知，在每一次循环 中，η 以离散的形式单调递增． 由圆坯的重量上限为 C 可知: i，j∈B，| uj － ui | ≤C，故 η = ∑ m i = 1 ∑ m j ＞ i | uj － ui | 存 在上界值． 综上所 述，在贪婪策略的启发式算法中，η = ∑ m i = 1 ∑ m j ＞ i | uj － ui | 以离散的形式单调递增且有上界． 所 以，贪婪策略的启发式算法在有限步骤内收敛． 定理 得证． 3 算法测试 为验证贪婪策略的启发式算法的有效性和稳定 性，采用实际生产数据和仿真数据两组试验分别对算 法进行测试． 整体算法采用 Microsoft Visual Studio C# 2008 编 程 实 现，测 试 环 境 为 Inter  Core ( TM) i5-- 3470CPU /3. 2 GHz /4 G /Windows 7 Professional． 3. 1 实际生产数据试验 提取某钢铁企业一段时期内的相同钢种的订单， 根据实际生产中的最小生产重量为 1. 35 t 的要求，求 得每个订单的最小分配支数，汇总订单生产信息如表 2 所示． 表 2 订单基本信息汇总 Table 2 Order summary 订单编号 钢管重量/t 钢管支数 最小分配支数 订单编号 钢管重量/t 钢管支数 最小分配支数 01 0. 188 32 8 11 0. 353 27 4 02 0. 217 28 7 12 0. 359 16 4 03 0. 239 27 6 13 0. 365 21 4 04 0. 245 12 6 14 0. 410 16 4 05 0. 251 24 6 15 0. 416 9 4 06 0. 256 21 6 16 0. 456 8 3 07 0. 296 20 5 17 0. 467 12 3 08 0. 302 28 5 18 0. 473 7 3 09 0. 308 19 5 19 0. 502 12 3 10 0. 348 9 4 20 0. 513 8 3 · 836 ·