X-向多段排样方式及其生成算法

李华

摘要：为解决大规模矩形毛坯无约束的二维剪切排样问题，提出多段排样方式及其生成算法。排样用一组剪切线将每段切分成一系列的块，每个块由一组水平方向的同质条带构成。实验结果表明，该算法能在合理的计算时间内取得较好的优化结果。

关键词：无约束二维切割;下料;多段排样方式;背包问题

引言：矩形件优化排样问题是指将一组矩形件互不重叠的排放在有限的区域内，并实现资源优化利用的布局问题，其研究成果主要应用在板材、玻璃加工业、金属制品业等领域。最大限度的提高材料利用率、节约生产成本，简化切割工艺、缩短计算时间、提高企业效率成为增强企业竞争力的关键。因此，矩形件的优化排样问题一直是国内外众多学者研究的热点。

本文讨论矩形毛坯无约束的二维剪切排样（Unconstrained two-dimensional cutting，UTDC）问题：采用剪切方式，将板材（长宽）切成种毛坯，第种毛坯的尺寸为，价值为，对每种毛坯在板材出现的次数无约束，排样目标是使得板材所含毛坯的总价值最大。令可行的排样方式中含第种毛坯个，为自然数的集合，则UTDC的数学模型为：

（1）

St. ;;满足一定的切割工艺的要求。

在生产实践中，经常将UTDC算法和线性规划算法相结合以求解二维下料问题（two-dimensional cutting stock problem，TDCSP）：使用库存板材剪切出种矩形小毛坯，第种毛坯的尺寸为，需求量为，，要求确定下料方案，在满足全部毛坯需求的前提下，使得消耗的板材总面积最小。在求解下料方案的过程中，需要反复调用UTDC算法。因此，要求UTDC算法能在合理的计算时间内给出高质量的解。

目前研究的UTDC算法大致可分为三类：第一类是生成普通排样方式的精确算法[1-2]。第二类是生成普通排样方式的近似算法[3-4]，该算法由于其收敛性未知，无法保证解的质量。第三类是生成具有明确几何性质的排样方式算法，如两段[5-6]、T形[7]、两阶段[8-9]、3阶段[9-10]、层排样[11]、同质三块[12]等排样算法，这类排样算法的利用率可能略低，但其切割工艺简单，得到广泛的应用。

本文研究特定类型的排样方式，提出多段排样方式及其生成算法，即在文献[12]的基础上，将辅助分界线由一条扩展到多条，将板材切成若干块;且在切割工艺方面，排样方式还可应用于求解生产中滚剪下料问题，简化切割过程，减少人工工作量。

本文详细介绍了排样方式及其生成算法，并通过两组实验测题验证了算法的有效性，实验结果的将在第3节详细列出。

1多段排样方式中的概念

1.1同质条带。条带由若干个互不重叠、水平（X向）或竖直（Y向）排列的毛坯组成。按照条带所含毛坯类型，可将其分为单毛坯条带和多毛坯条带。单毛坯条带又称同质条带，其中仅含尺寸和方向均相同的毛坯。多毛坯条带又称普通条带，其中含多种不同毛坯。本文采用X向同质条带，与采用普通条带相比利用率虽略低，但切割工艺较为简单。

1.2块。块是指由长度和方向均相同的X向同质条带拼接而成的板材的矩形區域，如图2所示，毛坯中的数字指明毛坯的类型。通过一系列的剪切的过程可将块切分成若干条X向同质条带，每次切下一根X向条带，连续被切下的两根条带相互平行。

2算法原理及实现

设板材和毛坯的尺寸均为整数，毛坯的方向固定。现只介绍生成X-向最优排样的方法，主要包含以下几个步骤：（1）求解X向带最大价值。（2）确定不同尺寸的最优块排样。（3）确定块在段上的最优排样。

2.1求解条带价值

记条带的宽度向量为，，对矩形毛坯，为第种毛坯的单价，为全部毛坯的最小宽度，即，条带长度为时的价值向量为

，可由如下公式决定：

， ，. （2）

2.2生成最优块。对长宽的块，设含第种X向带根，结合2.1节给出的求解X向带的最大价值方法，根据文献[9]动态规划的算法思想，可确定组成X向段的块中所含条带的总价值，，递推公式如下：

（3）

式（3）为最大化一定尺寸块价值的背包问题，可采用文献[13]中的动态规划算法求解。为减少计算时间，在求解过程中利用如下技术减少块中考虑拼接条带的数目：（1）将块排样初始化为块和块中较好者。（2）若，可令，因为，当出现在块中时，可用较短的条带代替它，而不影响解的质量。

2.3块在段上的最优排样

根据2.2节段的定义可知：X向段由一系列水平排列高度均相同的块构成，记为X向段最大价值，，则有如下公式：  （4）

，，

上述模型是典型的背包问题，可利用文献[13]中的动态规划算法求解。其中，背包长度为，需要考虑种物品，第个物品的长度为（对应于尺寸为的块），该物品个数为。

2.5算法步骤

步1：按2.1节式（2）确定各种尺寸的条带的价值。

步2：按2.2节式（3）确定各种尺寸的块的价值。

步3：求解2.3节式（4），得到各种尺寸的段的价值。

2.6算法的时间复杂度

1）式（2）确定条带价值的复杂度为。

2）式（3）确定块价值的复杂度为。

3）式（4）确定高度一定段价值的复杂度为。

由于，综上所述，X-向排样算法的时间复杂度为。