摘 要

Abstract 12

1 绪论 13

1.1 研究背景 13

1.2 研究目的和意义 13

1.2.1 研究目的 13

1.2.2 研究意义 13

1.3 国内外研究现状 13

1.4 研究基本内容 14

1.5 研究方法与行文结构 15

1.5.1 研究方法 15

1.5.2 行文结构 15

2 可用余料的下料问题的定义 16

2.1 引言 16

2.2 1DCSPUL的问题描述 16

2.3 1DCSPUL的下料方案 16

2.3.1 1DCSPUL的下料方案评价 17

2.3.1 余料的分类参数 18

3 列生成法 19

3.1 整数规划模型 19

3.2 列生成法求解整数规划 19

3.3 列生成法的步骤 20

4 启发式方法 22

4.1 算法提出 22

4.2 降序首次适应算法（FFD算法） 22

4.3 贪心算法（Greedy算法） 25

4.4 可用余料下的降序首次适应算法（FFD_L算法） 26

4.5 可用余料下的贪心算法（Greedy_L） 26

5 计算测试 28

5.1 实例使用参数与记号 28

5.2 计算实例 28

5.2.1 实例一 28

5.2.2 实例二 29

5.2.3 实例三 31

6 结论与展望 33

6.1 结论 33

6.2 未来展望 33

参考文献 35

致 谢 37

附录 38

附录1 FFD_L算法步骤 38

附录1 Greedy_L算法步骤 39

摘 要

本文讨论了以管材为代表一维下料问题，并考虑了布局图的切割余料如果规格达标，可在未来投入使用的情况。通过解决文献中的实例，实际实例和随机生成的实例，可以明显看到到修改后的启发式方法的性能。

本文讨论具有有限剩余规格的1DCSPUL整数规划模型，并描述了一种基于列生成过程的启发式算法来解决该问题。还比较了几种启发式算法与整数规划的特点。

研究结果表明，改良后的启发式方法在减少切割损失方面比列生成算法更为有效，尤其是在剩余类型的数量有限的情况下。整数规划的结果较为准确稳定，但是计算困难。

本文的特色在于：批判性地讨论了下料问题寻找下料方案时带来的一些困难之处，例如，在可以使用剩余材料的情况下，下料方案中最小剩余材料分布最有利的评判标准是什么。 定义了一些好的下料方案的理想特性，并讨论改良版的经典启发式方法。对企业生产制造有一定的指导作用。

关键词：一维下料问题；可用余料；列生成法；启发式方法

Abstract

In this work, the problem of one-dimensional cutting represented by pipe is discussed, and the situation that the cutting leftovers material of the patterns can be put into use in the future if the size meets the specifications standard. The performance of the modified heuristic method can be obviously seen by solving the examples in the the instances that generated randomly.

This work also discusses the 1DCSPUL integer programming model with limited types of leftovers, and describes a heuristic algorithm based on the column generation process to solve the problem. And compared heuristic algorithms with integer programming.

The results show that the improved heuristic method is more effective than the column generation algorithm in reducing the cutting loss, especially when the number of leftovers types is limited. The result of integer programming is more accurate and stable, but it is difficult to calculate.

This work features comparing some difficulties brought by the solution of 1DCSPUL, for example, where cutting leftovers can be used, what is the most favorable criterion for the minimum leftovers layout in the solution. The ideal characteristics of some good solutions are defined, and the modified classical heuristic method is discussed. It has a certain guiding role in the production and manufacturing of enterprises.

Key Words：One-dimensional cutting problem；Usable leftovers；Column generating method；Heuristic method

1 绪论

1.1 研究背景

近年来，由于资源的消耗过度和企业对自身成本管理的需要，材料的切割和包装问题引起了很多研究者的兴趣。 这样的问题之一就是一维下料问题（ne-dimensional cutting stock problem, 1DCSP）。 在1DCSP中，从线性原料（如管材，管材和型材；本文仅指管材）切割出具有特定长度和要求的一组物料类型，以制造各种产品。 这个问题出现在许多行业中，例如制造各种车辆，轮船，门，窗和金属家具。 在这些情况下，一个良好的模型和算法有望提高材料利用率。

1.2 研究目的和意义

1.2.1 研究目的

在过去的四十年中，越来越多的研究人员研究了下料问题问题^[1]。研究人员对这些问题的广泛兴趣，体现了他们对实际应用和对学术界难题的挑战。因为虽然它们看起来很简单，但是通常在计算上难以解决^[2]。