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

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

结合批量问题的多目标矩形件优化排样

设计多目标启发式进化算法,研究了一种考虑批量问题的二维矩形件排样问题,建立了含有原材料成本最小化和零件库存成本最小化的多目标优化模型。先用启发式算法初始化下料方式,再用改进的快速非支配排序算法进行优化求解,确定下料方案。通过实验结果以及与其他算法的对比表明,在中等规模的矩形件排样问题中,该算法能够在较快的时间内既保证较高的原料利用率,又能降低该问题的总成本,证明了该算法的有效性。     

基于匀质条带的矩形件最优三块布局算法

为解决大规模矩形件布局问题,提出一种动态规划算法生成基于匀质条带的矩形件最优三块布局方式。这种算法将板材分为三个块,同一块中只包含方向和长度均相同的匀质条带。通过求解背包模型生成块中的条带最优布局,隐枚举的讨论所有可能尺寸的块,确定所有三块组合的布局价值,选择布局价值最大的一个组合作为最优解。通过文献中的测题,将该算法与经典两段布局算法和启发式布局算法TABU500进行比较。实验结果表明:该算法在计算时间和材料利用率两方面都有效,且生成的布局方式简化了下料切割工艺。     

基于排样矩形的直角边零件下料算法

针对实际操作中直角边零件下料利用率不高的问题,导入排样矩形的概念,将直角边零件下料问题分解为若干优化子问题,在此基础上,基于动态规划思想通过求解子问题构建全局最优解.实验表明,与传统的直角边零件板材切割相比,使用本文算法能够使板材的利用率提高30％-50％;与其他几种典型算法相比,本算法板材利用率提高显著,并且排样方案...     

二维板材切割下料问题的一种确定性算法

研究二维板材切割下料问题,即使用最少板材切割出一定数量的若干种矩形件。 提出一种结合背包算法和线性规划算法的确定性求解算法。首先构造生成均匀条带四块排样方 式的背包算法;然后采用线性规划算法迭代调用上述背包算法,每次均根据生产成本最小原则 改善目标函数并修正各种矩形件的当前价值,按照当前价值生成新的排样方式;最后选择最优 的一组排样方式组成排样方案。采用基准测题,将该算法与著名的T 型下料算法进行比较,实 验结果表明,该算法比T 型下料算法更能节省板材,计算时间能够满足实际应用需要。     

生成最优单毛坯条带T型布局方式的精确算法

为解决大规模矩形件布局问题,提出一个生成单毛坯条带T型布局方式的精确算法。该算法不仅可在合理时间内取得好的优化结果,而且在满足实际下料工艺的同时化简了切割工艺。该算法首先确定最优单毛坯条带,然后通过求解一维背包问题确定单毛坯条带在级中的布局方式和级在段中的最优布局方式,最后选择两个最优段生成布局方式。通过文献中的63道基准测题,将该算法与5种著名算法(经典两阶段、普通T型、同质块两阶段、普通布局算法和启发式算法TABU500)进行了比较。实验结果表明,该算法在计算时间和材料利用率两方面都有效。     

面向可制造性的两阶段一维优化下料方法

针对诸多优化下料方法片面追求高原材料利用率,而对实际切割加工成本考虑不足的现状,提出一种既维持高原材料利用率又使下料方案可制造性好的一维优化下料方法.下料方案的可制造性从切割方式种类数和每种切割方式中套裁零件种类数两方面来衡量,基于此提出了非定长优化和定长优化相结合的两阶段一维优化下料方法,并采用两阶段列生成算法实现.最后通过实例验证了文中方法的实用性和有效性.     

二维优化排样方法及实现技术

在工业应用领域中存在大量的二维下料问题,其中应用最多的是矩形件下料问题.矩形件下料问题的关键是寻找二维平面的优化布局.针对工业生产中实际存在的问题与约束条件,给出了新的规则设计理论和数据模型,利用覆盖率和有效覆盖率的概念来控制余料合并操作的执行,运用布局规则、组合规则和切割规则给出了一种新的启发式算法.实验分析和工业应用证明,该启发式算法可以有效地提高板材的整体利用率,极大地减少了板材损耗.     

生成矩形毛坯最优T形排样方式的递归算法

讨论矩形毛坯无约束两维剪切排样问题．采用由条带组成的T形排样方式，切割工艺简单．排样时用一条分界线将板材分成2段，同一段中所有条带的方向和长度都相同．一段含水平条带．另一段含竖直条带．采用递归算法确定分界线的最优位置以及每段中条带的最优组合．以便使下料利用率达到最高．采用大量随机生成的例题进行实验，结果表明该算法在计算时间和提高材料利用率2方面都较有效．     

基于自适应遗传算法和多条带策略的排样方法研究

针对现代工业工艺生产中普遍存在的矩形件排样优化问题,在遗传算法的主要环节应用性能较优的算子对矩形件排样序列进行了求解,并运用交叉概率和变异概率能自适应调整的方法来提高遗传算法的收敛速度及稳定性。提出了满足工艺生产切割要求的多条带策略,辅以最低水平线算法的择优插入策略对矩形件序列进行解码。实验结果表明, 与分层策略相比,所提出的排样方法不仅能得到 更高、更稳定的板材利用率,而且还能提高工艺生产的效率并降低生产的时间成本,具有重要的现实意义。     

基于价值修正的圆片下料顺序启发式算法

讨论圆片剪冲下料方案的设计问题。下料方案由一组排样方式组成。首先构造一种生成圆片条带最优四块排样方式的背包算法,然后采用基于价值修正的顺序启发式算法迭代调用上述背包算法,每次都根据生产成本最小的原则改善目标函数并修正各种圆片的当前价值,按照当前价值生成一个新的排样方式,最后选择最优的一组排样方式组成下料方案。采用文献中的基准测题将文中下料算法与文献中T 型下料算法和启发式下料算法分别进行比较。实验计算结果表明,该算法的材料利用率比T 型下料算法和启发式下料算法分别高0.83%和3.63%,且计算时间在实际应用中合理。     

Strips minimization in two-dimensional cutting stock of circular items

Circular items are often produced from stock plates using the cutting and stamping process that consists of two stages. A guillotine machine divides the plate into strips at the cutting stage, and then a press punches out the items from the strips at the stamping stage. The cutting cost at the first stage often increases with the number of strips in the cutting plan. An approach is presented for the two-dimensional cutting stock problem of the strips at the cutting stage. The objective is to minimize the sum of the material and the cutting costs. The approach formulates the problem as an integer linear programming, and uses a column generation method for generating the cutting patterns. The cutting patterns have the feature that each cut on the plate produces just one strip. The computational results indicate that the approach can greatly reduce the number of strips in the cutting plan.     

Heuristic for constrained T-shape cutting patterns of rectangular pieces

T-shape patterns are often used in dividing stock plates into rectangular pieces, because they make good balance between plate cost and cutting complexity. A dividing cut separates the plate into two segments, each of which contains parallel strips, and the strip orientations of the two segments are perpendicular to each other. This paper presents a heuristic algorithm for constrained T-shape patterns, where the optimization objective is to maximize the pattern value, and the frequency of each piece type does not exceed the demand. The algorithm considers many dividing-cut positions, determines the pattern value associated to each position using a layout-generation procedure, and selects the one with the maximum pattern value as the solution. Pseudo upper bounds are used to skip some non-promising positions. The computational results show that the algorithm is fast and able to get solutions better than those of the optimal two-staged patterns in terms of material utilization.     

圆片下料并行遗传算法的设计与实现

针对制造行业中的圆片下料问题,为了在合理的计算时间内使材料的利用率尽可能高,提出并行遗传下料算法（PGBA）,以下料方案的材料利用率作为优化目标函数,将下料方案作为个体,采用多线程的方式对多个子种群并行进行遗传操作。首先,在并行遗传算法的基础上设计特定的个体编码方式,采用启发式方法生成种群的个体,以提高算法的搜索能力和效率,避免早熟现象的发生;然后,采用性能较好的遗传算子进行自适应的遗传操作,搜索出一种近似最优的下料方案;最后,通过多种实验验证算法的有效性。结果表明,与启发式算法相比,PGBA的计算时间有所增加,但材料利用率得到了较大的提高,能有效提高企业的经济效益。     

有限制二维板材启发式下料算法研究

橱柜及板式家具生产都涉及二维板材下料,材料利用率的最大化一直是该类企业追求的目标。本文提出了基于启发式规则的有限制二维板材下料算法。通过在橱柜生产过程中自动下料系统的实施和理论分析,该算法是实用有效的。     

冲裁条带最优多段排样方式的动态规划算法

讨论冲裁件无约束剪冲排样问题,用动态规划算法生成冲裁条带多段排样方式。采用一组相互平行的分割线将板材分成多个段,每段含一组方向和长度都相同的条带。通过动态规划算法确定所有可能尺寸段的最优价值以及板材中段的最优组合,使整张板材价值达到最大。实验结果表明该算法能够提高材料利用率,计算时间能满足实际应用的需要。     

Heuristic for the two-dimensional arbitrary stock-size cutting stock problem

A heuristic is presented for the two-dimensional arbitrary stock-size cutting stock problem, where a set of rectangular items with specified demand are cut from plates of arbitrary sizes that confirm to the supplier’s provisions, such that the plate cost is minimized. The supplier’s provisions include: the lengths and widths of the plates must be in the specified ranges; the total area of the plates with the same size must reach the area threshold. The proposed algorithm uses a pattern-generation procedure with all-capacity property to obtain the patterns, and combines it with a sequential heuristic procedure to obtain the cutting plan, from which the purchasing decision can be made. Practical and random instances are used to compare the algorithm with a published approach. The results indicate that the trim loss can be reduced by more than half if the algorithm is used in the purchasing decision of the plates.     

基于下料特征的大规模零件分组优化方法

针对诸多算法在处理大规模零件下料问题时易陷入时间效率和材料利用率矛盾的问题,提出一种基于零件下料特征的分组优化方法.首先采用图论工具对零件下料特征关联进行分析,建立零件相似特征关联有权无向图与零件下料配合特征关联有权无向图;然后将样本零件所表现的下料特征作为分组约束,通过对无向图最小生成树(MST)的分割完成待下料零件的自适应分组.优化前根据材料利用率对零件分组进行排序,优化中对零件的组间分布进行动态补偿,最后合并各组优化结果得到原问题的下料方案.实验结果表明,该方法是可行的和有效的.