工程科学学报，第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． Meanwhile，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-deterministic 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 strategy 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 ) ≤ mCm≥ 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≤品」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 ·
李铁克等：单一尺寸圆坯的无缝钢管坯料设计模型与算法 639· 按照现实生产中最常用的圆坯重量为9的情况， 可以看出，算法第一阶段结果的圆坯使用数量为14， 经贪婪策略的启发式算法计算得到结果如表3所示. 在第二阶段圆坯使用数量降到3，达到圆坯数量 在列【订单分配】中，括号外数字表示订单编号，括号 下界. 内数字表示该订单分配在圆坯中的钢管支数.从表3 表3圆坯重量为9：时订单分配结果 Table 3 Assignment results when the billet weight is 9 tons 第一阶段结果 第二阶段结果 编号 订单分配 使用重量t 订单分配 使用重量1 01 7(11),12(16) 9.000 7(11),12(16) 9.000 02 6(21),9(5),19(4) 8.924 6(13),9(5),11(6),19(4) 8.994 03 8(5),11(21) 8.923 4(6),8(5),11(17) 8.981 义 2(11),3(27) 8.840 4(6),5(7),10(4),15(5),16(5) 8.979 05 16(3),18(7),20(8) 8.783 2(11),3(19),6(8) 8.976 06 5(24),7(9) 8.688 9(9),10(5),15(4),16(3),18(3) 8.963 07 4(12),9(14),10(4) 8.644 1(8),3(8),17(3),20(8) 8.921 08 8(23),13(4) 8.406 5(17),7(9),18(4) 8.823 多 17(9),19(8) 8.219 8(23),9(5) 8.486 10 1(24),2(17) 8.201 11(4),17(6),19(8) 8.230 11 14(16),17(3) 7.961 1(24),2(17) 8.201 12 10(5),15(9),16(5) 7.764 14(16),17(3) 7.961 13 1(8),13(17) 7.709 13(21) 7.665 14 11(6) 2.118 总和 112.180 112.180 为检验对于任意尺寸的圆坯贪婪策略的启发式算 3.2随机数据仿真实验 法是否均有效，图3给出了圆坯为其他尺寸时算法运 为进一步验证贪婪策略的启发式算法的有效性， 行结果.可以看出，在圆坯使用数量方面，对于任意尺 本文采用仿真数据实验对贪婪策略的启发式算法进行 寸的圆坯，算法结果均达到了圆坯数量下界，表明算法 测试，并与装箱问题的经典降序最佳适应算法进行比 对于求解此类问题是有效的.在运行时间方面，随着 较.降序最佳适应算法先对物品按重量降序排序，再 圆坯重量增加，算法的运行时间在减小，这意味着算法 按照最佳适应算法进行装箱.然而，由于订单有最小 更适合求解圆坯数量较少的情况.另外，算法整体运 分配支数限制，降序最佳适应算法无法直接用于求解 行时间均不超过2$，表明了算法具有很高的运算 本文问题.因此，先将订单根据最小分配支数分成 效率. 15 L各]个子订单，每个订单包含的钢管支数为C一：然 第一阶段结果 第二阶段结果 20 一圆坯数量下界 后将剩余解管依次分配到合]个子订单中，使得所 要 一运动时间/s 有子订单包含的钢管支数相差不超过1：最后再用降 15 序最佳适应算法进行装箱，此时得到的解便为问题可 圆坯重量M 10 0 行解 6 7 910 第一阶段结果 20 18 15 13 13 随机数据规则设定如下：订单钢管重量在.00， 第二阶段结果 19 17 1513 12 10.00]随机取值，订单支数在20,100]随机取整，生 圆坯致量下界 19 17 151312 运动时间/s13280.6220.310.2470.134 产单元最小生产重量为2t.随着订单数量的增加，各 随机生成100组数据进行测试，汇总平均结果如表4 图3圆坯重量变化时运行结果对比图 Fig.3 Assignment results when the weight of the billet changes 所示
李铁克等: 单一尺寸圆坯的无缝钢管坯料设计模型与算法 按照现实生产中最常用的圆坯重量为 9 t 的情况， 经贪婪策略的启发式算法计算得到结果如表 3 所示． 在列【订单分配】中，括号外数字表示订单编号，括号 内数字表示该订单分配在圆坯中的钢管支数． 从表 3 可以看出，算法第一阶段结果的圆坯使用数量为 14， 在第二 阶 段 圆 坯 使 用 数 量 降 到 13，达 到 圆 坯 数 量 下界． 表 3 圆坯重量为 9 t 时订单分配结果 Table 3 Assignment results when the billet weight is 9 tons 编号 第一阶段结果 第二阶段结果 订单分配 使用重量/t 订单分配 使用重量/t 01 7( 11) ，12( 16) 9. 000 7( 11) ，12( 16) 9. 000 02 6( 21) ，9( 5) ，19( 4) 8. 924 6( 13) ，9( 5) ，11( 6) ，19( 4) 8. 994 03 8( 5) ，11( 21) 8. 923 4( 6) ，8( 5) ，11( 17) 8. 981 04 2( 11) ，3( 27) 8. 840 4( 6) ，5( 7) ，10( 4) ，15( 5) ，16( 5) 8. 979 05 16( 3) ，18( 7) ，20( 8) 8. 783 2( 11) ，3( 19) ，6( 8) 8. 976 06 5( 24) ，7( 9) 8. 688 9( 9) ，10( 5) ，15( 4) ，16( 3) ，18( 3) 8. 963 07 4( 12) ，9( 14) ，10( 4) 8. 644 1( 8) ，3( 8) ，17( 3) ，20( 8) 8. 921 08 8( 23) ，13( 4) 8. 406 5( 17) ，7( 9) ，18( 4) 8. 823 09 17( 9) ，19( 8) 8. 219 8( 23) ，9( 5) 8. 486 10 1( 24) ，2( 17) 8. 201 11( 4) ，17( 6) ，19( 8) 8. 230 11 14( 16) ，17( 3) 7. 961 1( 24) ，2( 17) 8. 201 12 10( 5) ，15( 9) ，16( 5) 7. 764 14( 16) ，17( 3) 7. 961 13 1( 8) ，13( 17) 7. 709 13( 21) 7. 665 14 11( 6) 2. 118 总和 112. 180 112. 180 为检验对于任意尺寸的圆坯贪婪策略的启发式算 法是否均有效，图 3 给出了圆坯为其他尺寸时算法运 行结果． 可以看出，在圆坯使用数量方面，对于任意尺 寸的圆坯，算法结果均达到了圆坯数量下界，表明算法 对于求解此类问题是有效的． 在运行时间方面，随着 圆坯重量增加，算法的运行时间在减小，这意味着算法 更适合求解圆坯数量较少的情况． 另外，算法整体运 行时间 均 不 超 过 2 s，表明了算法具有很高的运算 效率． 图 3 圆坯重量变化时运行结果对比图 Fig． 3 Assignment results when the weight of the billet changes 3. 2 随机数据仿真实验 为进一步验证贪婪策略的启发式算法的有效性， 本文采用仿真数据实验对贪婪策略的启发式算法进行 测试，并与装箱问题的经典降序最佳适应算法进行比 较． 降序最佳适应算法先对物品按重量降序排序，再 按照最佳适应算法进行装箱． 然而，由于订单有最小 分配支数限制，降序最佳适应算法无法直接用于求解 本文问题． 因此，先将订单根据最小分配支数 分 成 Co Cmin o 个子订单，每个订单包含的钢管支数为 Cmin o ; 然 后将剩余钢管依次分配到 Co Cmin o 个子订单中，使得所 有子订单包含的钢管支数相差不超过 1; 最后再用降 序最佳适应算法进行装箱，此时得到的解便为问题可 行解． 随机数据规则设定如下: 订单钢管重量在［1. 00， 10. 00］随机取值，订单支数在［20，100］随机取整，生 产单元最小生产重量为 2 t． 随着订单数量的增加，各 随机生成 100 组数据进行测试，汇总平均结果如表 4 所示． · 936 ·
·640 工程科学学报，第39卷，第4期 表4随机数据仿真实验测试结果 Table 4 Simulation test results in random data 下界 HAGS算法 BFD算法 订单数量 圆坯重量： 圆坯使用数量 圆坯使用数量 偏离率/% 圆坯使用数量 偏离率/% > 9.55 9.75 2.09 10.3 7.85 乎 8.45 8.65 2.37 8.65 2.37 10 9 7.65 7.75 1.31 7.9 3.27 10 6.95 7 0.72 7.1 2.16 1 19.5 19.85 1.79 20.3 4.1 20 乐 17 17.2 1.18 17.5 2.94 9 15.15 15.3 0.99 15.8 4.29 10 13.8 13.9 0.72 14 1.45 44.8 45.8 2.23 45.9 2.46 50 39.4 39.55 0.38 40.05 1.65 9 35.15 35.55 1.14 35.6 1.28 10 31.65 32 1.11 32.3 2.05 > 84.8 87.33 2.98 93.62 10.4 100 8 74.2 75.5 1.75 80.15 8.02 9 65.95 66.83 1.33 71.29 8.1 10 59.36 61 2.76 65.87 10.97 > 168.9 172.76 2.29 181.2 7.28 200 乎 147.8 149.77 1.34 157.23 6.39 9 131.37 134.6 2.46 140.98 7.32 10 118.23 121.3 2.6 127.1 7.5 > 423.9 435.31 2.69 448.65 5.84 500 370.9 377.32 1.73 387.98 4.6 9 329.71 333.18 1.05 343.72 4.25 10 296.74 301.5 1.6 308.63 4.01 注：HAGS偏离率(%)=(HAGS算法圆坯使用数量-下界圆坯使用数量)/下界圆坯使用数量×10O%:BFD偏离率(%)=(BFD算法圆 坯使用数量-下界圆坯使用数量)/下界圆坯使用数量×100% 从表4可以得到以下结论. 120 (1)总的来看，贪婪策略的启发式算法求得的圆 100 一HAGS算法 坯数量均低于降序最佳适应算法，说明贪婪策略的启 -·BFD算法 80 发式算法明显优于降序最佳适应算法，且随着问题规 模的增大，其优势更加明显. 60 (2)尽管当问题规模增大时，贪婪策略的启发式 算法结果与问题下界差值增大，但是其偏离下界的百 20 分比却维持在较低水平（低于3%），说明贪婪策略的 启发式算法一直保持较好的求解效果，且在圆坯数量 0050100i150200250300350400450500 订单数量 较少时效果更好 在算法运行时间方面，由于贪婪策略的启发式算 图4贪婪策略的启发式算法与降序最佳适应算法运行时间对 比图 法的复杂度要明显高于降序最佳适应算法.随着订单 Fig.4 Comparison between HAGS and BFD in operating time 数量的增加，贪婪策略的启发式算法的运行时间明显 增加，而降序最佳适应算法的运行时间保持稳定，算法 4 结论 运行时间对比结果如图4所示：随着订单数量的增加， 贪婪策略的启发式算法的运行时间大致呈线性递增， 无缝钢管坯料设计问题是从无缝钢管生产过程中 而降序最佳适应算法的运行时间维持在10s以下.虽 提取的实际问题，与热轧板材的板坯设计和一维装箱 然在算法运行效率方面较降序最佳适应算法略差，但 问题均有相似性.但是，由于订单在圆坯中有最小分 是，作为离线求解算法，贪婪策略的启发式算法可以满 配支数的限制，坯料设计成为与上述问题存在本质区 足实际生产需求 别的新工业工程问题.本文给出了无缝钢管坯料设计
工程科学学报，第 39 卷，第 4 期 表 4 随机数据仿真实验测试结果 Table 4 Simulation test results in random data 订单数量 圆坯重量/t 下界 HAGS 算法 BFD 算法 圆坯使用数量 圆坯使用数量 偏离率/% 圆坯使用数量 偏离率/% 7 9. 55 9. 75 2. 09 10. 3 7. 85 10 8 8. 45 8. 65 2. 37 8. 65 2. 37 9 7. 65 7. 75 1. 31 7. 9 3. 27 10 6. 95 7 0. 72 7. 1 2. 16 20 7 19. 5 19. 85 1. 79 20. 3 4. 1 8 17 17. 2 1. 18 17. 5 2. 94 9 15. 15 15. 3 0. 99 15. 8 4. 29 10 13. 8 13. 9 0. 72 14 1. 45 50 7 44. 8 45. 8 2. 23 45. 9 2. 46 8 39. 4 39. 55 0. 38 40. 05 1. 65 9 35. 15 35. 55 1. 14 35. 6 1. 28 10 31. 65 32 1. 11 32. 3 2. 05 100 7 84. 8 87. 33 2. 98 93. 62 10. 4 8 74. 2 75. 5 1. 75 80. 15 8. 02 9 65. 95 66. 83 1. 33 71. 29 8. 1 10 59. 36 61 2. 76 65. 87 10. 97 200 7 168. 9 172. 76 2. 29 181. 2 7. 28 8 147. 8 149. 77 1. 34 157. 23 6. 39 9 131. 37 134. 6 2. 46 140. 98 7. 32 10 118. 23 121. 3 2. 6 127. 1 7. 5 500 7 423. 9 435. 31 2. 69 448. 65 5. 84 8 370. 9 377. 32 1. 73 387. 98 4. 6 9 329. 71 333. 18 1. 05 343. 72 4. 25 10 296. 74 301. 5 1. 6 308. 63 4. 01 注: HAGS 偏离率( % ) = ( HAGS 算法圆坯使用数量 － 下界圆坯使用数量) /下界圆坯使用数量 × 100% ; BFD 偏离率( % ) = ( BFD 算法圆 坯使用数量 － 下界圆坯使用数量) /下界圆坯使用数量 × 100% ． 从表 4 可以得到以下结论． ( 1) 总的来看，贪婪策略的启发式算法求得的圆 坯数量均低于降序最佳适应算法，说明贪婪策略的启 发式算法明显优于降序最佳适应算法，且随着问题规 模的增大，其优势更加明显． ( 2) 尽管当问题规模增大时，贪婪策略的启发式 算法结果与问题下界差值增大，但是其偏离下界的百 分比却维持在较低水平( 低于 3% ) ，说明贪婪策略的 启发式算法一直保持较好的求解效果，且在圆坯数量 较少时效果更好． 在算法运行时间方面，由于贪婪策略的启发式算 法的复杂度要明显高于降序最佳适应算法． 随着订单 数量的增加，贪婪策略的启发式算法的运行时间明显 增加，而降序最佳适应算法的运行时间保持稳定，算法 运行时间对比结果如图 4 所示: 随着订单数量的增加， 贪婪策略的启发式算法的运行时间大致呈线性递增， 而降序最佳适应算法的运行时间维持在 10 s 以下． 虽 然在算法运行效率方面较降序最佳适应算法略差，但 是，作为离线求解算法，贪婪策略的启发式算法可以满 足实际生产需求． 图 4 贪婪策略的启发式算法与降序最佳适应算法运行时间对 比图 Fig． 4 Comparison between HAGS and BFD in operating time 4 结论 无缝钢管坯料设计问题是从无缝钢管生产过程中 提取的实际问题，与热轧板材的板坯设计和一维装箱 问题均有相似性． 但是，由于订单在圆坯中有最小分 配支数的限制，坯料设计成为与上述问题存在本质区 别的新工业工程问题． 本文给出了无缝钢管坯料设计 · 046 ·
李铁克等：单一尺寸圆坯的无缝钢管坯料设计模型与算法 ·641· 问题的一般性描述并且建立了混合整数规划模型.针 6]Hentenryek P V,Michel L.The steel mill slab design problem re- 对原料库中只存在一种尺寸圆坯的常见情况，证明了 visited Integration of Al and OR Techniques in Constraint Pro- 此时最小化圆坯数量和最小化圆坯总剩余量具有一致 gramming for Combinatorial Optimization Problems.Berlin,2008: 377 性，从而简化了问题模型.结合问题特点，本文提出了 Zhang W X,Li T K.Modelling and algorithm for the slab desig- 基于贪婪策略的两阶段启发式贪婪策略的启发式算 ning problem based on constraint satisfaction.Unin Sci Technol 法，并且证明算法是收敛的.与传统贪婪策略单一目 Beijing,2011,33(5):641 标不同，贪婪策略的启发式算法在两阶段选取了不同 (张文学，李铁克.基于约束满足的板坯设计模型与求解方 的贪婪目标，并以较低的计算复杂度设置了寻优路径. 法.北京科技大学学报，2011,33(5)：641) 最后，通过实际生产数据和大量仿真数据的验证，贪婪 [8]Li Y N,Tang L X,Meng Y,et al.Modeling and scatter search algorithm for dynamic slab allocation problem in iron and steel en- 策略的启发式算法明显优于传统降序最佳适应算法. terprises.Control Decis,2015,30(1):17 本文研究成果不仅为无缝钢管坯料设计问题的进一步 (吕亚娜，唐立新，孟盈，等.钢铁企业板坯动态分配问题的 研究奠定了基础，而且本文提出的数学模型可以被用 建模与分散搜索算法求解.控制与决策，2015,30(1)：17) 于描述有最小装箱量的一维装箱问题，可以应用到物 9]Tang L X,Luo J X,Liu J Y.Modelling and a tabu search solu- 流、仓储、交通运输等各个领域. tion for the slab reallocation problem in the steel industry.Int Prod Res,2013,51(14):4405 参考文献 [10]Rohlfshagen P,Bullinaria J A.Nature inspired genetic algo- [Frisch A M,Miguel I,Walsh T.Modeling a steel mill slab design rithms for hard packing problems.Ann Oper Res,2010,179 problem /Proceedings of the IJCAl-01 Workshop on Modeling (1):393 and Solving Problems with Constraints.Seattle,2001:39 [11]Brusco M J.Kohn H F,Steinley D.Exact and approximate 2]Hnich B,Kiziltan Z,Miguel I,et al.Hybrid modeling for robust methods for a one-dimensional minimax bin-packing problem solving.Ann Oper Res,2004,130(1):19 Ann0 per Res,2013,206(1):611 Xi Y,Li T K.An optimal algorithm for slab designing of fixed [12]Crainic T G,Perboli G,Rei W.et al.Efficient lower bounds weight slabs.J Univ Sci Technol Beijing,2008,30(10):1179 and heuristics for the variable cost and size bin packing problem. (席阳，李铁克.针对固定重量板坯的板坯设计优化算法.北 Comput0 per Res,2011,38(11）:1474 京科技大学学报，2008,30(10)：1179) D3] Hemmelmayr V,Schmid V,Blum C.Variable neighborhood 4]Dawande M,Kalagnanam J,Lee H S,et al.The slab-design search for the variable sized bin packing problem.Comput Oper problem in the steel industry.Interfaces,2004,34(3):215 Res,2012,39(5):1097 5]Gargani A.Refalo P.An efficient model and strategy for the steel 04] Pereira J.Procedures for the bin packing problem with preced- mill slab design problem Proceedings of the 13th International ence constraints.Eur J Oper Res,2016,250(3):794 Conference on Principles and Practice of Constraint Programming [15]Gualandi S,Malucelli F.Constraint programming-based column Berlin,2007:77 generation.40R Q J Oper Res,2009,7(2):113
李铁克等: 单一尺寸圆坯的无缝钢管坯料设计模型与算法 问题的一般性描述并且建立了混合整数规划模型． 针 对原料库中只存在一种尺寸圆坯的常见情况，证明了 此时最小化圆坯数量和最小化圆坯总剩余量具有一致 性，从而简化了问题模型． 结合问题特点，本文提出了 基于贪婪策略的两阶段启发式贪婪策略的启发式算 法，并且证明算法是收敛的． 与传统贪婪策略单一目 标不同，贪婪策略的启发式算法在两阶段选取了不同 的贪婪目标，并以较低的计算复杂度设置了寻优路径． 最后，通过实际生产数据和大量仿真数据的验证，贪婪 策略的启发式算法明显优于传统降序最佳适应算法． 本文研究成果不仅为无缝钢管坯料设计问题的进一步 研究奠定了基础，而且本文提出的数学模型可以被用 于描述有最小装箱量的一维装箱问题，可以应用到物 流、仓储、交通运输等各个领域． 参 考 文 献 ［1］ Frisch A M，Miguel I，Walsh T． Modeling a steel mill slab design problem / / Proceedings of the IJCAI--01 Workshop on Modeling and Solving Problems with Constraints． Seattle，2001: 39 ［2］ Hnich B，Kiziltan Z，Miguel I，et al． Hybrid modeling for robust solving． Ann Oper Ｒes，2004，130( 1) : 19 ［3］ Xi Y，Li T K． An optimal algorithm for slab designing of fixed weight slabs． J Univ Sci Technol Beijing，2008，30( 10) : 1179 ( 席阳，李铁克． 针对固定重量板坯的板坯设计优化算法． 北 京科技大学学报，2008，30( 10) : 1179) ［4］ Dawande M，Kalagnanam J，Lee H S，et al． The slab- design problem in the steel industry． Interfaces，2004，34( 3) : 215 ［5］ Gargani A，Ｒefalo P． An efficient model and strategy for the steel mill slab design problem / / Proceedings of the 13th International Conference on Principles and Practice of Constraint Programming． Berlin，2007: 77 ［6］ Hentenryck P V，Michel L． The steel mill slab design problem revisited / / Integration of AI and OＲ Techniques in Constraint Programming for Combinatorial Optimization Problems． Berlin，2008: 377 ［7］ Zhang W X，Li T K． Modelling and algorithm for the slab designing problem based on constraint satisfaction． J Univ Sci Technol Beijing，2011，33( 5) : 641 ( 张文学，李铁克． 基于约束满足的板坯设计模型与求解方 法． 北京科技大学学报，2011，33( 5) : 641) ［8］ Lü Y N，Tang L X，Meng Y，et al． Modeling and scatter search algorithm for dynamic slab allocation problem in iron and steel enterprises． Control Decis，2015，30( 1) : 17 ( 吕亚娜，唐立新，孟盈，等． 钢铁企业板坯动态分配问题的 建模与分散搜索算法求解． 控制与决策，2015，30( 1) : 17) ［9］ Tang L X，Luo J X，Liu J Y． Modelling and a tabu search solution for the slab reallocation problem in the steel industry． Int J Prod Ｒes，2013，51( 14) : 4405 ［10］ Ｒohlfshagen P，Bullinaria J A． Nature inspired genetic algorithms for hard packing problems． Ann Oper Ｒes，2010，179 ( 1) : 393 ［11］ Brusco M J，Khn H F，Steinley D． Exact and approximate methods for a one-dimensional minimax bin-packing problem． Ann Oper Ｒes，2013，206( 1) : 611 ［12］ Crainic T G，Perboli G，Ｒei W，et al． Efficient lower bounds and heuristics for the variable cost and size bin packing problem． Comput Oper Ｒes，2011，38( 11) : 1474 ［13］ Hemmelmayr V，Schmid V，Blum C． Variable neighborhood search for the variable sized bin packing problem． Comput Oper Ｒes，2012，39( 5) : 1097 ［14］ Pereira J． Procedures for the bin packing problem with precedence constraints． Eur J Oper Ｒes，2016，250( 3) : 794 ［15］ Gualandi S，Malucelli F． Constraint programming-based column generation． 4OＲ Q J Oper Ｒes，2009，7( 2) : 113 · 146 ·