基于两段方式的圆形片约束排样算法

讨论圆形片约束排样问题,提出一种两段排样方式生成算法。两段排样方式用一条分界线将板材划分为两个段,每个段由相同长度和方向的条料组成,每根条料排放同种圆形片。首先确定所有可能尺寸的条料中圆形片的排样方式;然后采用背包算法,生成所有可能尺寸的段中条料的排样方式;最后依据板材排样价值最大原则,确定段的分界线位置,得到整张板材上圆形片的两段排样方式。将本文算法和文献算法进行比较,数值实验结果表明,本文算法排样价值高于文献算法。

基于束搜索的三阶段约束排样算法

基于矩形件三阶段约束排样问题(CTDC),提出基于束搜索的启发式算法优化排样方式、以快速生成同质块三阶段排样方式。采用动态规划确定段的价值。束搜索是一种剪枝的分支定界算法,节点用局部排样方式和余料来表示,对节点的分支,即填充余料。在每一层上选择高潜力的节点作为精英节点做进一步分支,其他节点直接删除不再回溯,这有利于提高算法效率。实验结果表明:算法生成的三阶段排样方式,排样价值高,切割工艺相对简单,且时间相对合理。

生成矩形毛坯最优两段排样方式的确定型算法

排样价值、切割工艺和计算时间是排样问题主要考虑的3个因素.文中提出一个新的基于排样模式的确定型排样算法——同质块两段排样算法,此算法适合剪冲下料工艺,在实现工艺简化的同时提高了排样价值时间比.首先通过动态规划算法生成最优同质块,然后求解一维背包问题生成块在级中的最优排样方式和级在段中的最优排样方式,最后选择两个段生成最优的两段排样方式.通过3组经典测题对该文算法进行了测试,将算法与4种著名算法进行了比较.实验结果表明,该文算法的优化结果好于以上4种著名算法,有效地提高了板材利用率,并且计算时间合理.

对Agrawal单一矩形排样算法的改进与扩展

讨论单一矩形剪切下料排样方式最优设计问题 ,给出更为贴切的上界 ,从而改进 Agrawal算法 .Agrawal以图解方式说明规范多级排样方式中包含最优剪切割方式 ,现给出这一结论的数学证明 .

基于两段排样方式的矩形件优化下料算法

针对矩形件下料问题,提出一种基于两段排样方式的优化下料算法。首先构造一种约束排样算法,生成矩形件在板材上的两段排样方式。然后采用列生成算法依据矩形件剩余需求量迭代调用上述约束排样算法生成一个虚拟下料方案,按照不产生多余矩形件原则选取虚拟下料方案中的部分排样方式加入到实际下料方案中,更新矩形件剩余需求量;重复上述步骤直到矩形件剩余需求量为零。采用文献中基准例题将该算法与2种文献算法进行比较,数值实验结果表明该算法下料利用率比2种文献算法分别高1.61%和0.78%。

复合匀质块排样方式及其生成算法

为解决大规模矩形件无约束二维剪切排样问题,提出一种复合匀质块排样方式及其生成算法。用一条水平分界线将板材划分为上下两段,每段包括若干个由左到右水平排列的匀质块。采用文献算法生成匀质块,采用动态规划算法将匀质块组合成段,通过枚举法确定最优水平分界线的位置。采用3组基准例题对算法进行测试,实验结果表明,该算法能够有效提高材料利用率。

有约束单一尺寸矩形毛坯下料问题的一种求解算法

讨论有约束单一尺寸矩形毛坯下料问题:切割库存板材满足一定数量的单一尺寸矩形毛坯的需求,优化目标是使所切割的板材总面积最小,该问题广泛的出现在制造业领域的板材切割下料环节。提出一种基于五块布局模式的优化下料算法。首先调用无约束五块布局算法生成整张板材上的毛坯排样方式,然后调用有约束五块布局算法生成部分板上的毛坯排样方式。使用算例对文中下料算法进行了测试,并与文献中下料算法进行了比较。实验结果表明,下料算法可以提高下料利用率,而且计算时间合理。

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

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

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

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

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

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

矩形件简单块占角排样方式的动态规划

目的针对矩形件无约束2维剪切排样问题,提出一种可简化板材切割工艺的简单块占角排样方式,并构造这种排样方式的动态规划生成算法。方法该排样方式在板材左下角按照简单块方式排样若干行若干列同种矩形件,将板材剩余部分划分为两个子板;将子板按照上述方法继续递归排样和划分,直至子板排满矩形件为止。采用动态规划确定所有可能尺寸的板材左下角排样的最优矩形件、矩形件的最优行列数和板材剩余部分的最优子板划分。运用规范尺寸排除不必要的计算。结果将本文算法与目前常见的算法进行比较,实验结果表明本文算法计算时间合理,排样价值较高。在第1组41道基准例题中,本文算法所有例题均求出了精确解,同质块T型算法、同质块两段算法和复合条带两段算法分别有7道、5道和4道例题未求出精确解。在第2组20道基准例题中,本文算法只有1道例题未求出精确解,普通三阶段算法、同质块T型算法、同质块两段算法和匀质条带三块算法分别有18道、15道、15道和20道例题未求出精确解。在第3组50道随机例题中,本文算法、普通两段算法和同质块两段算法板材利用率分别为99.9137%、99.8623%和99.7961%。在第4组31道基准例题中,本文算法所有例题均求出了精确解,普通占角排样算法有2道例题未求出精确解。结论本文算法计算时间远小于精确算法,优化效果接近精确算法;本文算法计算时间与多种启发式算法接近,但优化效果好于多种启发式算法。