经济的发展以多种资源为基础,排样问题的工作主要是对材料进行优化利用,在涉及材料分割的行业有广泛的应用,如机械制造、皮革服装、建筑设计、交通运输、航空航天等领域。排样问题的优化目标为布局在单张板材中的毛坯总价值最大。本文研究的是排样生成算法。在实际工业生产中,在进行排样优化步骤中往往会有以下考虑因素：(a)毛坯的需求约束,排入板材中的毛坯数量不能超过需求；(b)不同的排样方式,其板材的排样形成过程、切割方式等均不同。本文就原材料毛坯数量是否有约束,提出两种求解三阶段的排样生成算法。第一种解决无约束三阶段排样问题(UTDC)。毛坯需求无限制,多种毛坯预先生成普通条带,多根普通条带预先拼接成子段,预先生成的子段组合填充整个板材,形成排样方式,上述三个过程各用一个背包算法实现。预先生成的普通条带中,普通条带是由多种类型的毛坯组成,主毛坯为宽度最大的毛坯。因此可能存在多根价值相同,且主毛坯相同,但条带长度不同的情况；或多根条带价值、长度都相同,但主毛坯不同的情况。在价值相同的基础上,多根条带中主毛坯相同的情况下,条带较大的长度被丢弃掉,保留长度最小的条带；在多根条带中长度相同的情况下,条带宽度最窄的条带保留,其余都丢弃,从而减少一阶段中普通条带数量。实验结果表明：普通条带可提高板材的利用率,普通条带的优化大幅减少了条带的数量,比规范长度更加能够提高排样效率,缩短计算时间,尤其在毛坯种类较多时,此优化算法效率更明显,且排样价值也在合理的范围内。第二种算法基于矩形件的三阶段约束排样问题(CTDC),提出基于束搜索的启发式算法优化排样方式,快速生成同质块的三阶段排样方式。采用动态规划确定段的价值。束搜索是一种剪枝的分支定界算法,节点用局部排样方式和余料来表示,对节点的分支,即填充余料。在每一层上选择高潜力的节点作为精英节点做进一步分支,其他节点直接删除不再回溯,这有利于提高算法效率。实验结果表明：算法生成的三阶段排样方式,排样价值高,切割工艺相对简单,且时间相对合理。