板材下料问题

《板材下料问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、板材玻璃的下料问题摘要“下料问题（cuttingstockproblem）”就是指在给定板材宽度和长度的情况下，如何将具有一定种类和数量的矩形件排放到板材上，使所需的板材数量最少的问题，该问题广泛存在于工业生产中。本文运用优化理论，建立了矩形件优化排样数学模型，并提出了基于启发式算法的一刀切约束条件下二维板材下料算法。关键词下料二维下料问题优化启发式算法矩形件排样一刀切问题的重述在大型建筑工程中，需要大量使用玻璃材料，如门窗等。在作材料预算时，需要求出原材料的张数。已知板材玻璃原材料和下料后的成品均为矩形。由于玻璃材料的特点，切割玻璃时，刀具只能走直线，且中间不能拐弯或者停顿，即每

2、切一刀均将玻璃板一分为二。切割次序和方法的不同、各种规格搭配（即下料策略）不同，材料的消耗将不同。工程实际需要解决如下问题，在给定一组材料规格尺寸后：（1）在原材料只有一种规格的情况下（例如长为2100cm,宽为1650cm）,给出最优下料策略，此时所需要材料张数最小。（2）在原材料为两种规格的情况下（例如2100cm1650cm和2000cmX1500cm），给出最优下料策略，使所需材料的张数最小，且利用率（实际使用总面积与原材料总面积之比）尽量高。（3）下表是一些成品料及所需块数（长X宽X块数）分别以一种原材料2100cmX1650cm及两种原材料规格2100cmX1650cm

3、,2000cmX1500cm为例，分别给出（1）和（2）的算法及数字结果，并给出两种情况下的利用率。二、问题的分析本问题属于二维下料问题，该问题已被证明为是NP完全问题。由于任何NP完全问题都不能用任何已知的多项式算法求解，所以我们建立一个排样的算法模型。由题目要求该算法首先要满足生产工艺，即要满足“一刀切”，即从板材的一端，沿直线方向切割到另一端。其次下料方案应该使原材料的利用率大，从而降低生产成本，提高经济效益。再次应该使用最少的下料方式，可以节省在生产过程因转换下料方式而产生的时间和费用的浪费，提高生产效率。三、模型的假设切割玻璃时，刀具只能走直线，且中间不能拐弯或者停顿矩形

4、件允许任意摆放要求加工矩形件无顺序（四）切割矩形件时长和宽要与原材料的长和宽平行（五）不考虑切割时的产生的损耗（六）矩形件不能重叠，不超过原材料的大小四、符号的说明符号表示意义规格为2100cmK1650cm的原材料的长规格为2100cmK1650cm的原材料的宽规格为2000cmx1500cm的原材料的长规格为2000cmx1500cm的原材料的宽矩形件的长，i=1,2,……,26矩形件的宽，i=1,2,……,26矩形件的数量，i=1,2,……,26所需原材料的块数有两种规格原材料是，所需规格为2100cmX1650cm原材料的块数有两种规格原材料是，所需规格为2000cmX15

5、00cm原材料的块数只有一种原材料的利用率后两种原材料的利用率表示第一块板材的使用数量指在消耗第一块料板的数量为ki=i时，所生产的第j种产品的数量指所需生产的第j种商品的总量0所需的第二块板的数量所需要的第i块板的总数量五、模型的建立与求解5.1综述从理论上看，该类问题属于具有最高计算复杂性的优化计算问题即NPI全问题。对于这类问题，以目前已成熟的计算理论和算法，或者根本无法求解，或者求解的计算量是爆炸性的。本文从现有算法中，总过比较分析，找到一种基于优化排列的启发式算法。通过实际排列和比对，可以达到较高的原材料利用率，符合实际生产过程的要求。5.1一种原材料规格下的二维下料算法

6、本问题属于N琉全问题，有现有理论知NFPI全问题问题具有以下的性质：(1)任何N矣全问题都不能用任何已知的多项式算法求解；(2)若任何一个N酷全问题具有多项式算法，则一切NPI全问题都有多项式算法。基于上述理论通过查阅资料知该问题是属于离散优化问题，归为背包问题一类，背包算法的特点是算法简单，但只是针对数量较多，种类较少的矩形件排样，当矩形件的尺寸差异较大时，并不适合采用该算法。所以我们采用启发式算法。5.2.1优化排样本文利用计算机模拟，采用优化排样的方法，对所有矩形件进行排样，算出最少的原材料张数。在矩形件优化排样中，待排矩形件的排列先后顺序、矩形件与矩形件之间的排放方式以及矩

7、形件与板材之间的相对排放位置都是十分重要的。本排样算法应用的相应规则如下：(1)排列先后规则：通过比较待排矩形件的面积来建立定序规则，即根据待排矩形件的面积递减的顺序进行排样，它对最终排样结果有着重要的影响。(2)定位规则：确定被选待排矩形件在布局空间中的摆放位置。本算法采用的是占角策略，即将待排矩形件摆放在板材的某一角，采用的是先占左下脚的定位规则。(3)排布规则：矩形件在板材上有沿板材长度方向的横排和竖排、沿板材宽度方向的横排和竖排共4种方式，如图。本算法采用沿宽