基于单毛坯条带的矩形件排样算法  

An algorithm for generating patterns of rectangular items based on homogenous strips

作　　者：孟朝霞[1] 杨玉丽[1] 崔耀东[2] 

机构地区：[1]运城学院公共计算机教学部,运城044000 [2]广西师范大学计算机科学与信息工程学院,桂林541004

出　　处：《机械设计与制造》2010年第1期61-62,共2页Machinery Design & Manufacture

基　　金：国家自然科学基金(60763011);广西科学基金资助(桂科自0728100)

摘　　要：提出一种基于单毛坯条带的矩形件排样算法,该算法采用三条剪切线将板材分成四个矩形区域,每个区域中包含一组方向和长度都相同的单毛坯条带。其中,用枚举的方法确定三条分割线的位置,用背包算法确定每个区域中条带的最优布局,使整张板材价值达到最大。将该算法与线形规划相结合形成基于单毛坯条带的矩形件排样方案生成算法,用于求解大规模矩形件排样问题。利用文献中报道的例题进行计算,实验结果表明该算法的计算时间满足实际应用的需要,并能在一定程度上提高材料利用率。An algorithm is proposed for generating patterns of rectangular items based on homogenous strips（RIBTHS ）. It divides the plate into four regions. Each region contains homogenous strips of the same direction and length. An enumeration method is used to determine the positions of the three partition lines. The knapsack algorithm is used to obtain the optimal layout of the strips in each region. The combination of the regions that has the maximum value is selected as the optimal solution. The procedure is combined with the linear programming approach to form the algorithm for generating the cutting plans of large scale cutting stock problems. The algorithm was tested using lots of benchmark instances reported in the literature. The results indicate that the algorithm is efficient both in material utilization and computation time.

关 键 词：矩形件排样 切割下料 优化排样 

分 类 号：TH164[机械工程—机械制造及自动化]