论文部分内容阅读
矩形件排样优化通常是指在一定数量的长和宽给定的板材上,尽可能多地排放所需要的矩形件,从而使得所需要的板材尽可能地少,以达到节省材料的目的。这项工作广泛用于机械制造、轻工、家具以及玻璃切割等行业。对于非矩形件的不规则装配件排样问题,也可以通过计算机的图形处理技术转化为矩形件的排样问题。矩形件排样优化问题实际上是一个十分困难的问题,从数学计算复杂性理论看,它属于具有最高计算复杂性的一类问题:NP完全问题。按是否允许在同一张板材中排入多种尺寸的毛坯,把相应的排样方式称为套裁排样方式或单一排样方式。套裁排样方式有利于提高材料利用率,但由于单一排样方式的切割工艺简单、排样过程易于管理,往往更容易为用户所接受。目前,矩形毛坯单一排样的常用算法主要有动态规划算法、分支定界算法、连分数算法、多项式时间算法。算法的实现难易程度由动态规划算法到多项式算法依次提高。动态规划算法以其简单容易实现而经常使用,而且在计算中比其它的算法具有一定的优势。在生产实践中,企业所购入的板材长度可能超过剪床所能切割的最大长度,排样时必须先将长板用平行于宽边方向的切割线分割成多张子板,每张子板的长度均小于等于刀刃长度;然后,在各张子板上切出毛坯。在这里我们把这个问题称为刀刃长度受限问题。已经提出的动态规划算法要求刀刃长度不小于板材长度,否则就有可能生成不能切割的排样方式,因而不能有效地解决上述问题。本文致力于从实现的角度改进动态规划算法来解决刀刃长度受限的问题。另外已经提出的动态规划算法实际上解决的是无约束排样问题,即如何在单张板材上生成尽可能多的毛坯。在实际生产中,毛坯需求总是有限的。因此,有必要进行有约束排样。即在满足毛坯需求量的情况下所使用的板材面积最少。本文从实现的角度阐述了如何对动态规划算法进行改进以进行有约束排样。另外,本文还讨论了如何把单一排样优化算法应用于库存优化决策中。市面上有多种尺寸的板材可供选择,本文讨论了如何把采用了动态规划算法与库存成本计算相结合来提高库存决策的科学性。当企业从市场上购买不到合适尺寸的板材时,可以考虑在向板材生产厂家支付一笔定尺费用的情况下,直接向生产厂家订制板材。本文讨论了如何利用动态规划算法优化决策。