中文摘要：

金属制品、通用设备、专用设备、交通运输设备、电气机械及器材等制造行业，经常采用剪切或剪冲下料工艺将金属卷板切成零件毛坯，用于制造各种产品。全国每年卷板消费量约一亿吨，采用优化排样技术提高材料利用率，经济效益较为明显。卷板剪切下料排样问题是指用优化算法生成排样方案，使满足毛坯需求所需卷板的总成本尽可能小。这是一个NP难度问题，其基础算法可为解决许多研究领域的问题提供支持，如切割与填充、布局、生产线平衡、生产计划与调度、库存控制、CAD和CAM等。本项目采用数学规划、递归和分支定界等确定性技术，以及遗传算法等随机性技术，求解多种宽度卷板剪切下料排样问题。研究内容主要涉及有约束排样算法和排样方案生成算法。通过研究形成系统的理论与方法，推动相关学科领域的发展，促进制造行业CAD和CAM应用水平的提高，促进节约型制造的发展，为建设节约型社会做出贡献。

结论摘要：

金属制品、通用设备、专用设备、交通运输设备、电气机械及器材等制造行业，经常采用剪切或剪冲下料工艺将金属卷板切成零件毛坯，用于制造各种产品。全国每年卷板消费量约一亿吨，采用优化排样技术提高材料利用率，经济效益较为明显。卷板剪切下料排样问题是指用优化算法生成排样方案，使满足毛坯需求所需卷板的总成本尽可能小。这是一个NP难度问题，基础算法可为解决许多研究领域的问题提供支持，如切割与填充、布局、生产线平衡、生产计划与调度、库存控制、CAD和CAM等。 本项目适合卷板两阶段下料工艺，第一阶段将卷板切成一种或多种尺寸的平板，第二阶段将平板切成毛坯。采用线性规划、动态规划、递归、分支定界等确定性技术，求解多宽度卷板或普通平板的剪切下料排样问题。首先通过分析，明确多宽度卷板下料问题和平板下料问题之间的转换关系，然后在对平板下料问题的研究中，注意考虑其可扩充用于卷板下料问题的要求。研究内容分为有约束排样算法和排样方案生成算法。对于有约束排样算法，先后研制并在SCI检索期刊上发表了同质条带T形排样方式生成算法、同质条带两段排样方式生成算法、普通条带T形排样方式生成算法、扩展块排样方式生成算法等。对于排样方案生成算法，先后在SCI检索期刊上发表了两种算法余算法和顺序分组法。最后，在已经获得的平板下料成果基础上，在国际顶级和SCI一区期刊上发表一篇讨论多宽度卷板切割下料与购买决策的论文，使得应用该文算法，不但可以提高卷板的下料利用率，还可以通过购买决策，优化卷板宽度组合，进一步降低卷板成本。 本项目成果为本领域提供了系列新思想和方法，为工程优化软件设计的技术创新提供了前提。受本项目资助已培养博士和硕士研究生12名；发表排样研究论文21篇，其中在SCI检索的英文期刊上发表13篇，在EI光盘版检索的期刊上发表3篇。