板材下料问题

1、材下料问题Prepared on 22 November 2020板材玻璃的下料问题摘要下料问题（cutting stock problem）就是指在给定板材宽度和长度的情况下，如何 将具有一定种类和数量的矩形件排放到板材上，使所需的板材数量最少的问题.该问题 广泛存在于工业生产中。本文运用优化理论，建立了矩形件优化排样数学模型，并提出 了基于启发式算法的一刀切约束条件下二维板材下料算法。关键词下料二维下料问题优化启发式算法矩形件排样一刀切一、问题的重述在大型建筑工程中.需要大量使用玻璃材料，如门窗等。在作材料预算时，需要求 出原材料的张数。已知板材玻璃原材料和下料后的成品均为矩形。由于玻璃材

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

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

4、率。三、模型的假设（-）切割玻璃时，刀具只能走直线，且中间不能拐弯或者停顿（-）矩形件允许任意摆放（三）要求加工矩形件无顺序（四）切割矩形件时长和宽要与原材料的长和宽平行（五）不考虑切割时的产生的损耗（六）矩形件不能重叠，不超过原材料的大小四、符号的说明符号表乔意义规格为2100cmx 1650cm的原材料的长规格为2100cmx 1650cm的原材料的宽规格为2000cmx 1500cm的原材料的长规格为2000cmx 1500cm的原材料的宽矩形件的长，i=l, 2,26矩形件的宽，匸1, 2,26矩形件的数量，上1, 2,26所需原材料的块数有两种规格原材料是，所需规格为2100cmxl

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

6、的原材料利用率，符合实际生产过程的要求。 一种原材料规格下的二维下料算法本问题属于NP完全问题，有现有理论知P完全问题问题具有以下的性质：任何P完全问题都不能用任何已知的多项式算法求解；(2) 若任何一个P完全问题具有多项式算法，则一切P完全问题都有多项式算法。基于 上述理论通过查阅资料知该问题是属于离散优化问题，归为背包问题一类，背包算法的 特点是算法简单，但只是针对数量较多，种类较少的矩形件排样，当矩形件的尺寸差异 较大时，并不适合采用该算法。所以我们采用启发式算法。521优化排样本文利用计算机模拟，采用优化排样的方法，对所有矩形件进行排样，算出最少的原 材料张数。在矩形件优化排样中待排矩

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

8、来决定横排或竖排。沿长度方向横排沿长度方向纵排沿宽度方向横排沿宽度方向纵排5. 2. 2问题一的数学模型设板材长为L,宽为W,且LW,板材数量不记。第k种矩形件的长为厶，宽为陷数量为面积为s(lWiWk),所需要的板材总数为则优化的目标函数为厶匚工s”Ar = min() = min(-),同时每张板材的利用率也要符合工业生产的要LfrLfr求。5.2. 3模型的求解我们借肋于计算机模拟排样过程，求解出所需的最小张数，模拟过程如下：(-) 将所有的矩形件按从大到小排列并保存，从中找出一个未排的面积最大的 矩形件，放在已知板材的左下角。(二) 确定排放方式：按照沿宽度方向排列横排和纵排的原则。设

9、置一下四个参 数：A二mod (附 厶)B二mod 他 匚)C=floor （W,厶）D二 floor （W, 7）分为一下四种情况：（1）CN1, DM1此时矩形件横排纵排均可，接着看怎么样排剩余边界 距离小，如果BA,同时L心则说明沿着宽度方向纵排剩余边界 面积小于沿着宽度方向横排，所以采用纵排，反之横排。（2）CM1, Dw,则采用纵排（3）CV1, DM1 L厶则采用横排（4）CV1, Dsum(A(:,3)0) z=l;SIZE(1, :) = ；endif isempty(SIZE) = 1 break;endif sum (A ( : z 3) ) =0 break;endb=p

10、aixu(Afz);x=xingzhuang(SIZE(1,1)rSIZE(lf 2)z b); if x=0P=P,x;S=S+b *b(2);for i=l:length(A)if A(i,l)=b(l)&A(iz2)=b(2) A(iz3)=A(ir3)-1； z=l;break;endendSIZE1=pailie(b,SIZE(lr :),x);SIZEd, :) = ；SIZE=SIZE;SIZE1；elsez=z+l;endendQ=Q+sum(P0); paper=paper+l;SIZE=L1,W1;V=V,S/(L1*W1);P=J;s=o；endvpaper问题二的主程序

11、源代码clcz clear;Ll=2100;Wl=1650;L2=2000;W2=1500;paper=0;SIZE=L2zW2;U=l;P=；V=；S=0;z = l；Q=0；A=865 85798857 715 98 ;804 746 196;857 675 28 ;857 665 28804 663 224;804 661 308;804 639 84 ;804536196;804535392;804551392;86544698 ;762446196;71544698 ;680446224;67544628 ;66744628 ;65544684 ;64744656 ;66742630

12、8;580446224;552446196;551446392;527426392;while sum(A(:z 3)=0while isempty(SIZE) = 0if zsum(A(:,3)0)Z = l；SIZE(lz ：) = ；endif isempty(SIZE) = 1break;endif sum(A(:z 3)=0break;endb=paixu(A,z); x=xingzhuang(SIZE(lz1),SIZE(lz 2)zb); if x=0P=P,x；S=S+b(l)*b(2);for i=l:length(A)if A(i, l)=b(l )& A(i,2)=b(2)A(i,3)=A(i,3)-l;z=l；break;endendS