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

Grouping Optimization Method of Large-Scale Parts Based on Cutting Stock Characteristics

作　　者：覃斌[1] 阎春平[1] 汪科[1] 刘飞[1] 

机构地区：[1]重庆大学机械传动国家重点实验室,重庆400030

出　　处：《计算机辅助设计与图形学学报》2012年第3期387-393,共7页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(50975299);中央高校基本科研业务费(CDJZR11110002)

摘　　要：针对诸多算法在处理大规模零件下料问题时易陷入时间效率和材料利用率矛盾的问题,提出一种基于零件下料特征的分组优化方法.首先采用图论工具对零件下料特征关联进行分析,建立零件相似特征关联有权无向图与零件下料配合特征关联有权无向图;然后将样本零件所表现的下料特征作为分组约束,通过对无向图最小生成树(MST)的分割完成待下料零件的自适应分组.优化前根据材料利用率对零件分组进行排序,优化中对零件的组间分布进行动态补偿,最后合并各组优化结果得到原问题的下料方案.实验结果表明,该方法是可行的和有效的.In order to resolve the contradiction of time efficiency and material utilization ratio in largescale parts cutting stock problem （LPCSP）, a grouping optimization method based on parts＇ cutting stock characteristics is proposed. By analyzing the association of parts＇ cutting stock characteristics with graph theory, the weighted undirected graphs of parts＇ similarity association and parts＇ combination association are established. Then, with cutting stock characteristics of parts samples as grouping constraints, the adaptive grouping of parts is accomplished by segmenting MST of the weighted undirected graph. The LPCSP is decomposed into several small-scale parts cutting stock problems （SPCSP）. Before parts nesting, the SPCSPs are sorted in descending order according to material utilization ratio. For every pair of two adjacent SPCSPs, a dynamic compensation strategy is adopted to adjust parts in different groups. Finally, the result of the LPCSP is obtained by combining all the results of the SPCSPs. The experimental results validate the feasibility and effectiveness of the proposed method.

关 键 词：下料问题 零件下料特征 最小生成树 优化 零件分组 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]