摘 要

诸如钢铁和纸张等许多行业中的有一个重要问题是如何确定生产管料或管料应如何切割成用户所需产品的长度。在这个问题中的考虑最多的经济因素是修剪损失，即由于管材切割而未使用的那部分管材。目前在很多情况下都可以找到最小修剪损失的解决方案。虽然这是一个重要的进步，但实际上管材修剪问题并未得到解决。由于所涉及的材料通常每单位尺寸的价值较低并且需要许多处理和操作，因此将判定标准定义为修剪损失的最小化通常是不恰当的。除此之外有一个更好的标准是所有可控成本的最小化。这不仅包括修剪损失的成本，还包括各种操作（例如分切）所产生的成本，产品在重新成型之前必须符合用户提出要求。因为选择切割模式可以控制完成每个操作所需的各种成本，所以这些成本变成可控。

本文总结了一维下料问题，和国内外一维下料问题的研究现状，介绍了几种典型的一维下料算法，并对其中存在的问题和优缺点进行了介绍。最后，提出了一种有效的计算机程序来解决由模式变化引起的成本变化的一维下料问题。最后介绍了两个实例问题及其解决方案，并总结了该启发式算法的优势。

关键词：切割下料，修剪损失，顺序启发式；

Abstract

An important problem in many industries, such as steel and paper, is how to determine how long the production pipe or tube should be cut into the user's required product. The most important economic factor in this problem is pruning loss, that is, the part of pipe that is not used because of pipe cutting. At present, the minimum trim loss can be found in many cases. Although this is an important progress, the problem of pipe pruning has not been solved. Since the material involved is usually lower in value per unit size and requires a lot of treatment and operation, it is often inappropriate to define the criteria as minimization of pruning losses. In addition, a better standard is the minimization of all controllable costs. This includes not only the cost of pruning losses, but also the cost generated by various operations such as cutting, and the product must meet the requirements of the user before remolding. Because the choice of cutting mode can control the cost of each operation, so these costs become controllable.

Apart from pruning losses, other factors may also introduce nonlinearity, making finding the optimal solution more difficult or even impossible. Therefore, there are few solutions to nonlinear problems in the literature. Nevertheless, the nonlinear problem still exists and largely prevents the execution of computer cutting procedures. Manually generated solutions (at least considering these nonlinear factors) are usually better than solutions generated by incomplete computer programs.

This paper first summarizes the one dimension blanking problem, and then summarizes the research status of one dimension blanking problem at home and abroad, and then introduces several typical one-dimensional cutting algorithms, analyzes their problems and advantages and disadvantages in application, and finally proposes an effective computer sequence to solve the one dimension caused by pattern change. The problem of blanking. Two instances and their solutions are introduced, and the advantages of the heuristic algorithm are discussed.

Key Words：Cutting off material, pruning loss, sequential heuristic；

目 录

摘 要 I

Abstract II

第1章 绪论 1

1.1 问题的概述 1

1.2一维下料问题国内外研究现状 2

1.3 本题研究的主要内容 4

1.4 本文结构安排 4

第2章 一维下料问题常见的数学模型和算法在实际应用中存在的问题 5

2.1 一维下料问题的数学模型描述 5

2.2 早期的经典启发式算法 6

2.3 基于遗传算法的求解方法 7

2.4 基于模拟退火算法的求解方法 8

第3章 基于顺序启发式算法的求解方法 9

3.1 求解下料问题的一种顺序启发式算法模型建立 9

3.1.1 问题的描述及定义 9

3.1.2数学模型的建立 9

3.2 切割模式的计算方法 10

3.3 算法流程 11

3.4 算法在程序中的实现步骤 13

第4章 一维下料程序在实际问题中的实验计算 15

4.1 实验计算 15

4.2 第一组算例 15

4.2.1 结果对比与分析 15

4.3 第二组算例 16

4.3.1 结果对比与分析 16

4.4 本章小结 17

第5章 总结与展望 18

5.1 总结 18

5.2 展望 18

参考文献 20

致 谢 23

附录 20

第1章 绪论

1.1 问题的概述

在各种领域中，如水利、国防、电力、机械、航空航天等这些行业中下料问题获得了越来越多的使用。近年来，随着经济计划与管理的科学化和综合化，资源优化配置与利用的合理化，工程技术的复杂化、大型化与精密化，寻找最优的决策以期获得最佳的技术方案和经济效益已经成为促进企业健康发展，提高自身竞争力的发展趋势^[1]。找出一个比较好的下料方式，可以给企业以及公司带来更大的效益和收益，这些好的下料方案不仅可以节省原料的使用，还可以简化整个切割过程，大大的加快切割的速度。所以，对于下料问题的研究，从70年代起至今，各国学者对该问题的研究不仅仅体现了该问题具有指导生产实践的价值，而且能够增加公司以及企业的经济效益。

这些年来，下料问题引起了许多研究者的广泛关注，人们根据所需要解决的具体问题，从不同的角度、采用不用的方法对其进行了大量的研究，提出了许多下料问题的数学模型和一些行之有效的算法^[2]。

切割下料的优化问题可以具体的描述为通过优化一个目标函数，将原材料切割成订单所需的坯料数目。根据原材料和所需坯料的尺寸数量，该下料优化问题可进一步分为以下三类:一维下料问题、二维下料问题和三维下料问题。一维下料问题所指为常见的型材、棒材等的下料，具体描述为只考虑一个方向，即长度方向的下料，比如，建筑业，制造业中所使用的钢管，钢筋，铝合金，塑料管等材料，结果是要使得这些材料的利用率提高，余料减少。二维下料问题所主要是板材的下料，具体描述为将原板材切割为所需要不同大小和形状的坯料，比如类似于报纸的排版，书刊的排版，集成电路的排布等都可以统称为二维下料问题（二维排样）。此外，坯料在线圈平面上的排出也属于这种问题。三维下料问题又称为三维布局问题，具体指的是原材料和所需坯料的长、宽、高、都要规划具体的尺寸，也可以抽象的描述为根据零件的长、宽、高，将零件装入一个固定大小的箱子中，要求箱子的使用量要最少，也可以称为三维装箱问题。本文侧重的是一维下料问题的讨论，将重点放在考虑通过一种固定长度的原材料去切割多种需求长度的生产管的下料问题。

根据不同的原材料一维下料问题也可以分为等长、不等长的一维下料问题。相同长度的原材料一般是有足够多的原材料以满足订单中的不同的切割需求，而不等长的原材料，且有限数量的原材料，所有原材料的总长度可以满足订单的切割需求。具体的一维下料优化问题的解决方案是生成切割模式方案，该模式方案可以包括不同的排样方法。同时指出各种模式方案中原材料的重复使用次数和使用方法。而最终要达到的目的是使目标解最优化，这个目标也可以分为两种情况，一种是以消耗的原材料最少作为目标函数，另一种情况是将整个下料过程中产生的余料最少作为目标函数。在找出这个所谓好的下料方案过程中，需要考虑到原材料的使用率高，排样的模式数量多少，最后切割完的材料余料最少等多个目标实现优化。目前，国内外对于一维下料问题的研究，主要是在减少排样方式上或提高原材料利用率，所采用的算法包括启发式算法、精确算法和各种智能算法等，并取得了许多成果。

1.2一维下料问题国内外研究现状

伴随着工业技术的迅速发展和资源紧张，各种行业都对该‘下料’问题重视起来。国内外的许多学者，在过去的40多年中都有研究过切割下料的问题。

研究该问题最早的属于国外学者，典型的第一个一维下料问题的数学模型在1939年由前苏联经济学家Kantorovich提出，他的主要观点是用线性规划的方法去研究该下料问题^[3]。所采用的方法为解乘法，由于方法很不完善，所以得到的解不能保证为最优解。美国数学学家G.B.Dantzing 在1947年提出了解线性规划的单纯形法，他是通过不断的换基迭代去寻找最优基，经过有限的步骤之后就可以得到最优解，这个线性规划方法在往后得到了广泛的应用。

Gilmore和Gomory分别于1961年、1963年和1965年用线性规划的方法建立了一个线性规划的数学模型，其主要的思想是将主要规划问题划分为多个子规划问题，通过求解辅助的背包问题来生成新的可以改进的线性规划可行基的切割模式^[4、5、6]。这种方法使得用线性规划方法求解一维下料问题成为可能。并且大大缩短了解决这一问题的时间。这一突破为今后一维下料问题的解决奠定了基础。自那时以来，越来越多的学者参与到了这一领域，并提出了各种标准和算法。

由于原材料和坯料的数量在生产中是大量存在的，所以Harld Dyckhoff 于1981年提出了另外一个线性规划的数学模型，并且于九年后的1990年提出了求解该一维下料问题的经典算法^[7]。该数学模型主要从两个方面去考虑一维下料问题，第一个方面是以模式为导向，以模式为导向的方法通常是结合线性规划的思想，但是由于只考虑模式可能会产生多余的零件，而超过订单的需求量；另外一个方面是以去毛坯的需求量为导向，当以需求量为导向时具体的方法是逐个对每一项的需求去单独切割，处理完一项需求再去出来另外一项需求，该导向的方法通常与顺序启发式算法结合，由于该算法的贪婪性造成了处理后面需求向时差生的排样方式使得材料的使用率降低。

想找出既是最优解又是整数解的方法在实际的实践中是比较难的，所以，启发式算法变成了求解一维下料问题最优解的一种重要的方法，并且得到了广泛的使用。于是就有了Haessler在1975年提出的顺序启发式算法（Sequential Heuristic Procedure，简称SHP ）^[8]，该算法的主要思想为：在剩余的需求订单中找到满足让原材料适应率比较高而且余料（即损耗）比较少的排样模式，并且最大可能性的去重复使用这种排样模式，顺序的执行这一过程一直到所有的订单切割需求任务完成。这一种算法是最具有代表性的启发式算法。

Chauny和Loulou给出了一个基于线性规划方法的多线材下料问题的求解过程^[9], 首先用一种特殊的启发式方法对问题的线性规划解进行舍入，然后用分支定界法对其整数解进行改进，最后得到问题的最优解

Gradisar将一种字典排序的方法应用于多种原材料的一维下料问题^[10]，以订单需求量作为导向的顺序启发式算法解决一维下料问题，首先使用线性规划的方法求解，再讲得到的结果中超出需求量的解删除掉，最后再用SHP算法求解，最后得到的解为两部分解的和，这种方法不仅仅满足了订单的需求量还减少切割损失。

用1999年，Chu尝试着将动态规划方法运用到求解下料问题中^[11]。指出这种方法只能用于精确解决极小的切割下料问题。同时，提出了一种基于动态规划的启发式算法来求解大规模一维下料问题的近似解。该算法与SHP算法的思想有一定的相似性，实验结果表明，该算法在解决多目标、多准则的消隐问题方面具有良好的性能。也表明了，相对于一些传统的优化算法如果加以改进即可以应用到实际具体的求解下料的问题中去。

Below和Scheithaue结合Chvatal-Gomory的割平面方法与列生成技术对多种长度原材料的一维下料问题进行了求解^[12,13]。然后采用基于序贯值修正的启发式算法求解一维下料问题。在传统序贯启发式算法的基础上，结合空值修正的启发式策略，给出了空值修正公式。实验结果表明，该算法在提高材料利用率方面是有效的。

由于一维下料问题在生活和生产中有着重要的应用，国内许多学者也进行了大量的相关研究并取得了丰硕的成果。曹炬等用遗传算法讨论了大规模矩形优化布局问题的求解^[15]。2001年，聂义勇等采用了一种典型的基准下料算法来解决背包问题，并提出了一种考虑剩余库存利用的下料方案^[16]。

崔耀东教授等采用更改进的顺序启发式算法求解一维下料问题^[14,17]，采用多种启发式策略和参数优化方法，很好地解决了一维下料问题。在保证材料利用率的前提下，考虑了减少布局方式数量、增加多余长度等优化目标，布局方案效果明显。

可以看出，解决一维下料问题的关键在于建立良好的数学模型和使用良好的算法。近年来，国内外许多专家学者采用各种智能算法来解决一维下料问题。遗传算法、模拟退火算法、蚁群算法等得到了广泛的应用，并将一些改进的遗传算法或两种以上智能算法相结合。可以看出，当问题规模较小时，可以使用线性规划来解决这个问题。当问题规模较大时，下料问题是一个NP难问题^[18,19,20]，而对于NP难问题，只能用近似算法来求解。

1.3 本题研究的主要内容

本文提出一维修剪问题的一个公式，即切割的固定费用是与使的切割模式有关。固定费用的目的是限制模式变化的数量。由于可能的切割的模式数量众多，所导致的问题远远超出了现有的算法所编程的程序。因此，我们制定了一个启发式程序，可以通过实验调整来平衡潜在的相互冲突的目标，即尽量减少修剪损失和模式变化。启发式程序是围绕一个顺序搜索来组织的，该搜索依赖于未处理订单的描述符，以便为下一个进入解决方案的模式（如修剪损失和模式用法）设置目标。并且给两个示例问题，去讨论该启发式过程的应用范围。

1.4 本文结构安排

本文各章节按照以下方式组织:

第一章 绪论。概述了一维下料问题，介绍了一维下料问题的研究进展和本文的主要工作。

第二章 一维下料问题的数学模型及几种典型算法。给出了一维下料问题的一般数学模型，并对其基本解法进行了介绍和分析。

第三章 基于顺序启发式算法的求解方法。详细介绍本文算法的算法思想及其具体实现方法。

第四章 该一维下料程序在实际问题中的实验计算。本章通过两组实验实例验证了该系统算法的有效性并与其它文献的算法结果进行对比分析其切割模式和余料的大小。

第五章 总结与展望。对全文进行了总结，并指出了存在的问题和进一步的研究工作。

第2章 一维下料问题常见的数学模型和算法在实际应用中存在的问题

本章将介绍本文中应用的一些符号、模型及算法。首先对一维下料问题进行了数学描述，然后介绍了解决一维下料问题的几种常用方法，包括传统的线性整数规划模型、早期的启发式算法、模拟退火算法和遗传算法。

2.1 一维下料问题的数学模型描述

许多作者认识到，一维下料切削损失最小化问题可以用下面的公式来描述为线性规划问题：

, （2.1）

其中 ,；

这里，R是订货需求量的向量，为包含一组元素，i=1，2...，n，的切割方式，表示从第j种切割方式种产生第i种零件的数量。

是按照模式J去处理生产原管的模式数量(模式重复次数)，是模式J引起的修剪损失的尺寸数。如果W是最大可用长度（原管长），

为了使成为可行的切割模式，必须满足以下限制条件:

, 为整数 （2.2）

中等大小的问题中可能存在大量的切割模式，从而排除了用标准线性编程解决这些问题的可能性。直到1961年, Gilmore和 Gomory开发了他们的延迟模式生成技术，可以有效地解决可能出现的任意模式的问题。