约束二维排样问题的一种求解算法

讨论有约束二维切割排样问题,即将板材切割成若干种矩形毛坯,其中每种毛坯的数量有上界约束,优化目标以使板材所切割的毛坯总价值(排样价值)最大。采用五块排样方式简化切割工艺,将板材切割成五块,每块切割成所需毛坯。构造一种基于隐式枚举和分支定界思想的算法生成五块排样方式:(1)计算所有可能尺寸的块的排样价值;(2)选择排样价值最大的五块组合生成五块排样方式;(3)采用文献中的基准测题,验证文中的有约束五块排样算法。研究结果表明,文中算法平均排样价值比文献中的3种算法分别高出12.85%,4.52%和1.89%,且算法计算时间较短。     

矩形件二维下料问题的一种求解方法

求解矩形件二维下料问题,即解决如何用最少的板材切割出所需的全部矩形毛坯。提出一种切割工艺简单的新型排样方式即单毛坯条带四块排样方式。首先采用经典背包算法生成排样方式,然后采用基于列生成的线性规划算法迭代调用上述排样方式生成算法求解下料方案。将文中排样方式分别与文献中经典两阶段和经典两段排样方式进行比较,实验计算结果表明,四块排样方式排样价值高于以上两种排样方式。最后通过实际下料求解,证明了使用该算法的材料利用率较高。     

单一尺寸矩形毛坯下料问题的一种确定性算法

针对单一尺寸矩形毛坯下料问题,讨论了如何用最少的库存板材切割出一定数量的单一尺寸矩形毛坯。提出1种切割工艺简单的5块排样方式,该排样方式将板材划分成5块区域,每块区域中矩形毛坯按照相同方向排列。设计了1种确定性算法求解下料方案,首先构造1种基于隐式枚举思想的算法确定整张板上的最优5块排样方式;然后对该算法进行扩展,使其能够求解部分板上的最优5块排样方式。采用算例将文中下料算法和文献中递归下料算法、拼合下料算法进行比较,数值模拟分析结果表明,文中的下料算法在切割工艺和板材利用率两方面均较为有效。     

矩形件五级剪切排样方式的一种生成算法

针对钣金件二维切割排样问题,提出一种满足剪切要求的五级排样方式及其生成算法。这种排样方式将板材划分为5个级,每级中只排放同种矩形件。首先,确定所有可能尺寸的级中矩形件的最优布局方式和级的最大排样价值;然后,采用隐式枚举技术考察板材的所有可能的5级划分,选择排样价值最大的一个作为最终解。采用文献中的基准例题将本文算法与文献算法进行比较,数值实验结果表明本文算法具有如下优势:排样价值高于两段排样算法、四块排样算法、三阶段排样算法、匀质条带三块排样算法和复合条带三阶段排样算法;生成的排样方式切割工艺比较简单;算法计算时间较短,可以满足实际应用需要。     

匀质条带五块布局方式及其生成算法

针对矩形毛坯无约束二维布局问题,提出一种匀质条带五块布局方式。这种布局方式将板材划分为5个矩形块,每个块由包含同种毛坯的匀质条带组成。构造五块布局方式的生成算法:首先采用动态规划方法生成所有可能尺寸的块中匀质条带的最优布局;然后采用隐式枚举和分支定界技术考察板材所有可能的五块划分方式,按照板材布局价值最大原则确定板材的最优五块划分,得到最终的五块布局方式图。数值实验结果表明,这种算法能有效地提高板材布局价值。     

复合条带三阶段排样方式的生成算法

提出复合条带三阶段排样方式用以解决无约束二维剪切排样问题。该排样方式用3个阶段将板材切割成毛坯,首先用水平刀具将板材切成复合条带,然后用竖直刀具将复合条带切成初始毛坯,最后用水平刀具将初始毛坯切成具有精确尺寸的毛坯。采用背包算法生成该种排样方式,该算法求解两个背包模型分别生成条带在板材中的布局和毛坯在复合条带中的布局。采用文献中基准测题,将文中排样方式与文献中5种重要的排样方式进行比较。实验结果表明,文中复合条带三阶段排样方式平均排样价值高于以上5种排样方式,且切割工艺比较简单。     

基于顺序价值修正算法的矩形件二维优化下料

针对矩形件二维下料问题,提出一种顺序价值修正下料算法。构造了四块排样算法,生成矩形件数量有上界约束的四块排样方式;这种排样方式将板材划分为4个块,每个块包含方向相同的条带,每条条带包含同种矩形件。采用顺序启发式算法调用上述四块排样算法逐个生成排样方式,按照不产生多余矩形件原则,确定每个排样方式的最大使用次数;在生成每个排样方式后修正该种排样方式中矩形件的价值。将上述顺序启发式算法迭代执行多次,生成多个下料方案,选择板材使用张数最小的一个作为最终解。采用文献例题进行计算比较,数值实验结果表明本文算法比文献算法更能节省板材。     

一种分阶段式匀质块最优矩形件排样方法

在生成排样图案时,应同时考虑材料利用率和切割过程的复杂性。提出了一种用于生成矩形件剪切割方式的分阶段式排样方案的算法。它仅允许一种尺寸的毛坯出现在匀质块中,从而简化了切割过程。该算法采用隐式枚举算法和动态规划来确定最佳优化排样方案,以使材料利用率达到最大。通过文献中的测题,将该算法与普通T形排样方式算法、普通两段排样方式算法和复合条带两段排样方式算法进行比较。实验结果表明:在所有测题中,本文算法的材料利用率均高于以上3种算法;本文算法解决二维无约束剪切排样问题的平均计算时间为0.363 s,计算时间合理。     

矩形件剪切下料问题的一种顺序价值修正算法

针对矩形件剪切下料问题,提出一种基于顺序价值修正策略的优化下料算法。首先构造普通块排样方式的生成算法,生成矩形件在单张板材上的排样方式。然后采用顺序价值修正算法,调用上述排样算法,逐个生成排样方式,每个排样方式满足部分矩形件的需求量,直到所有矩形件的需求量均被满足为止,在生成每个排样方式后按照一定规则修正这个排样方式中矩形件的价值。最后将上述顺序价值修正算法迭代执行多次得到多个下料方案,选择耗费板材张数最少的作为最终解。使用基准例题将本文算法与两种文献算法进行对比实验,结果表明,本文算法在节省板材方面优于两种文献算法,且计算时间合理。     

应用递归划分策略解决矩形件剪切排样问题

针对机械制造领域的矩形件剪切排样问题,提出一种基于递归划分思想的排样算法。用两条互相垂直呈T型的剪切线将板材划分为3个子板,称板材的左下角子板为排样块,称其余两个子板为递归块。对于排样块,按照简单方式排放矩形件;对于递归块,将其看做板材继续划分。用隐式枚举算法确定排样块的最优排样方式,得到块中排放的最优矩形件种类和矩形件的行列数;用分支定界算法确定递归块是否继续划分。采用基准例题将本文算法与文献算法进行对比,实验结果表明,本文算法排样价值高于文献算法,且计算时间能满足实际应用需要。     

面向可加工性的卷材优化下料方法

针对成品为矩形件的卷材优化下料问题,综合考虑材料利用率高和便于加工,将顺序价值修正算法与剪切排样方式生成算法结合,确定下料方案。第1阶段,将卷材纵剪为长条带(子卷),每根条带含同一种矩形件;第2阶段,将条带冲剪出矩形件。剪切排样方式生成算法通过递推生成排样方式。每次生成排样方式后,均对矩形件进行一次价值修正,使其价值接近理想值。每个排样方式满足部分矩形件需求,重复此过程,直到满足所有矩形件需求为止。通过迭代生成不同下料方案,选择材料利用率最高的作为解。与文献算法比较,可知该算法在有效提高材料利用率的同时,可以简化切割加工工艺。     

基于均匀条带排样方式的二维下料启发式算法

条带结构排样方式在机械制造业下料领域有广泛的应用。针对矩形件二维下料问题,提出一种基于均匀条带排样方式的启发式下料算法。下料方案包含多个排样方式,每个排样方式满足部分矩形件的需求量。首先构造均匀条带四块排样方式的约束排样算法;然后采用列生成法反复调用上述约束排样算法生成各个排样方式,直到所有矩形件需求量得到满足为止。采用文献中的基准例题,将本文下料算法和文献中下料算法进行比较,数值实验结果表明本文下料算法能有效地提高板材利用率,且计算时间能满足实际应用要求。     

矩形毛坯工艺定额的制定

讨论金属板材矩形毛坯剪切下料材料工艺定额的制定问题。对Agrawal提出的单一尺寸矩形毛坯最优化排样方法进行扩展 ,使之适用于解决任意数量矩形毛坯的材料工艺定额制定问题。所述方法可以给出最为先进合理的材料工艺定额。举例说明本文所述定额制定系统的优越性。     

矩形毛坯工艺定额的制定

讨论金属板材矩形毛坯剪切下料材料工艺定额的制定问题。对Ａｇｒａｗｌａ提出的单一尺寸矩形毛坯最优化排样方法进行扩展，使之适用于解决任意数量矩形毛坯的材料工艺定额制定问题。所述方法可以给出最为先进合理的材料工艺定额。举例说明本文所述定额制定系统的优越性。     

基于普通块的四块排样方式及其生成算法

针对矩形件无约束二维剪切排样问题,提出普通块四块排样方式及其生成算法。这种排样方式首先将板材划分成4个普通块,然后将普通块切成条带,最后将条带切成所需要的矩形件。普通块由条带组成,每刀在普通块上仅切下一根条带,连续被切下的两根条带的方向互相平行或垂直。首先采用背包算法确定条带中矩形件的最优布局,然后采用递推算法确定普通块中条带的最优布局,最后采用隐式枚举法确定板材的最优四块划分。采用2组文献例题将本文算法与文献算法进行比较,实验结果表明,本文算法排样价值高于4种文献算法。     

约束剪切问题的三块排样方式及其生成算法

讨论了矩形件有约束剪切排样问题,即在一张板材上剪切下若干种已知尺寸和价值的矩形件,约束每种矩形件允许剪切的数量不能超过其需求量,优化目标为使板材剪切出的矩形件总价值最大。提出了一种三块排样方式及其生成算法。这种算法用两条互相垂直的剪切线将板材分成3个块;对于每个块,排放一个矩形件在其左下角,将其剩余部分划分为2个子块;将子块看作块继续递归排样,直到其无法再容纳矩形件为止。采用基准例题将本文算法与文献算法进行实验对比,结果表明本文算法排样价值比4种文献算法分别高0. 35%,0. 31%,0. 19%和0. 37%,且计算时间可满足实际应用需要。     

基于两阶段排样方式的卷材下料算法研究

讨论矩形件卷材下料问题,采用切割工艺简单的两阶段排样方式采进行下料。这种排样方式采用一组平行于卷材宽度方向的剪切线将卷材切割成多个条带,然后将每个条带切割成所需要的矩形件。首先,构造一种有界背包算法确定矩形件在条带中的优化布局;然后,采用基于列生成的线性规划算法调用上述有界背包算法生成排样方式;最后,采用顺序启发式算法,用当前矩形件剩余需求量反复调用线性规划算法生成各个排样方式,直至每种矩形件剩余需求量均为零,组合各个排样方式形成下料方案。将本文算法与2种文献算法进行比较,计算结果表明,本文算法下料方案比2种文献算法分别节省1.97%和1.66%的卷材。     

冲压条带二维优化排样问题的一种启发式算法

针对条带在板材中的优化排样问题,提出一种启发式算法。这种启发式算法的基本思想是每刀从板材上剪切下一根水平或竖直条带,直至板材被剪切完,并且在每次剪切时按照板材排样价值最大原则确定条带的方向和宽度。首先,计算所有可能尺寸的条带的价值,按照条带价值最大原则确定条带中零件的最优布局。然后,采用动态规划原理按照从小到大顺序依次生成板材上的条带优化排样方式。采用文献中的基准例题,将本文算法与多段排样算法、三块排样算法和四块排样算法进行比较,数值实验结果表明本文算法排样价值更高,并且计算时间可满足实际应用的需要。     

条带上圆形件的优化排样

针对圆形件下料问题,从条带的利用率角度讨论了板材上圆形件的排样问题。条带上圆形件的排样一般有3种排法:并排、品排和基于品排的斜排。由于基于品排的斜排极大地减小了相邻圆形件之间和板材边界与圆形件之间的空隙,因此被认为是最好的排样法。从理论分析、数据模拟和实例计算3个方面出发,具体分析了上述3种排法的优劣,旨在得出已知毛坯规格及数量时,采用何种排样方式排入毛坯。结果显示:基于品排的斜排在绝大多数情况下,材料利用率都优于其他两种方法,且3排斜排优于2排斜排;但从实际角度出发,当某块板材排入的需求毛坯数不大于10时,应采用并排法排入毛坯,当需求毛坯数大于10时,应采用3排品排法排入毛坯。     

圆形片剪冲下料问题的一种求解算法

求解圆形片剪冲下料问题,即解决如何用最少的板材切割出所需的全部圆形片毛坯。本文提出一种生成圆形片条带四块下料方案的确定型算法。首先采用动态规划技术生成排样方式,然后采用基于列生成的线性规划技术迭代调用排样方式生成算法生成下料方案。采用测题将本算法与直切下料算法与T型下料算法进行比较,研究结果表明,本算法生成的下料利用率高于以上两种经典算法。最后通过一个下料实例的解表明:所提出的算法在计算时间和下料利用率两方面都有效。