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

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

矩形件单一排样问题的一种精确算法

针对机械制造业领域的矩形件单一排样问题,即在长宽为L、W的板材里排放最多个数的长宽为l、w的矩形件,提出一种基于整数规划和约束规划的精确排样算法。首先在板材上刻画W+1条等距的水平基线;然后建立单一排样问题的整数规划数学模型,求解出最优排样方案所对应的每条基线上排放的水平矩形件和竖直矩形件个数;最后采用约束规划模型求解出每个矩形件在基线上的具体排放坐标,画出最优排样方案图。将本文算法与文献中的单一排样算法进行比较,结果表明,本文算法求得的板材排样方案中可以排放更多的矩形件,板材利用率更高。     

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

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

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

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

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

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

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

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

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

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

可减少排样方式数的二维下料顺序启发式算法

讨论矩形件二维下料问题，将板材成本最小作为主要优化目标，将排样方式数最少作为辅助优化目标。提出一种可减少排样方式数的下料算法。该算法基于顺序启发式框架，按顺序逐个产生排样方式满足剩余矩形件的部分需求量，直到矩形件的所有需求量均得到满足为止。它采用一种分组技术选择可用来生成下一个排样方式的矩形件，用这些矩形件生成下一个排样方式后根据顺序价值校正方法调整矩形件的价值，其中每个排样方式均采用动态规划程序生成。将本文下料算法与两种文献算法进行对比，实验结果表明，本文下料算法使用的板材面积比文献算法分别节省了1.12%和0.89%,排样方式数比文献算法分别减少了45.56%和30.79%,且计算时间与文献算法接近。     

基于T型布局方式的异构矩形件下料算法

讨论异构矩形件下料问题,提出一种基于T型布局方式的优化下料算法。首先构造一种约束布局算法,生成矩形件在单张板材上的T型布局方式,然后采用列生成算法,依据当前矩形件剩余需求量,迭代调用上述约束布局算法,生成一个虚拟下料方案,按照不产生多余矩形件原则,选取虚拟下料方案中的部分布局方式加入到实际下料方案中,更新当前矩形件剩余需求量,重复上述步骤,直到矩形件剩余需求量为零。采用文献中基准例题将本文算法与3种文献中算法进行比较,数值实验结果表明,本文算法比3种文献中算法分别节省3.93%,1.27%和1.17%的板材。     

混合遗传算法在矩形件优化排样中的应用

二维排样是典型的组合优化问题。通过综合遗传算法和模拟退火算法思想,提出一种适宜于大批量、多种类的矩形件排样的混合遗传算法,并结合基于局部板材利用率最高的填充算法不断填充板材,获得近似总体最优的排样结果。运用此算法,作者开发了实用的排样软件,并给出了计算实例,结果表明该算法是一种行之有效的方法。     

圆形件卷材排样问题的启发式优化算法

圆形件卷材排样问题是将一组不同尺寸的圆形件排样在宽度指定的卷材上,使得占据的卷材长度最小。针对该问题提出一种基于先定序后定位思想的启发式优化排样算法,构建了圆形件卷材排样问题的数学模型,计算了待排样圆形件在当前布局的所有可行放置位置的优度指标,选择优度指标最高的位置放置圆形件,并通过对圆形件排放序列进行变换,得到多种不同的排样方案,选择耗费卷材长度最小的排样方案作为最终解。构造了半径非递增、首圆形件置换和子序列划分3种算法,并利用文献中的例题,比较了3种算法和文献算法排样的计算时间和卷材使用长度。实验结果表明:本文算法生成的排样方案耗费的卷材长度较小,且算法计算时间比较合理;子序列划分算法的求解质量最好,能较好地使大小圆形件在卷材中均匀分布。     

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

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

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

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

矩形毛坯五块切割排样方式的生成算法

材料利用率和切割工艺复杂度是金属板材切割排样中主要考虑的两个因素。本文提出基于简单块方式的矩形毛坯五块切割排样算法,用以解决金属板材切割排样问题。这种算法将板材分为5个块,各块中矩形毛坯按照简单块方式排列。首先确定所有可能尺寸的最优简单块方式;然后采用隐式枚举法考察所有可能的五块组合的排样价值,选择排样价值最大的一个组合作为最终的五块排样方式。采用文献中的基准测题对比验证了五块排样算法。结果表明,该算法在提高材料利用率和简化板材切割工艺两方面均有效,且算法计算时间较短。     

遗传算法模型在矩形件排样优化中的应用

采用遗传算法对矩形件在板材上的排样进行优化,以提高板材的利用率和降低生产成本.本文建立了优化排样的遗传算法模型,描述了遗传算子的设计方法.将此模型与基于最低水平线的搜索算法相结合应用到矩形件排样优化中,产生的排样结果满足"一刀切"和相同的矩形件尽量排放在一起等工艺要求,并且使板材的利用率在94%左右,可以应用到企业的实际生产中.     

矩形件排样问题的遗传模拟退火混合求解算法

为了提高矩形件排样问题的板材利用率,提出了基于匹配度的最低水平线定位方法和遗传模拟退火的排序方法。对于矩形件排样问题,建立了以提高板材利用率为目标的优化模型。在矩形件的定位方法中,为了提高最低水平线算法的板材利用率,提出了矩形件与板材匹配度的概念,实现了基于匹配度的最低水平线算法,此方法可以对排序结果进行微调和再优化。在排序方法中,给出了遗传模拟退火的混合算法,此算法依概率选择染色体,相比于贪婪准则可有效提高染色体的多样性。经Benchmark中的C算例进行验证,遗传模拟退火算法排样的板材利用率均高于遗传算法排样的板材利用率,验证了所提排样方法的优越性。     

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

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

矩形件排样优化的一种近似算法

摘要根据矩形件排样的实际下料工艺要求，以板材的长或宽对待排矩形件的长或宽求余数，根据余数结果提出了一种矩形件排样的近似优化算法。     

多卷材二维下料问题的一种启发式算法

讨论多卷材二维剪切下料问题,即使用多种不同宽度的卷材剪切出若干种一定数量的矩形件,优化目标为材料利用率最高。提出一种顺序启发式下料算法,构造排样方式生成算法,首先根据卷材宽度方向切割废料最小原则,确定矩形件在卷材宽度方向上的排列方式;然后根据卷材长度方向切割废料最小原则,确定卷材的长度以及矩形件在卷材长度方向上的排列方式。按照当前矩形件需求量调用上述排样方式生成算法,生成一个排样方式满足部分矩形件需求量,重复该过程,直到所有矩形件需求量均得到满足为止。采用实际生产中的例题将本文下料算法和文献中排样系统进行比较,数值模拟结果表明:本文算法在优化结果和计算时间两方面均有效。     

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

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