在工业生产中经常会遇到2维排样问题，例如金属板材、玻璃、胶合板等切割成工件的下料环节，优良的排样方式能有效地简化板材切割工艺，提高板材利用率，减少资源消耗，降低企业生产成本^[1-3]。2维排样问题，按照工件的几何形状，可分为矩形件排样问题和其他形状件排样问题；按照工件是否允许旋转，可分为可旋转排样问题和不可旋转排样问题；按照每种工件在板材中允许出现的次数是否有约束，可分为有约束排样问题和无约束排样问题；按照下料的切割工艺是否满足一刀切，可分为剪切排样问题和非剪切排样问题。

讨论矩形件无约束2维剪切排样(UTGCR)问题^[4]：将板材$L×W$($L$为长，$W$为宽)剪切成$m$种矩形件，第$i$种矩形件的尺寸为$l_{i}×w_{i}$，价值为$v_{i}$，其中$i∈ \mathit{\boldsymbol{M}}$={1, 2, …, $m$}；对每种矩形件在板材中出现的次数$k_{i}$无约束，优化目标是寻找一个剪切排样方式使得排样价值即板材所含矩形件总价值最大，这里排样价值$V=\sum\limits_{i=1}^{m} k_{i} v_{i}$。该问题属于一刀切允许旋转排样问题。由于可行的剪切排样方式组成的解空间非常庞大，精确算法^[5-6]在求解大规模问题时耗时过长，无法满足实际应用要求。实际中一般采用启发式算法求解UTGCR问题，按照算法的构造思想可分为两类。

第1类是智能优化算法，此类算法在矩形件非剪切排样问题中应用较多，在UTGCR问题中应用相对较少。Alvarez等人^[7]提出了贪心随机自适应搜索算法。Leung等人^[8]提出了混合模拟退火元启发式算法，首先给出一个匹配策略用来确定某位置应该被哪个矩形件最先填充，基于该策略构造一种启发式算法确定矩形件的排放顺序得到初始解，然后采用贪心算法搜索更优解，用模拟退火算法跳出局部最优解实现全局搜索。李波等人^[9]提出了启发式动态分解算法，根据矩形件将板材正交分解成多个子板，计算矩形件的放置耦合度选择最佳子板，通过干涉关系实现所有子板状态更新。Wang等人^[10]提出了粒子群优化算法，适应度函数为板材的浪费面积，解码规则为最佳适应插入排样。Shiangjen等人^[11]提出了双向启发式填充算法，通过在板材长宽两个方向逐层填充剩余空间来最大化板材利用率，用迭代局部搜索和移位策略来平衡广度与深度搜索。此类算法由于收敛性未知从而难以保证解的质量，另外生成的排样方式结构比较复杂，不利于板材切割工艺。

第2类是通过限制排样方式满足一定的几何特征，从而缩小排样方式的解空间，减少算法的计算量。此类算法虽然不保证求到最优解，但是由于计算时间较快，排样方式的结构比较简单, 有利于切割工艺，目前被广泛采用。Hifi^[12]提出了两阶段和三阶段排样方式的动态规划算法，首先构造矩形件在条带上排样的无约束背包问题模型；然后构造条带在段上排样的无约束背包问题模型；最后采用深度优先树搜索确定板材的段划分。崔耀东等人分别提出了两段排样方式的递归算法^[13]和占角排样方式的递归算法^[14]。杨传民等人^[15]提出了简单块四块排样方式的分支定界算法。Cui等人^[16]提出了同质块T型排样方式的动态规划算法，这种算法沿竖直方向将板材切成两个段，每个段包含长度和方向均相同的级，每个级包含一行同质块，每个同质块包含由同种矩形件组成的条带；算法首先采用动态规划生成最优同质块，然后通过求解背包问题得到同质块在级上的布局和级在段上的布局，最后择优选择两个段组成排样方式。之后又提出了三阶段排样方式的改进动态规划算法^[17]，通过求解3个背包问题分别得到矩形件在条带中的布局、条带在段中的布局和段在板材中的布局。季君等人^[18]提出了同质块两段排样方式的背包算法。潘卫平等人^[19]提出了匀质条带三块排样方式的背包算法。薛焕堂等人^[20]提出了复合条带两段排样方式的确定型算法。

本文提出一种新的排样方式——简单块占角排样方式，并构造其动态规划生成算法。在板材左下角排放若干行若干列同种矩形件，将板材剩余部分划分为两个子板，把子板当作板材按照上述方式继续递归考察，直至子板排满矩形件为止。采用动态规划算法从小到大构造所有可能尺寸的子板的简单块占角排样方式，直至得到板材的简单块占角排样方式。

不失一般性，假设矩形件方向固定。因为当矩形件允许转向90°时，可将矩形件$l_{i}×w_{i}$看做$l_{i}×w_{i}$和$w_{i}×l_{i}$两种矩形件。规定板材和矩形件的水平边为长，竖直边为宽。

定义1   简单块。若干行若干列同种矩形件排列在一起组成的矩形块。

定义2   简单块占角排样方式。初始时选择一种矩形件按照简单块方式在板材左下角排放若干行若干列，然后用一条剪切线将板材剩余部分划分为2个子板^[15]；将子板当作板材按照上述方式继续递归考察，直到子板排满矩形件为止。

简单块占角排样方式是一种启发式排样方式，它的基本单元是简单块，简单块只含同种矩形件，可以简化板材的切割工艺。

定义3   排样价值。板材或子板的排样价值是指按照某种排样方式其包含的矩形件总价值。

设$F(x, y)$为子板$x×y$的最大排样价值。为了叙述的统一性，将板材看做长为$L$、宽为$W$的子板。如图 1所示，在子板$x×y$左下角排放$s$行$t$列矩形件$i$后，用一条剪切线沿着矩形件的上边界(如图 1(a)所示)或右边界(如图 1(b)所示)将板材剩余部分划分为A、B两个子板。设两种划分方式所得简单块占角排样方式的价值分别为

$ \begin{array}{c}{f_{X}(x, y, i, s, t)=} \\ {v_{i} s t+F\left(x-t l_{i}, s w_{i}\right)+F\left(x, y-s w_{i}\right)}\end{array} $

(1)

$ \begin{array}{c}{f_{Y}(x, y, i, s, t)=} \\ {v_{i} s t+F\left(t l_{i}, y-s w_{i}\right)+F\left(x-t l_{i}, y\right)}\end{array} $

(2)

排放在子板左下角的矩形件$i$有$m$种选法；对于特定的矩形件$i$，因为矩形件不能超出子板边界，故其在子板左下角允许排放的最大行数为$\left\lfloor {y/w_{i}} \right\rfloor $，最大列数为$\left\lfloor {x/l_{i}} \right\rfloor $，其中符号“$ \left\lfloor {\; } \right\rfloor $”表示向下取整。设图 1(a)划分方式所得排样方式的最大价值为$F_{X}(x, y)$，图 1(b)划分方式所得排样方式的最大价值为$F_{Y}(x, y)$，具体公式为

$ \begin{array} [c]{c} F_{X}(x, y)=\\ \underset{i\in \mathit{\boldsymbol{M}}}{\mathop{\text{max}}}\, \underset{s\in \{1, \ldots , \left\lfloor y/{{w}_{i}} \right\rfloor \}, t\in \{1, \ldots , \left\lfloor x/{{l}_{i}} \right\rfloor \}}{\mathop{\text{max}}}\, {{f}_{X}}\left( x, y, i, s, t \right) \end{array} $

(3)

$ \begin{array} [c]{c} F_{Y}(x, y)=\\ \underset{i\in \mathit{\boldsymbol{M}}}{\mathop{\text{max}}}\, \underset{s\in \{1, \ldots , \left\lfloor y/{{w}_{i}} \right\rfloor \}, t\in \{1, \ldots , \left\lfloor x/{{l}_{i}} \right\rfloor \}}{\mathop{\text{max}}}\, {{f}_{Y}}\left( x, y, i, s, t \right) \end{array} $

(4)

$ F(x, y)=\max \left\{F_{X}(x, y), F_{Y}(x, y)\right\} $

(5)

式(3)(4)表示对于每种子板划分方式按照子板排样价值最大原则选择子板左下角排放的矩形件种类，以及矩形件排列的行数和列数。式(5)表示子板的最大排样价值等于两种划分方式所对应，最大排样价值的较大者。

采用动态规划原理^[21]由小到大逐个构造不同尺寸子板的简单块占角排样方式，在构造当前尺寸的子板排样方式时能够直接使用比当前尺寸小的子板的排样信息。当得到子板$L×W$的简单块占角排样方式时即得到了板材的简单块占角排样方式。

运用规范尺寸可以在不影响解的质量前提下缩小排样问题的计算量^[18]。本文规范长度是矩形件长度的线性组合，规范宽度是矩形件宽度的线性组合。令$ \mathit{\boldsymbol{G}}_{\rm L}$、$ \mathit{\boldsymbol{G}}_{\rm W}$分别为规范长度集合和规范宽度集合，则有

$ \boldsymbol{G}_{\mathrm{L}}=\left\{x \in {\bf{Z}} | x=\sum\limits_{i=1}^{m} a_{i} l_{i} ; a_{i} \in {\bf{N}}, 0 \leqslant x \leqslant L\right\} $

(6)

$ \boldsymbol{G}_{\mathrm{W}}=\left\{y \in {\bf{Z}} | y=\sum\limits_{i=1}^{m} b_{i} w_{i} ; b_{i} \in {\bf{N}}, 0 \leqslant y \leqslant W\right\} $

(7)

式中，$\bf N$为非负整数集合，$a_{i}$为规范长度所包含矩形件$i$长度的个数，$b_{i}$为规范宽度所包含矩形件$i$宽度的个数。规范尺寸具有性质：假如$A_{\rm L}(x)$为不超过$x$的最大规范长度，$A_{\rm W}(y)$为不大于$y$的最大规范宽度，则按照简单块占角排样方式进行排样时子板$x×y$与子板$A_{\rm L}(x)$×$A_{\rm W}(y)$具有相等的排样价值。令$l_{{\rm min}}$、$w_{{\rm min}}$分别为矩形件的最小长度和最小宽度，即$l_{\min }=\min\limits _{i \in \mathit{\boldsymbol{M}}}\left\{l_{i}\right\}$、$w_{\min }=\min\limits _{i \in \mathit{\boldsymbol{M}}}\left\{w_{i}\right\}$。

由规范尺寸性质可知，本文排样算法只需考察规范尺寸的子板即可。分别对集合$\mathit{\boldsymbol{G}}_{\rm L}$、$\mathit{\boldsymbol{G}}_{\rm W}$中的元素进行升序排列，记$\mathit{\boldsymbol{G}}_{\rm L}$、$\mathit{\boldsymbol{G}}_{\rm W}$的第$i$($i=0, …, |\mathit{\boldsymbol{G}}_{\rm L}|－1$)个元素分别为$g_{\rm L}(i)$、$g_{\rm W}(i)$，其中$|\mathit{\boldsymbol{G}}_{\rm L}|$、$|\mathit{\boldsymbol{G}}_{\rm W}|$分别为集合$\mathit{\boldsymbol{G}}_{\rm L}$、$\mathit{\boldsymbol{G}}_{\rm W}$的元素个数。令$l_{{\rm min}}$、$w_{{\rm min}}$分别为矩形件的最小长度和最小宽度，即$l_{\min }=\min\limits _{i \in \mathit{\boldsymbol{M}}}\left\{l_{i}\right\}$、$w_{\min }=\min\limits _{i \in \mathit{\boldsymbol{M}}}\left\{w_{i}\right\}$。易知普通子板的长度个数$\overline{L}$=$L－l_{{\rm min}}+1$，宽度个数$\overline{W}$=$W－w_{{\rm min}}+1$；规范尺寸子板的长度个数为$|\mathit{\boldsymbol{G}}_{\rm L}|$-1，宽度个数为$|\mathit{\boldsymbol{G}}_{\rm W}|$-1。因此普通子板数量为$\overline{L}\overline{W}$，规范尺寸子板的数量为($|\mathit{\boldsymbol{G}}_{\rm L}|$-1)($|\mathit{\boldsymbol{G}}_{\rm W}|$-1)，由于$(|\mathit{\boldsymbol{G}}_{\rm L}|$-1)($|\mathit{\boldsymbol{G}}_{\rm W}|$-1)有可能小于$\overline{L}\overline{W}$，故采用规范尺寸有可能减少算法考察的子板数量，从而加速排样算法的求解过程。

构造动态规划算法生成板材的简单块占角排样方式。令$Q(x, y)$、$N_{1}(x, y)$和$N_{2}(x, y)$分别为子板$x×y$左下角排放的矩形件的编号、矩形件的行数和矩形件的列数；$T(x, y)$表征子板$x×y$剩余部分的划分方式，水平划分时$T(x, y)=1$，竖直划分时$T(x, y)=2$。在计算出板材最大排样价值后，通过逆向追踪上述4个数组的取值，可以得到板材的最优排样方式。简单块占角排样方式的动态规划生成算法具体步骤如下：

输入：一个矩形件无约束2维剪切排样问题的实例$I^{\#}=(L, W, l[\;], w[\;], v[\;])$。

输出：实例$I^{\#}$的最大排样价值$F(L, W)$及其对应排样方式的特征数组$ \mathit{\boldsymbol{Q}}$、$ \mathit{\boldsymbol{N}}_{1}$、$ \mathit{\boldsymbol{N}}_{2}$、$ \mathit{\boldsymbol{T}}$。

1) 初始化$F(x, y)=N_{1}(x, y)=N_{2}(x, y)=T(x, y)=0$, 其中$x=0, …, L$, $y=0, …, W$。

2) For $p=1$ to $(|\mathit{\boldsymbol{G}}_{\rm L}|$-1)

3)   For $q=1$ to $(|\mathit{\boldsymbol{G}}_{\rm W}|$-1)

4)      $x=g_{\rm L}(p)，y = g_{\rm W}(q)$

5)    If $F(g_{\rm L}(p-1), y)≥F(x, g_{\rm W}(q-1)) $

      Then $F(x, y) = F(g_{\rm L}(p-1), y)$

6)   Else $F(x, y)=F(x, g_{\rm W}(q－1))$

7)   For $i=1$ to $m$

8)     If $x <l_{i} \;{\rm or} \;y <w_{i}$

      Then skip type $i$

9)     For $s=1 \;{\rm to}\; \left\lfloor {y/w_{i}} \right\rfloor $

10)        For $t=1 \;{\rm to}\; \left\lfloor {x/l_{i}} \right\rfloor $

11)          If $F(x, y) < v_{i}st + F(A_{\rm L}(x-tl_{i}), sw_{i}) +$ $F(x, A_{\rm W}(y-sw_{i})) $

12)           Then $F(x, y)=v_{i}st+F(A_{\rm L}(x－tl_{i}), sw_{i})+$ $F(x, A_{\rm W}(y－sw_{i})), \mathit{\boldsymbol{Q}}(x, y)=i, $ $ \mathit{\boldsymbol{N}}_{1}(x, y)=s, \mathit{\boldsymbol{N}}_{2}(x, y)=t, \mathit{\boldsymbol{T}}(x, y)=1$

13)           If $F(x, y) <v_{i}st+F(tl_{i}, A_{\rm W}(y－sw_{i}))+$ $F(A_{\rm L}(x－tl_{i}), y)$

14)           Then $F(x, y)=v_{i}st+F(tl_{i}, A_{\rm W}(y－sw_{i}))+$ $F(A_{\rm L}(x－tl_{i}), y), \mathit{\boldsymbol{Q}}(x, y)=i,$ $\mathit{\boldsymbol{N}}_{1}(x, y)=s, \mathit{\boldsymbol{N}}_{2}(x, y)=t, \mathit{\boldsymbol{T}}(x, y)=2$

15)          End for

16)        End for

17)      End for

18)    End for

19) End for

20) For $x=l_{{\rm min}}$ to L

21)    For $y=w_{{\rm min}}$ to W

22)      $F(x, y)=F(A_{\rm L}(x), A_{\rm W}(y))$, 同理, 令$\mathit{\boldsymbol{Q}}, \mathit{\boldsymbol{N}}_{1}, \mathit{\boldsymbol{N}}_{2}, \mathit{\boldsymbol{T}}$数组的元素值为其对应规范尺寸的元素值。

23)   End for

24) End for

步骤1)，初始化所有可能尺寸子板的排样价值和子板排样方式的特征数组：$\mathit{\boldsymbol{Q}}$，$\mathit{\boldsymbol{N}}_{1}$，$\mathit{\boldsymbol{N}}_{2}$，$\mathit{\boldsymbol{T}}$；步骤2)-4)，按照尺寸大小顺序考察所有可能的规范尺寸子板；步骤5)6)，令子板最大排样价值等于与其尺寸最接近的两个小子板的最大排样价值的较大者；步骤7)8)，子板左下角矩形件有$m$种选择，当矩形件尺寸大于子板尺寸时，该种矩形件不予考虑；步骤9)10)，逐个考察矩形件排放的行数和列数，其中矩形件不能超出子板边界；步骤11)12)，若水平划分子板剩余部分得到的子板排样价值更大，则令子板最大排样价值为当前排样价值，且记录左下角的矩形件编号和矩形件行列数及子板划分方式。步骤13)14)，若竖直划分子板剩余部分得到的子板排样价值更大，则令子板最大排样价值为当前排样价值，且记录左下角的矩形件编号和矩形件行列数及子板划分方式。步骤20)-24)，令非规范尺寸子板的排样方式和排样价值与其对应的规范尺寸子板相同。

本文算法的时间复杂度上界为O$(m(\mathit{\boldsymbol{G}}_{\rm L}-1)^{2}(\mathit{\boldsymbol{G}}_{\rm W}-1)^{2}/(l_{\min}w_{\min}))$。

将尺寸为$9×7$的板材剪切成2种矩形件，其中$l_{1}=4$，$w_{1}=3$，$v_{1}=11$，$l_{2}=5$，$w_{2}=7$，$v_{2}$=36，对每种矩形件在板材中出现的次数无约束，优化目标是寻找一个剪切排样方式使得排样价值即板材所含矩形件总价值最大。

用本文算法求解该例题。由式(6)(7)确定规范长度集合$\mathit{\boldsymbol{G}}_{\rm L}|={0, 4, 5, 8, 9}，规范宽度集合|\mathit{\boldsymbol{G}}_{\rm W}$={0, 3, 6, 7}，可知($|\mathit{\boldsymbol{G}}_{\rm L}|$-1)=4，($|\mathit{\boldsymbol{G}}_{\rm W}|$-1)=3，故算法中$p$的取值范围为{1, 2, 3, 4}；$q$的取值范围为{1, 2, 3}。

当$p$=1，$q$=1时，执行算法步骤4)-6)，由于$F(0, 3)≥F(4, 0)$，故$F(4, 3)=F(0, 3)=0$(这里$F(g_{\rm L}(p-1), g_{\rm W}(q))$为$F(0, 3)$，$F(g_{\rm L}(p), g_{\rm W}(q－1))$为$F(4, 0)$，$F(g_{\rm L}(p), g_{\rm W}(q))$为$F(4, 3)$)。执行算法步骤7)-17)，当$i$=1，$s$=1，$t$=1时，由于$F(4, 3)=0 < v_{1} + F(A_{\rm L}(4-l_{i}), w_{i}) + F(4, A_{\rm W}(3-w_{1}))=11+F(0, 3)+F(4, 0)=11$，故$F(4, 3)$=11，同时记录数组$ \mathit{\boldsymbol{Q}}、\mathit{\boldsymbol{N}}_{1}、\mathit{\boldsymbol{N}}_{2}、\mathit{\boldsymbol{T}}$的对应元素值；当$i$=2，$s$=1，$t$=1时，算法步骤8)由于4 <$l_{2}$，故跳过$i$。最终得到$F(4, 3)$=11。

同理可得：$F(4, 6)=2v_{1}$=22，$F(4, 7)=2v_{1}$=22，$F(5, 3)$=$v_{1}$=11，$F(5, 6)$=2$v_{1}$=22，$F$(5, 7)=$v_{2}$=36，$F(8, 3)$=2$v_{1}$=22，$F$(8, 6)=4$v_{1}$=44，$F(8, 7)$=4$v_{1}$=44，$F(9, 3)$=2$v_{1}$=22，$F$(9, 6)=4$v_{1}$=44。

当$p$=4，$q$=3时，执行算法步骤4)-6)，由于$F(8, 7)≥F(9, 6)$，故$F(9, 7)=F(8, 7)$=44。执行算法步骤7)-17)，当$i$=1时，可知$s$取值范围为{1, 2}，$t$取值范围为{1, 2}。当$s$=1，$t$=1时，算法步骤11)条件$F(9, 7) < v_{1} + F(A_{\rm L}(9-l_{1}, w_{1})) + F(9, A_{\rm W}(7-w_{1}))=11+F(5, 3)+F(9, 3)$=44不成立，算法步骤13)条件$F(9, 7) < v_{1} + F(l_{1}, A_{\rm L}(7-w_{1})) + F(A_{\rm W}(9-l_{1}), 7)=11+F(4, 3)+F(5, 7)$=58成立，执行算法步骤14)，$F(9, 7)=58$，同时记录数组$ \mathit{\boldsymbol{Q}}、\mathit{\boldsymbol{N}}_{1}、\mathit{\boldsymbol{N}}_{2}、\mathit{\boldsymbol{T}}$的对应元素值。同理可得$s$=1，$t$=2时，$F(9, 7)=58$；$s$=2，$t$=1时，$F$(9, 7)=58；$s$=2，$t$=2时，$F(9, 7)=58$。

当$i$=2时，可知$s$的取值范围为{1}，$t$的取值范围为{1}。当$s$=1，$t$=1时，同理可得$F(9, 7)=58$。

因此最终得$F(9, 7)=58$。通过逆向追踪数组$ \mathit{\boldsymbol{Q}}、\mathit{\boldsymbol{N}}_{1}、\mathit{\boldsymbol{N}}_{2}、\mathit{\boldsymbol{T}}$的元素取值，可以得到板材的简单块占角排样方式。图 2为例题的解，其中灰色区域为板材裁剪后的剩余部分。

采用文献[14, 18]实验所用的全部例题，共有5组，其中第1组、第2组和第4组为国际通用的Benchmark基准例题(http://www.laria.u-picardie.fr/hifi/OR-Benchmark)；第3组为随机例题，第5组为实际生产实例。需要注意的是文献[18]所用的例题矩形件方向允许转向90°，文献[14]所用的例题矩形件方向是固定的。本文算法是简单块占角排样方式的精确算法，由于简单块占角排样方式是一种启发式排样方式，它只是剪切排样方式的一个子集，故本文算法也可以看做是剪切排样方式的一种启发式算法。将本文算法与9种文献算法进行比较，其中文献[5-6]算法是剪切排样方式的精确算法，其余7种文献算法是剪切排样方式的启发式算法。由于本文算法和9种文献算法都是确定性算法，故只要算法执行完毕，实验环境只对算法的计算时间有影响而对算法优化结果无影响。本文实验采用的计算机为：AMD速龙4880+ CPU主频2.8 GHz，内存512 MB。

本组包含41道国际通用的Benchmark例题，具体参见文献[12]。表 1为5种算法的排样价值统计结果，4种文献算法的排样价值和计算时间(硬件环境与本文算法相同)来源于文献[18]。从表 1可以看出，对于41道例题，本文算法均得到了最优解；文献[16]同质块T型算法有34道例题得到最优解；文献[18]同质块两段算法有36道例题得到最优解；文献[20]复合条带两段算法求解了其中20道例题，有16道例题得到最优解。

本文算法求解41道例题，总共耗时19.67 s，平均每道例题耗时0.48 s，计算时间在实际应用中合理。文献[16, 18]算法平均每道例题分别耗时0.46 s和0.51 s，文献[20]算法计算时间未被报道。文献[5]精确算法每道例题平均耗时41.67 s，其中例题UU11耗时958.55 s，本文算法求解例题UU11只用13.67 s。综上得：1)本文算法在计算时间合理的前提下，排样优化结果好于文献[16, 18, 20]这3种文献算法；2)本文算法在排样优化结果等于文献[5]精确算法的前提下，计算时间远短于文献[5]精确算法。

本组包含20道国际通用的Benchmark例题^[7]。表 2为6种算法的排样价值统计结果，其中前4种文献算法的排样价值和计算时间(硬件环境与本文算法相同)来源于文献[18]的表 6，第5种文献算法排样价值和计算时间(主频2.7 GHz，内存2 GB)来源于文献[19]。从表 2可以看出，本文算法有19道例题得到最优解；文献[12]经典三阶段算法有2道例题得到最优解；文献[16]同质块T型算法和文献[18]同质块两段算法均有5道例题得到最优解；文献[19]匀质条带三块算法没有例题得到最优解。

本文算法每道例题的排样价值均高于或等于文献[12, 16, 18-19]算法。本文算法求解20道例题总共耗时38.64 s，平均每道例题耗时1.93 s，计算时间可以满足实际应用需要；文献[12, 16, 18-19]算法平均每道例题分别耗时32.96 s、2.18 s、2.18 s和0.023 s。文献[5]精确算法每道例题平均耗时92.08 s。综上得：1)本文算法计算时间长于文献[19]算法，但短于文献[12, 16, 18]算法，排样优化结果好于这4种文献算法；2)本文算法排样优化结果非常接近文献[5]精确算法，但计算时间远远短于文献[5]精确算法。

本组包含50道随机例题，具体参见文献[18]。在相同的硬件环境下，分别用本文算法、文献[17-18]算法求解这组例题，表 3为实验统计结果。从表 3可以得出本文算法板材利用率高于文献[17-18]算法；计算时间短于文献[18]算法，略长于文献[17]算法。图 3为本文算法和两种文献算法求得的例题26的排样方式，图中数字表示矩形件编号；灰色区域为板材裁剪后的剩余部分。本文算法、文献[17-18]算法求得的排样方式的排样价值分别为4 497 382、4 490 668和4 497 306。文献[17-18]算法的排样价值均小于本文算法。

本组包含31道国际通用的Benchmark例题，具体参见文献[14]。例题的板材尺寸及其规范尺寸子板数量如表 4所示。从表 4可以看出，规范尺寸子板的数量只有普通子板数量的11%~66%，平均为34%。本文算法求解这31道例题，算法总共耗时7.39 s，平均每道例题耗时0.24 s，所有例题均求出了最优解。在不运用规范尺寸时求解31道例题总共耗时32.89 s，平均每道例题耗时1.06 s，可见运用规范尺寸可以提高算法的计算效率。文献[14]算法平均每道例题耗时0.64 s(硬件环境与本文算法相同)，有2道例题未得到最优解。

用本文算法求解文献[18]的4.4节桂林客车厂的排样实例，算法求得了最优解，耗时0.86 min；文献[18]两段算法和文献[6]精确算法也求得了最优解，分别耗时1.6 min和21 min(硬件环境与本文算法相同)。可以看出本文算法在计算时间上优于文献[18]算法和文献[6]精确算法。

针对矩形件无约束2维剪切排样问题，设计了一种简单块占角排样方式，构造了其动态规划生成算法，这种排样方式能使同种矩形件尽量聚集在一个块中，有利于板材切割工艺。本文算法是剪切排样方式的启发式算法，与剪切排样方式的其他启发式算法相比，本文算法排样价值高于同质块T型排样算法、同质块两段排样算法、经典三阶段排样算法、普通占角排样算法、复合条带两段排样算法、改进的三阶段排样算法和匀质条带三块排样算法，计算时间比前4种算法短，比后2种算法长。与剪切排样方式的精确算法相比，本文算法计算时间远小于精确算法，优化结果非常接近精确算法。本文算法设计思想比较简单，计算时间能满足实际应用需要。

由于本文算法只考虑单张板材上矩形件的无约束排样，故只能生成单张板材上矩形件的排样方式；对于每种矩形件需求量已知的下料问题，本文算法暂无法解决。今后可将本文算法作为排样方式生成算法与线性规划、整数规划和顺序启发式算法相结合来求解矩形件2维剪切下料问题。