李铁克等：单一尺寸圆坯的无缝钢管坯料设计模型与算法 ·637 最优解。因此，本文提出一种基于贪婪策略的启发式 heuristic algorithm based on greedy strategy, 配支数，遵循如下订单分配准则：()若号」≥C, HAGS)可以在较短时间内获得问题的满意解，图2给 出了算法框架.算法第一阶段在满足最小分配支数条 则w=c:2)若c≤品」<C且c-总」≥ 件下，将订单依次放入圆坯，得到初始解：第二阶段通 过贪婪策略改进初始解，得到满意解.算法收敛性的 G,则=」3)若c≤e」<c且C- 证明保证了算法在有限时间内可以得到问题满意解. <C,但是C≥2C,则xw=C-C。;(4)否 L10。 输入：订单 输入：订单 和圆坏参数 分配方案 则，x=0. 圆坯按使用重量 其中，条件(1)表示当圆坯剩余重量大于订单未 订单按自由度 由低到高排序 由高到低排序 分配钢管总重量时，将订单装入该圆坯：条件(2)表示 选择两支圆坯 当圆坯最大可容纳订单钢管支数满足并且使装入后的 依次选择订单 剩余支数也满足最小分配支数时，圆坯可以分配的钢 是香 重新分配两支圆不 管支数为最大可容纳订单钢管支数：条件(3)表示当 可以放入现有 包含的订单钢管 、圆坯？ 圆坯最大可容纳订单钢管支数满足最小分配支数，但 是 新增圆坯 装入后的剩余支数不满足最小分配支数时，如果未分 是否满足 否 终止条件？ 配钢管支数不小于两倍的最小分配支数，预留出最小 分配订单 是 分配支数，将其余钢管均分配给圆坯：条件(4)不存在 输出：订单 可行分配方案，圆坯可以分配的钢管支数为0. 输出：订单 分配方案 第一阶段 匹配方案 第二阶段 根据订单分配准则，令i表示订单集合O排序后 的订单顺序号，则贪婪策略的启发式算法第一阶段步 图2贪婪策略的启发式算法整体框架 骤描述如下 Fig.2 HAGS algorithm process framework 输入订单和圆坯参数值：0，。，C。,C,C. 2.1第一阶段：贪婪准则订单分配 Stepl将全部订单按自由度由低到高排序，令 为了将订单可以按照某种顺序依次放入圆坯中， i=1,转至Step2. 引入订单自由度的概念来衡量订单分配的困难程度 Step2令b=1,转至Step4: 订单自由度与订单能够分配的圆坯数和订单钢管的理 Step3令b=-b+1,转至Step4: 论重量有关，订单能够分配的圆坯数越大，订单自由度 Step4根据订单分配准则计算x·如果x≠0， 越大：当订单能够分配的圆坯数相同时，订单钢管的理 更新圆坯b的使用重量u,=山+心，xw,圆坯余重量 论重量越小，订单自由度越大.表1中有三个订单，订 e。=e-10,x和订单o的未分配支数C=C-xw,转 单1和3能够分配的圆坯数均为4(=20/5=16/4)， 至Step5;否则，转至Step3. 订单2能够分配的圆坯数为3(=15/5).因此，三个订 Step5如果C。=0,转至Step6;否则，至Step3. 单的自由度由低到高排序为订单2、订单3和订单1. Step6若i>n,终止循环，转入输出：否则，令i= 将订单按照订单自由度排序后，根据最小化圆坯剩余 i+1转至Step2. 量准则可以确定订单在圆坯中的分配支数 输出初始分配方案 表1订单自由度排序示例 在算法第一阶段中，排序的复杂度为O(nlog n), Table 1 Example for the freedom degree of orders 订单分配最坏情况下的复杂度为O(mn).因此，算法 订单编号 订单支数 钢管重量上最小分配支数 第一阶段的整体计算复杂度为O(mm). 1 20 0.28 5 2.2第二阶段：初始方案优化改进 针对算法第一阶段得到的初始分配方案，算法第 15 0.30 5 二阶段设计了订单重分配准则，将圆坯使用重量作为 16 0.40 贪婪策略的核心，最大化每个圆坯的使用重量，从而优 为描述贪婪准则和算法步骤，对其中使用的数学 化问题的目标.订单重分配准则是指将某两支圆坯包 符号做如下定义：令C表示订单0的未分配钢管支 含的订单在圆坯之间进行重新分配，尽可能多地使用 其中一支圆坯的重量.具体准则如下所示 数山=三 (wx)表示圆坯b已使用的重量；e6=C- 订单重分配准则对于圆坯集合B中任意两支圆 u。表示圆坯b的剩余重量.那么，订单o在圆坯b的分 坯，设其使用重量为山：山，根据订单分配准则将圆李铁克等: 单一尺寸圆坯的无缝钢管坯料设计模型与算法 最优解． 因此，本文提出一种基于贪婪策略的启发式 算 法 ( heuristic algorithm based on greedy strategy， HAGS) 可以在较短时间内获得问题的满意解，图 2 给 出了算法框架． 算法第一阶段在满足最小分配支数条 件下，将订单依次放入圆坯，得到初始解; 第二阶段通 过贪婪策略改进初始解，得到满意解． 算法收敛性的 证明保证了算法在有限时间内可以得到问题满意解． 图 2 贪婪策略的启发式算法整体框架 Fig． 2 HAGS algorithm process framework 2. 1 第一阶段: 贪婪准则订单分配 为了将订单可以按照某种顺序依次放入圆坯中， 引入订单自由度的概念来衡量订单分配的困难程度． 订单自由度与订单能够分配的圆坯数和订单钢管的理 论重量有关，订单能够分配的圆坯数越大，订单自由度 越大; 当订单能够分配的圆坯数相同时，订单钢管的理 论重量越小，订单自由度越大． 表 1 中有三个订单，订 单 1 和 3 能够分配的圆坯数均为 4( = 20 /5 = 16 /4) ， 订单2 能够分配的圆坯数为3( = 15 /5) ． 因此，三个订 单的自由度由低到高排序为订单 2、订单 3 和订单 1． 将订单按照订单自由度排序后，根据最小化圆坯剩余 量准则可以确定订单在圆坯中的分配支数． 表 1 订单自由度排序示例 Table 1 Example for the freedom degree of orders 订单编号 订单支数 钢管重量/t 最小分配支数 1 20 0. 28 5 2 15 0. 30 5 3 16 0. 40 4 为描述贪婪准则和算法步骤，对其中使用的数学 符号做如下定义: 令 CＲ o 表示订单 o 的未分配钢管支 数; ub = ∑ n o = 1 ( wo xob ) 表示圆坯 b 已使用的重量; εb = C － ub 表示圆坯 b 的剩余重量． 那么，订单 o 在圆坯 b 的分 配支数 xob遵循如下订单分配准则: ( 1) 若 εb wo ≥CＲ o ， 则 xob = CＲ o ; ( 2) 若 Cmin o ≤ εb wo ＜ CＲ o 且 CＲ o － εb wo ≥ Cmin o ，则 xob = εb wo ; ( 3) 若 Cmin o ≤ εb wo ＜ CＲ o 且 CＲ o － εb wo ＜ Cmin o ，但是 CＲ o ≥2Cmin o ，则 xob = CＲ o － Cmin o ; ( 4) 否 则，xob = 0． 其中，条件( 1) 表示当圆坯剩余重量大于订单未 分配钢管总重量时，将订单装入该圆坯; 条件( 2) 表示 当圆坯最大可容纳订单钢管支数满足并且使装入后的 剩余支数也满足最小分配支数时，圆坯可以分配的钢 管支数为最大可容纳订单钢管支数; 条件( 3) 表示当 圆坯最大可容纳订单钢管支数满足最小分配支数，但 装入后的剩余支数不满足最小分配支数时，如果未分 配钢管支数不小于两倍的最小分配支数，预留出最小 分配支数，将其余钢管均分配给圆坯; 条件( 4) 不存在 可行分配方案，圆坯可以分配的钢管支数为 0． 根据订单分配准则，令 i 表示订单集合 O 排序后 的订单顺序号，则贪婪策略的启发式算法第一阶段步 骤描述如下． 输入 订单和圆坯参数值: O，wo，Co，Cmin o ，C． Step1 将全部订单按自由度由低到高排序，令 i = 1，转至 Step2． Step2 令 b = 1，转至 Step4; Step3 令 b = b + 1，转至 Step4; Step4 根据订单分配准则计算 xob ． 如果 xob≠0， 更新圆坯 b 的使用重量 ub = ub + wo xob，圆坯余重量 εb = εb － wo xob和订单 o 的未分配支数 CＲ o = CＲ o － xob，转 至 Step5; 否则，转至 Step3． Step5 如果 CＲ o = 0，转至 Step6; 否则，至 Step3． Step6 若 i ＞ n，终止循环，转入输出; 否则，令 i = i + 1 转至 Step2． 输出 初始分配方案． 在算法第一阶段中，排序的复杂度为 O( nlog n) ， 订单分配最坏情况下的复杂度为 O( mn) ． 因此，算法 第一阶段的整体计算复杂度为 O( mn) ． 2. 2 第二阶段: 初始方案优化改进 针对算法第一阶段得到的初始分配方案，算法第 二阶段设计了订单重分配准则，将圆坯使用重量作为 贪婪策略的核心，最大化每个圆坯的使用重量，从而优 化问题的目标． 订单重分配准则是指将某两支圆坯包 含的订单在圆坯之间进行重新分配，尽可能多地使用 其中一支圆坯的重量． 具体准则如下所示． 订单重分配准则对于圆坯集合 B 中任意两支圆 坯 i、j，设其使用重量为 ui、uj ，根据订单分配准则将圆 · 736 ·