下料问题是一种计算复杂度很高的组合优化问题,具有很深的工程应用背景,如机械制造的金属切割、家具业的木材切割、建筑业的玻璃切割、印刷业的排版、化工业的塑料加工、服装业的布料剪裁等都属于此类应用。优化算法可以为下料问题提供合理的排样方案,降低材料成本,简化切割操作,从而降低生产成本,提高企业竞争力。本文以二维剪切下料问题为研究对象,从以消耗的板材数量最少为目标的三阶段同质(3H)排样方案开始,扩展到考虑余料标准化的排样方案,最后研究了考虑余料标准化的余料下料问题。达到板材用量最少的同时,提高余料的二次利用价值和可用性。并在后继生产周期中合理优先使用余料,进一步减少板材用量和材料浪费,减少废料对环境的污染。本文从以下三个方面研究二维剪切下料问题,主要的工作和创新点包括:(1)针对普通的二维剪切下料问题,采用迭代顺序价值修正算法,迭代生成多个3H排样方案,从中选择板材用量最少者作为剪切下料问题的解。将排样方案分解成多个3H排样方式的顺序求解。采用递推过程快速生成排样方式,通过毛坯初始价值调整、排样方式毛坯价值修正和代际价值修正,改变毛坯在排样过程中的优先顺序,引导不同种类毛坯在不同排样方式中均衡分布。多个系列、大量算例的实验结果表明,迭代顺序价值修正算法特别适用于中大规模的应用场合,生成的三阶段排样方案优于文献算法和商业软件的同类三阶段排样方案,其效果不仅体现在节省板材用量和节省计算时间上,而且体现在剪切切割操作的简化上。(2)针对考虑余料标准化的二维剪切下料问题,采用基于束搜索的余料聚集算法,将余料汇集于板材的右侧,形成与板材同宽的标准余料。束搜索节点的评价算子包含已填充子板的局部排样方式价值、剩余子板的估计价值或余料的二次利用价值,以递推生成的初始排样方式作为过滤器删除部分差节点。实验结果表明,束搜索算法可以快速聚集余料碎片形成大的标准余料,生成的3HL排样方式在毛坯价值上比其他启发式算法生成的同类排样方式高。而在相同毛坯价值下,3HL排样方式与文献中的其他剪切排样方式相比,废料碎片少,可用标准余料的面积更大,有利于余料的管理和使用。(3)针对考虑余料标准化的余料下料问题,阐述两种启发式算法:ISVCL算法和ISVC-BS算法。ISVCL算法以材料成本(板材总面积-余料总面积)最少为目标,在迭代顺序价值修正算法的基础上增加了标准余料生成和优先使用。ISVC-BS算法结合了迭代顺序价值修正算法和束搜索算法,先通过束搜索算法试排样部分毛坯,再利用迭代顺序价值修正算法搜索剩余毛坯的板材用量最少排样方案,并由束搜索算法对材料利用率低的排样方式进行余料聚集。按最大板长生成虚拟排样方式,按性价比最高的原则选择排样方式。通过设置余料的使用系数,使余料比板材具有更高的使用优先权。单周期的实验结果表明,两种启发式算法在生成标准可用余料的同时,排样方案的板材用量并没有增加。ISVC-BS算法达到最少板材用量的迭代次数比ISVCL算法要少,相同迭代次数下生成的标准余料更大。多周期的实验结果表明,ISVC-BS算法可有效用于余料下料问题,将标准余料用于后继生产周期,减少板材的用量,降低长期生产成本。