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