一维下料CAD 系统的测试与评价*

李好学 杨 柳 崔耀东

(①河南机电高等专科学校机电系，河南 新乡 453003;②广西大学计算机与电子信息学院，广西 南宁 530004)

制造业经常需要将线材(型材、管材、棒材等)切成各种长度的毛坯，用于制造产品。采用一维下料CAD 系统确定下料方案，可以有效地降低产品成本。本文通过对一维下料过程与应用软件的分析，阐述CAD 系统应该考虑的优化目标与工艺约束;以五种影响较大的CAD 系统为对象，通过示例说明如何对系统功能进行测试与评价。目的是使通过阅读本文，潜在的软件设计者能够根据所面向的用户，确定CAD 系统应该具有的功能;潜在的用户能够根据自身需求的特点，通过功能测试选择CAD 系统。

1 一维下料问题及排样方案的特点

在一维下料问题(1DCSP:1D Cutting Stock Problem)中，使用库存M 种线材切割m 种毛坯。第i 种毛坯的长度和需求量分别为li和di，第k 种线材的长度、库存量(根数)和单价(每根价值)分别为Lk、Dk和Ck，i=1，…，m;k=1，…，M。1DCSP 的解是一个排样方案，其中包括若干个排样方式。排样方案具有下列特点:

(1)每个排样方式所含毛坯总长度和切口损耗材料长度之和，不超过所用线材的长度。

(2)排样方案所含每种毛坯的数量等于其需求量。

(3)排样方案所使用的每种线材的根数不超过其库存量。

为方便起见，以下叙述中将不考虑切口损耗。本文使用下料示例如下:使用8 种型材切割16 种毛坯;表1 所示为型材数据，假定每根型材的价格等于其长度;表2 所示为毛坯数据，毛坯总长度341 108 mm。图1 所示为一个下料方案，每个排样方式左侧给出“序号* 线材长度* 线材根数”。例如，排样方式1 使用长度为3 000 mm 的线材18 根，每根线材中含3 号、7 号和12 号毛坯各1 件。排样方案含12 个排样方式，共使用线材88 根，总长度为34 200 mm。排样方案的材料利用率为99.74%(=341 108/342 000)。不难验证每种毛坯的需求都得到了满足，每种线材的使用量不超过库存量。例如对于7 号毛坯，按排样方式1 切出18 件，按排样方式9 和10 各切出1 件，切出的总数正好等于需求量20 件。

表1 示例的型材数据

表2 示例的毛坯数据(总长度341 108 mm)

2 一维下料CAD 系统的优化目标

1DCSP 通常是个多目标优化问题，主要目标通常是线材成本最小。此外，尚需考虑减少排样方式数、减少短材料库存、集中余料等次要目标。

减少排样方式数:下料机床通常有多把切割刀具。将按同一排样方式切割的一根或多根线材装夹好后，沿垂直于线材长度方向一次进刀，就可以将这些线材切成毛坯。每更换一个排样方式，就需要调整全部或部分刀具的位置，以保证切下的各种毛坯具有准确的长度。减少排样方案中所含排样方式数，就可以减少刀具的调整次数，从而降低下料成本。

减少短材料库存:短材料即长度较短的线材，可以是过去下料过程中产生的余料，也可以是从市场上购买来的。短材料通常较难有效利用，库存管理也较麻烦。在不明显提高线材成本的前提下，生成下料方案时应尽量使用短材料。

集中余料:有时因库存线材种数少或毛坯平均需求量小等原因，导致余料较长。这时应尽量将余料集中到排样方案的最后一根线材上，产生一根较长的余料，返回库存供以后使用。

尽管1DCSP 可能涉及的目标很多，但对于具体的生产环境，目标数就不一定多，通常只考虑1～3 个目标就够了。常采用两种方式处理1DCSP 的多目标:成本法和优先级法。成本法的优化目标是总成本最小，要求将每个目标都按金额折算。优先级法按重要性排定目标顺序，优先考虑高优先级的目标。

设计CAD 系统时，采用文献［1］中的算法可以达到减少排样方式数的目的，采用文献［2］中的算法可以达到减少短材料库存的目的，采用文献［3］中的算法可以达到集中余料的目的。

3 一维下料的工艺约束

最大毛坯数约束和最大毛坯种数约束是两个最为常见的工艺约束。

最大毛坯数约束:指一个排样方式中所含毛坯数的上限。本约束通常取决于下料机床所具有的刀具数，因为要求一次进刀切下一根线材中所含全部毛坯。

最大毛坯种数约束:指一个排样方式中所含毛坯种数的上限。按一个排样方式切割时，切下的各种毛坯需要分开存放(例如，一种毛坯占用一个容器)。毛坯种数多，需要的容器数多，占据的工作场地面积大。因此，本约束取决于可供使用的容器数或工作场地面积。采用文献［4］中的算法，可以达到约束毛坯种数的目的。

尽管1DCSP 可能涉及的工艺约束很多，但对于具体的生产环境和下料数据，约束数就不一定多。

4 一维下料CAD 系统的比较分析

笔者从网上下载了五种CAD 系统［A -E］，其中前四种系统(系统A［5］、B［6］、C［7］和D［8］)为国外开发的商业CAD 系统的试用版，系统E［9］是国内开发的免费软件。在Google 搜索引擎下，这些系统通过关键词“Stock Cutting Software”可以找到;系统E 也可通过关键词“下料软件”或“排样软件”找到。选择系统E 的原因有二:一是笔者从网上没有下载到可与前四种系统性能匹敌的国产软件;二是用前述关键词搜索时，系统E 总是出现在搜索结果的最前面几条，也许说明其有一定影响。各系统考虑的优化目标见表3，其中“降低线材成本”是主要目标，其它为次要目标。下面使用本文示例，说明系统的优化功能测试方法。

表3 各种CAD 系统考虑的优化目标

4.1 降低线材成本的实验

令各次要目标取尽可能小的权值，表4 总结出各系统输出的解的特性。可以看出除系统A 的线材成本较高外，其他4 种系统的线材成本接近，所耗线材总长度的差别在0.5 m 以内。系统E 的排样方式数最少，系统C 使用的线材根数最多(平均长度小)。也即在次要目标中，系统E 的解有利于“减少排样方式数”，系统C 的解有利于“减少短材料库存”。

表4 降低线材成本的实验结果

后面关于各次要目标的实验中，只考虑系统C、D和E，因为系统A 和B 不考虑这些目标。

4.2 减少排样方式数的实验

设置后三种系统的次要目标权值，使之优先考虑“减少排样方式数”。实验结果如表5 所示。三个系统输出的排样方式数相近，平均值比表4 中大为减少。除系统C 外，系统D 和E 的线材成本稍有上升。三个系统消耗线材总长度的差别在0.9 m 以内。系统D和E 的解有利于“减少短材料库存”，因为它们使用的线材根数较大。

表5 减少排样方式数的实验结果

4.3 减少短材料库存的实验

设置后三种系统的次要目标权值，使之优先考虑“减少短材料库存”。实验结果如表6 所示。系统D使用102 根线材，最有利于“减少短材料库存”，但其线材成本上升较为明显。很难评价系统C 和E 排样方案的优劣，因为前者消耗线材的总长度比后者少0.6 m，但其排样方式数多出4 个，使用的线材少13根，不利于“减少排样方式数”和“减少短材料库存”。系统E 输出的排样方案如前面图1 所示。

表6 减少短材料库存的实验结果

4.4 集中余料的实验

本文示例由于线材种数多，材料利用比较充分。将示例修正为:16 种毛坯的需求量均为2(毛坯总长度成为38 584 mm)，只能使用长6 000 mm 的一种线材，以说明集中余料的效果。

设置后三种系统的次要目标权值，使之优先考虑“集中余料”。实验结果如表7 所示。三个系统的线材成本相同，材料利用率均为91.87%，系统E 的最后一根余料长度最长。图2 所示为系统E 输出的排样方案，图中文字意义和图1 中相同。

表7 集中余料的实验结果

5 结语

本文根据一维下料的生产实践和对各CAD 系统的分析，阐述了CAD 系统设计与选购时应该考虑的优化目标与工艺约束，供CAD 系统设计者和用户参考。设计者可以根据用户需求，确定系统要考虑的优化目标与工艺约束;用户可以根据自己的生产特点，提取部分有代表性的下料实例数据，通过实验计算，选择最适合的CAD 系统。

［1］Cui Y，Zhao X，Yang Y，et al.A heuristic for the one dimensional cutting stock problem with pattern reduction［J］.Journal of Engineering Manufacture，2008，222:677 -685.

［2］Cherri A C，Arenales M N，Yanasse H H.The one-dimensional cutting stock problem with usable leftover -a heuristic approach［J］.European Journal of Operational Research，2009，196:897 -908.

［3］Cui Y，Yang Y.A heuristic for the one-dimensional cutting stock problem with usable leftover［J］.European Journal of Operational Research，2010，204:245 -250.

［4］郑文，崔耀东，周密.一种基于递归技术的一结下料算法［J］.广西科学院学报，2010，26(4):415 -417.

［5］Pipe Cutting Suite v5.29［OL］.http://www.optimizecutter.com

［6］1D Cutting Optimizerv1.2［OL］.http://www.optimumcut.com

［7］CutLogic 1D v4.4［OL］.http://www.tmachines.com

［8］1D Stock Cutter 2.94［OL］.http://www.astrokettle.com

［9］BarCutE［OL］.http://www.gxnu.edu.cn/Personal/ydcui/html/Soft-Down.htm