单一尺寸圆坯的无缝钢管坯料设计模型与算法

工程科学学报，第39卷，第4期：634641,2017年4月 Chinese Journal of Engineering,Vol.39,No.4:634-641,April 2017 DOI:10.13374/j.issn2095-9389.2017.04.020:http://journals.ustb.edu.cn 单一尺寸圆坯的无缝钢管坯料设计模型与算法 李铁克，刘玉琢四，王柏琳，栾治伟 北京科技大学东陵经济管理学院，北京100083 ☒通信作者，E-mail:sunrise8818@hotmail.com 摘要无缝钢管坯料设计是在满足生产工艺要求下，将客户订单钢管合理地分配到生产原料圆坯的过程.实际生产中的 批量原则使得每个钢管订单在圆坯中有最小分配重量要求；由于无缝钢管分配支数必须取整，导致钢管订单在圆坯中的分配 重量并非连续取值.因此，比起相关的板坯设计问题和装箱问题，无缝钢管坯料设计的求解更为复杂.本文给出了无缝钢管 坯料设计问题的一般性描述，并建立了混合整数规划模型.针对库存中只有单一尺寸圆坯的情况，简化了问题模型并且求得 了问题的下界.结合问题特点，提出了基于贪婪策略的两阶段启发式算法，并用实际生产数据和仿真数据验证了算法求解此 类问题具有很好的有效性和稳定性. 关键词坯料设计：无缝钢管：贪婪策略：启发式算法 分类号0221.4：TG335.7 Model and algorithm of the billet design problem in the production of seamless steel tubes with a single billet size LI Tie-ke,LIU Yu-zhuo,WANG Bai-in,LUAN Zhi-ei Donlinks School of Economics and Management,University of Science and Technology Beijing,Beijing 100083,China Corresponding author,E-mail:sunrise8818@hotmail.com ABSTRACT The billet design problem (BDP)in seamless steel tube production is to assign order tubes to billets under process constraints.Because of the batch rule in practical production,each order has a minimum weight of tubes assigned to any billet.Mean- while,as the number of tubes assigned to a billet must be an integer,the weight of tubes assigned to any billet is not continuous in its domain.Thus,the BDP discussed herein is more difficult to solve than the slab design and bin packing problems.In this study,a multi-objective mix-integer programming model was built based on a generalized description of the BDP,which is proved to be non-de- terministic polynomial (NP)hard.For the case with single billet size wherein two objectives in the model are equivalent,a simplified model was set up and the lower bound of the objective could be found.Further,a two-stage heuristic algorithm based on greedy strate- gy was proposed to solve the problem.Finally,using computational results,it was proved that the algorithm is effective and efficient in solving the BDP. KEY WORDS billet design:seamless steel tube:greedy strategy;heuristic algorithm 无缝钢管生产计划中的坯料设计环节（以下简称外径、钢种以及质量，通常情况下为尺寸确定的定尺 坯料设计)是将客户订单和生产原料联系起来的纽坯.坯料设计的任务就是将订单钢管参数转化为圆坯 带.在坯料设计过程中，主要考虑的客户订单参数包 参数，在满足工艺要求的前提下，将订单钢管合理分配 括订单钢管的外径、壁厚、长度、钢种以及订单重量；生 到圆坯中，建立订单钢管和圆坯的匹配关系.坯料设 产原料是来自炼钢连铸车间的圆坯，其主要参数包括 计问题是无缝钢管生产计划中必须解决的问题，它对 收稿日期：201607-20 基金项目：中央高校基本科研业务费资助项目(FRF-BD-16O06A):国家自然科学基金资助项目(71231OO1):北京市自然科学基金资助项 目(9174038)

工程科学学报，第 39 卷，第 4 期: 634--641，2017 年 4 月 Chinese Journal of Engineering，Vol． 39，No． 4: 634--641，April 2017 DOI: 10． 13374 /j． issn2095--9389． 2017． 04． 020; http: / /journals． ustb． edu． cn 单一尺寸圆坯的无缝钢管坯料设计模型与算法 李铁克，刘玉琢，王柏琳，栾治伟 北京科技大学东陵经济管理学院，北京 100083 通信作者，E-mail: sunrise8818@ hotmail． com 摘 要 无缝钢管坯料设计是在满足生产工艺要求下，将客户订单钢管合理地分配到生产原料圆坯的过程． 实际生产中的 批量原则使得每个钢管订单在圆坯中有最小分配重量要求; 由于无缝钢管分配支数必须取整，导致钢管订单在圆坯中的分配 重量并非连续取值． 因此，比起相关的板坯设计问题和装箱问题，无缝钢管坯料设计的求解更为复杂． 本文给出了无缝钢管 坯料设计问题的一般性描述，并建立了混合整数规划模型． 针对库存中只有单一尺寸圆坯的情况，简化了问题模型并且求得 了问题的下界． 结合问题特点，提出了基于贪婪策略的两阶段启发式算法，并用实际生产数据和仿真数据验证了算法求解此 类问题具有很好的有效性和稳定性． 关键词 坯料设计; 无缝钢管; 贪婪策略; 启发式算法 分类号 O221. 4; TG335. 7 Model and algorithm of the billet design problem in the production of seamless steel tubes with a single billet size LI Tie-ke，LIU Yu-zhuo ，WANG Bai-lin，LUAN Zhi-wei Donlinks School of Economics and Management，University of Science and Technology Beijing，Beijing 100083，China Corresponding author，E-mail: sunrise8818@ hotmail． com ABSTＲACT The billet design problem ( BDP) in seamless steel tube production is to assign order tubes to billets under process constraints． Because of the batch rule in practical production，each order has a minimum weight of tubes assigned to any billet． Mean￾while，as the number of tubes assigned to a billet must be an integer，the weight of tubes assigned to any billet is not continuous in its domain． Thus，the BDP discussed herein is more difficult to solve than the slab design and bin packing problems． In this study，a multi-objective mix-integer programming model was built based on a generalized description of the BDP，which is proved to be non-de￾terministic polynomial ( NP) hard． For the case with single billet size wherein two objectives in the model are equivalent，a simplified model was set up and the lower bound of the objective could be found． Further，a two-stage heuristic algorithm based on greedy strate￾gy was proposed to solve the problem． Finally，using computational results，it was proved that the algorithm is effective and efficient in solving the BDP． KEY WOＲDS billet design; seamless steel tube; greedy strategy; heuristic algorithm 收稿日期: 2016--07--20 基金项目: 中央高校基本科研业务费资助项目( FＲF--BD--16--006A) ; 国家自然科学基金资助项目( 71231001) ; 北京市自然科学基金资助项 目( 9174038) 无缝钢管生产计划中的坯料设计环节( 以下简称 坯料设计) 是将客户订单和生产原料联系起来的纽 带． 在坯料设计过程中，主要考虑的客户订单参数包 括订单钢管的外径、壁厚、长度、钢种以及订单重量; 生 产原料是来自炼钢连铸车间的圆坯，其主要参数包括 外径、钢种以及质量，通常情况下为尺寸确定的定尺 坯． 坯料设计的任务就是将订单钢管参数转化为圆坯 参数，在满足工艺要求的前提下，将订单钢管合理分配 到圆坯中，建立订单钢管和圆坯的匹配关系． 坯料设 计问题是无缝钢管生产计划中必须解决的问题，它对

李铁克等：单一尺寸圆坯的无缝钢管坯料设计模型与算法 ·635 生产原料的利用率以及生产过程的效率都会产生重要 是不确定性多项式(non-deterministic polynomial,NP) 影响. 难题，故本文问题也是NP难问题.求解一维装箱问题 在实际生产中，为了满足大规模生产的要求，每个 的算法主要分为近似求解算法和精确算法两大类.近 生产单元有最小生产重量的要求，在无缝钢管生产中 似求解算法包括：经典算法，如降序最佳适应(best fit 指的就是同一订单分配在一支圆坯的钢管有最小重量 decreasing,BFD)算法；人工智能算法，如遗传算法a 要求.由于无缝钢管产品的特殊性，在建立订单和圆 模拟退火算法m等；启发式算法，如Crainic等☒在降 坯匹配关系时，订单在圆坯中实际分配的是钢管支数， 序最佳适应算法基础上，提出了基于上界和下界技术 而非钢管重量.因此，生产单元的最小生产重量要求 的ABFD、LB-BFD和TER-BFD三种近似求解算法， 实际上是订单钢管的最小分配支数要求 并且还系统分析了箱子成本与容积的关系：以及结合 尽管坯料设计在无缝钢管生产计划中起着重要作 了多种算法的混合算法，如Hemmelmayr等围提出的 用，但是，目前尚未有直接对此问题公开发表的文献. 基于下界技术、动态规划和变邻域搜索的混合算法，并 在现有文献中，与无缝钢管坯料设计问题密切相关的 且通过大量的实验测试发现，算法在大规模算例中性 是热轧板材的板坯设计问题.与无缝钢管坯料设计相 能优越，在200组测试数据中找到了其中86组的最优 似，板坯设计是热轧板材生产组织过程的先行环节. 解.除了上述近似求解算法，分支定界法、列生成 Frisch等0最早对该问题进行了整理，对问题的研究 方法等精确算法也被用于求解装箱问题 背景、特点和约束进行了分析，提出了多个问题模型， 尽管已经提出了许多启发式算法求解装箱问题， 并最终将问题归结为变尺寸装箱问题.随后，Hnich 但是，由于在实际生产中每个订单有最小生产批量的 等四提出了整数规划模型、约束满足模型和结合了两 限制，使得坯料设计问题实际上为带有装箱下限的装 种模型的混合模型.针对板坯重量被事先确定的情 箱问题.这就导致现有的求解装箱问题的方法无法满 况，席阳和李铁克四提出了一种两阶段的板坯设计最 足订单最小生产批量的要求，故不能直接用于求解本 优算法，并且给出了最优性质的理论证明.针对订单 文问题 重量和板坯重量为区间值的情况，Dawande等考虑 综上所述，无缝钢管坯料设计问题是既区别于热 了生产单元重量限制，提出了一种混合整数规划模型： 轧板材的板坯设计问题，又与经典装箱问题不尽相同 Gargani和Refalo、Hentenryck和Michel和张文学 的新工业工程问题，鉴于其对生产计划的重要作用，对 和李铁克切则使用了约束满足模型对问题进行求解. 该问题的研究十分必要和重要 Gargani设计的邻域搜索技术第一次得到了问题的最 1问题描述和数学模型 优解：张文学使用了约束满足技术在较短时间内获得 了问题的满意解.近年来，针对板坯重分配问题，吕亚 1.1问题描述 娜等陶建立了动态环境下以最小化加权总费用为目标 在一个计划期内，所有订单钢管的外径、壁厚、长 的板坯分配问题数学模型，并且设计了基于多邻域的 度、钢种和订单重量，以及原料库中圆坯的外径、钢种 分散搜索算法对问题近似求解，算法可以在较短时间 和重量均已知，在订单有最小分配支数的要求下，如何 内获得问题的近优解，而且在求解重量和效率方面远 确定每个订单在每支圆坯上的分配支数，使得生产全 远优于传统方法.另外，对于板坯生产中有可能发生 部订单所需的圆坯数量最小以及总剩余重量最小.为 的板坯重分配问题，Tamg等网还建立了混合整数规划 建立数学模型，对问题做进一步限定及说明 模型，并设计了基于禁忌搜索和多邻域搜索的启发式 (1)订单钢管的外径、壁厚、长度、钢种及订单重 算法. 量的要求均为确定值，即不考虑钢管属性为区间值的 虽然两个问题无论在问题背景还是在生产中的作 情况，不考虑不同钢种间的替代可能性 用方面都极为相似，但是，由于无缝钢管的产品特殊 (2)由于订单钢管的外径、壁厚和长度均为确定 性，因此，在将订单进行拆分并放入圆坯的过程中，本 值，可以求得订单钢管的理论重量。因此，在建立订单 文问题要求拆分后的订单在满足批量原则的同时必须 与圆坯匹配关系时可以使用钢管支数代替钢管重量进 包含整数支钢管，而在板坯设计时则只需满足重量要 行求解 求，拆分后的订单重量是连续取值的，这使得本文问题 (3)原料库中只存在一种尺寸的圆坯，即坯料设 在求解时难度更大 计中的所有圆坯均相同. 若将订单分成满足最小分配支数要求的子订单， (4)所有订单钢管和圆坯的钢种相同.如果存在 把子订单看作物品，圆坯看作箱子，无缝钢管坯料设计 多个钢种，可以按钢种划分为多个相互独立的子问题 问题可被看作是典型的一维装箱问题.因此，一维装 (5)每个订单只包含一种钢管产品，即同一订单 箱问题是坯料设计问题的子问题.由于一维装箱问题 的钢管的外径、壁厚、长度和钢种均相同.如果订单包

李铁克等: 单一尺寸圆坯的无缝钢管坯料设计模型与算法 生产原料的利用率以及生产过程的效率都会产生重要 影响． 在实际生产中，为了满足大规模生产的要求，每个 生产单元有最小生产重量的要求，在无缝钢管生产中 指的就是同一订单分配在一支圆坯的钢管有最小重量 要求． 由于无缝钢管产品的特殊性，在建立订单和圆 坯匹配关系时，订单在圆坯中实际分配的是钢管支数， 而非钢管重量． 因此，生产单元的最小生产重量要求 实际上是订单钢管的最小分配支数要求． 尽管坯料设计在无缝钢管生产计划中起着重要作 用，但是，目前尚未有直接对此问题公开发表的文献． 在现有文献中，与无缝钢管坯料设计问题密切相关的 是热轧板材的板坯设计问题． 与无缝钢管坯料设计相 似，板坯设计是热轧板材生产组织过程的先行环节． Frisch 等［1］最早对该问题进行了整理，对问题的研究 背景、特点和约束进行了分析，提出了多个问题模型， 并最终将问题归结为变尺寸装箱问题． 随后，Hnich 等［2］提出了整数规划模型、约束满足模型和结合了两 种模型的混合模型． 针对板坯重量被事先确定的情 况，席阳和李铁克［3］提出了一种两阶段的板坯设计最 优算法，并且给出了最优性质的理论证明． 针对订单 重量和板坯重量为区间值的情况，Dawande 等［4］考虑 了生产单元重量限制，提出了一种混合整数规划模型; Gargani 和 Ｒefalo［5］、Hentenryck 和 Michel［6］ 和张 文 学 和李铁克［7］则使用了约束满足模型对问题进行求解． Gargani 设计的邻域搜索技术第一次得到了问题的最 优解; 张文学使用了约束满足技术在较短时间内获得 了问题的满意解． 近年来，针对板坯重分配问题，吕亚 娜等［8］建立了动态环境下以最小化加权总费用为目标 的板坯分配问题数学模型，并且设计了基于多邻域的 分散搜索算法对问题近似求解，算法可以在较短时间 内获得问题的近优解，而且在求解重量和效率方面远 远优于传统方法． 另外，对于板坯生产中有可能发生 的板坯重分配问题，Tang 等［9］还建立了混合整数规划 模型，并设计了基于禁忌搜索和多邻域搜索的启发式 算法． 虽然两个问题无论在问题背景还是在生产中的作 用方面都极为相似，但是，由于无缝钢管的产品特殊 性，因此，在将订单进行拆分并放入圆坯的过程中，本 文问题要求拆分后的订单在满足批量原则的同时必须 包含整数支钢管，而在板坯设计时则只需满足重量要 求，拆分后的订单重量是连续取值的，这使得本文问题 在求解时难度更大． 若将订单分成满足最小分配支数要求的子订单， 把子订单看作物品，圆坯看作箱子，无缝钢管坯料设计 问题可被看作是典型的一维装箱问题． 因此，一维装 箱问题是坯料设计问题的子问题． 由于一维装箱问题 是不确定性多项式( non-deterministic polynomial，NP) 难题，故本文问题也是 NP 难问题． 求解一维装箱问题 的算法主要分为近似求解算法和精确算法两大类． 近 似求解算法包括: 经典算法，如降序最佳适应( best fit decreasing，BFD) 算法; 人工智能算法，如遗传算法［10］、 模拟退火算法［11］等; 启发式算法，如 Crainic 等［12］在降 序最佳适应算法基础上，提出了基于上界和下界技术 的 A--BFD、LB--BFD 和 ITEＲ--BFD 三种近似求解算法， 并且还系统分析了箱子成本与容积的关系; 以及结合 了多种算法的混合算法，如 Hemmelmayr 等［13］提出的 基于下界技术、动态规划和变邻域搜索的混合算法，并 且通过大量的实验测试发现，算法在大规模算例中性 能优越，在 200 组测试数据中找到了其中 86 组的最优 解． 除了上述近似求解算法，分支定界法［14］、列生成 方法［15］等精确算法也被用于求解装箱问题． 尽管已经提出了许多启发式算法求解装箱问题， 但是，由于在实际生产中每个订单有最小生产批量的 限制，使得坯料设计问题实际上为带有装箱下限的装 箱问题． 这就导致现有的求解装箱问题的方法无法满 足订单最小生产批量的要求，故不能直接用于求解本 文问题． 综上所述，无缝钢管坯料设计问题是既区别于热 轧板材的板坯设计问题，又与经典装箱问题不尽相同 的新工业工程问题，鉴于其对生产计划的重要作用，对 该问题的研究十分必要和重要． 1 问题描述和数学模型 1. 1 问题描述 在一个计划期内，所有订单钢管的外径、壁厚、长 度、钢种和订单重量，以及原料库中圆坯的外径、钢种 和重量均已知，在订单有最小分配支数的要求下，如何 确定每个订单在每支圆坯上的分配支数，使得生产全 部订单所需的圆坯数量最小以及总剩余重量最小． 为 建立数学模型，对问题做进一步限定及说明． ( 1) 订单钢管的外径、壁厚、长度、钢种及订单重 量的要求均为确定值，即不考虑钢管属性为区间值的 情况，不考虑不同钢种间的替代可能性． ( 2) 由于订单钢管的外径、壁厚和长度均为确定 值，可以求得订单钢管的理论重量． 因此，在建立订单 与圆坯匹配关系时可以使用钢管支数代替钢管重量进 行求解． ( 3) 原料库中只存在一种尺寸的圆坯，即坯料设 计中的所有圆坯均相同． ( 4) 所有订单钢管和圆坯的钢种相同． 如果存在 多个钢种，可以按钢种划分为多个相互独立的子问题． ( 5) 每个订单只包含一种钢管产品，即同一订单 的钢管的外径、壁厚、长度和钢种均相同． 如果订单包 · 536 ·

·636· 工程科学学报，第39卷，第4期 含多种钢管产品，可将其拆分为多个同产品的子订单. 当圆坯包含订单时，订单分配在该圆坯的钢管支数必 (6)订单和圆坯之间是多对多关系.一个圆坯可 须不小于订单的最小分配支数，否则，订单在该圆坯的 以包含多个订单，一个订单也可以分配给多个圆坯 分配支数必须为0：约束(7)为决策变量的取值范围 图1给出了单一尺寸圆坯坯料设计问题的一个实 目标函数(1)可做如下变形： 例，假设订单钢管的重量均为1，订单1~4的订单钢 三(c- 管支数分别为9、10、11和9：最小分配重量为3，即订 会)=c-)=mc- 单的最小分配支数为3：圆坯的重量为14.图1给出了 一种订单钢管与圆坯的匹配方案，在该方案中，圆坯的 (心，三w小将约束条件(3)代入上式可知，目标函 使用数量为3，剩余重量为3. 数(1)可以化简为Minimize mC-∑(o,C.).由于 坏 9 三(m,C)和C均为固定值，故目标函数(1)等价 Minimize m,与目标函数(2)相同.因此，当原料库中只 9 有一种尺寸圆坯时，目标函数(1)和(2)具有一致性， 可以用目标(2)代替(1).此时模型可以简化为单目 图1订单圆坯匹配关系 标模型P2]如下： Fig.I Matching relation between orders and billets Minimize m, s.t.(3)~(7) 1.2符号定义 1.4问题下界 为描述无缝钢管坯料设计问题数学模型，对模型 在模型P2]中，将约束条件(4)作如下变形： 中用到的数学符号做如下定义：o为订单序号；n为订 单数量：0为订单序号集合0={1,2，…，n}:b为圆坯 名C, 序号；m为圆坯使用数量；B为已使用圆坯序号集合 Vb∈B曰 B={1,2,,m}:W。为第b支圆坯的重量，由于圆坯 为单一尺寸，假设重量为C,则W。=C,Hb∈B:C。为 三（后≤mc=豆m,c)≤ 订单o的钢管总支数；w。为订单o的钢管的理论重量； 1 C为订单o的钢管最小分配支数：x为订单o分配 mG→m≥乙￡ (o.C). 到圆坯b中的钢管支数，则x的取值范围是整数集合 已知m∈Z,所以，圆坯数量下界为m"= Z:y为0一变量，1表示订单o分配钢管到圆坯b,否 则为0. [亡云.)[o1表示不小于a的最小整数基 1.3数学模型 于此【定理1】给出了圆坯数量m达到下界的条件. 根据上述定义的数学符号，建立混合整数线性规 划模型PI]如下所示： 定理当满是条件宫(C-宫】<c 时，圆坯数量m达到下界 (x） (1) 证明：由以上结论可知，如果 Minimize m. (2) (c- s.t. 三(（)）<C那么，不等式可以简化为： xw=C。,Hoe0: (3) mC- (e.c)c(m-c< (w.C）. A≤C.VbcB:- (4) 由此可以看出，m-1支圆坯无法容纳全部订单. 定理得证 Cya-xb≤C。-C,Ho∈O,b∈B; (5) Cyu-xa≥0，Ho∈0，b∈B; (6) 在【定理1】中， 月(c-()）表示圆坯 x∈Z,y={0,1},Ho∈0，b∈B. (7) 的总剩余量.因此，根据【定理1】可知：当圆坯总剩余 目标函数(1)表示最小化圆坯总剩余量；式(2)表 量小于圆坯重量时，圆坯数量m达到下界 示最小化使用圆坯数量：约束(3)表示订单钢管必须 全部分配到圆坯中：约束(4)表示每支圆坯分配的订 2求解算法 单钢管总重量不能超过圆坯重量：约束(5)和(6)表示 由于问题为NP难题，很难在短时间内求得问题

工程科学学报，第 39 卷，第 4 期 含多种钢管产品，可将其拆分为多个同产品的子订单． ( 6) 订单和圆坯之间是多对多关系． 一个圆坯可 以包含多个订单，一个订单也可以分配给多个圆坯． 图 1 给出了单一尺寸圆坯坯料设计问题的一个实 例，假设订单钢管的重量均为 1，订单 1 ～ 4 的订单钢 管支数分别为 9、10、11 和 9; 最小分配重量为 3，即订 单的最小分配支数为3; 圆坯的重量为14． 图1 给出了 一种订单钢管与圆坯的匹配方案，在该方案中，圆坯的 使用数量为 3，剩余重量为 3． 图 1 订单圆坯匹配关系 Fig． 1 Matching relation between orders and billets 1. 2 符号定义 为描述无缝钢管坯料设计问题数学模型，对模型 中用到的数学符号做如下定义: o 为订单序号; n 为订 单数量; O 为订单序号集合 O = { 1，2，…，n} ; b 为圆坯 序号; m 为圆坯使用数量; B 为已使用圆坯序号集合 B = { 1，2，…，m} ; Wb 为第 b 支圆坯的重量，由于圆坯 为单一尺寸，假设重量为 C，则 Wb = C，b∈B; Co 为 订单 o 的钢管总支数; wo 为订单 o 的钢管的理论重量; Cmin o 为订单 o 的钢管最小分配支数; xob为订单 o 分配 到圆坯 b 中的钢管支数，则 xob的取值范围是整数集合 Z; yob为 0--1 变量，1 表示订单 o 分配钢管到圆坯 b，否 则为 0． 1. 3 数学模型 根据上述定义的数学符号，建立混合整数线性规 划模型［P1］如下所示: Minimize ∑ m b = ( 1 C － ∑ n o = 1 ( wo xob ) ) ， ( 1) Minimize m． ( 2) s． t． ∑ m b = 1 xob = Co，o∈O; ( 3) ∑ n o = 1 wo xob≤C，b∈B; ( 4) Co yob － xob≤Co － Cmin o ，o∈O，b∈B; ( 5) Co yob － xob≥0，o∈O，b∈B; ( 6) xob∈Z，yob = { 0，1} ，o∈O，b∈B． ( 7) 目标函数( 1) 表示最小化圆坯总剩余量; 式( 2) 表 示最小化使用圆坯数量; 约束( 3) 表示订单钢管必须 全部分配到圆坯中; 约束( 4) 表示每支圆坯分配的订 单钢管总重量不能超过圆坯重量; 约束( 5) 和( 6) 表示 当圆坯包含订单时，订单分配在该圆坯的钢管支数必 须不小于订单的最小分配支数，否则，订单在该圆坯的 分配支数必须为 0; 约束( 7) 为决策变量的取值范围． 目 标 函 数 ( 1 ) 可 做 如 下 变 形: ∑ m b = ( 1 C － ∑ n o = 1 ( wo xob ) ) = ∑ m b = 1 C － ∑ m b = 1 ∑ n o = 1 ( wo xob ) = mC － ∑ n o = ( 1 wo ∑ m b = 1 xob ) ． 将约束条件( 3) 代入上式可知，目标函 数( 1) 可以化简为 Minimize mC － ∑ n o = 1 ( woCo ) ． 由于 ∑ n o = 1 ( woCo ) 和 C 均为固定值，故目标函数( 1) 等价于 Minimize m，与目标函数( 2) 相同． 因此，当原料库中只 有一种尺寸圆坯时，目标函数( 1) 和( 2) 具有一致性， 可以用目标( 2) 代替( 1) ． 此时模型可以简化为单目 标模型［P2］如下: Minimize m， s． t． ( 3) ～ ( 7) ． 1. 4 问题下界 在模型［P2］中，将约束条件( 4) 作如下变形: ∑ n o = 1 wo xob≤C， b∈B ∑ m b = 1 ∑ n o = 1 wo xob≤ ∑ m b = 1 C ∑ n o = ( 1 wo ∑ m b = 1 xob ) ≤mC ∑ n o = 1 ( woCo ) ≤ mCm≥ 1 C ∑ n o = 1 ( woCo ) ． 已知 m ∈ Z + ，所 以，圆坯数量下界为 mLB = 1 C ∑ n o = 1 ( woCo ) ，「a?表示不小于 a 的最小整数． 基 于此，【定理 1】给出了圆坯数量 m 达到下界的条件． 【定理1】当 m 满足条件 ∑ m b = ( 1 C － ∑ n o =1 ( wo xob ) ) ＜ C 时，圆坯数量 m 达到下界． 证 明: 由 以 上 结 论 可 知，如 果 ∑ m b = ( 1 C － ∑ n o = 1 ( wo xob ) ) ＜ C，那么，不等式可以简化为: mC － ∑ n o = 1 ( woCo ) ＜ C( m － 1) C ＜ ∑ n o = 1 ( woCo ) ． 由此可以看出，m － 1 支圆坯无法容纳全部订单． 定理得证． 在【定理 1】中，∑ m b = ( 1 C － ∑ n o = 1 ( wo xob ) ) 表示圆坯 的总剩余量． 因此，根据【定理 1】可知: 当圆坯总剩余 量小于圆坯重量时，圆坯数量 m 达到下界． 2 求解算法 由于问题为 NP 难题，很难在短时间内求得问题 · 636 ·

李铁克等：单一尺寸圆坯的无缝钢管坯料设计模型与算法 ·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 ·

·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 ·