解决二维下料问题的最优两阶段排样方式  

Optimal two-staged patterns for the two-dimensional cutting problem

作　　者：季君[1] 邢斐斐 黄敦华[1] 崔耀东[2] 师宁[1] JI Jun;XING Feifei;HUANG Dunhua;CUI Yaodong;SHI Ning(School of Mechanical,Electronic Engineering,Beijing Polytechnic,Beijing 100176,China;School of Computer,Electronics and Information,Guangxi University,Nanning 530004,China)

机构地区：[1]北京电子科技职业学院机电工程学院,北京100176 [2]广西大学计算机与电子信息学院,南宁530004

出　　处：《现代制造工程》2021年第3期81-86,119,共7页Modern Manufacturing Engineering

基　　金：国家自然科学基金项目(71371058,61363026);北京市教委科研计划项目(KM201910858004);北京电子科技职业学院科技重点课题项目(2019Z002-003-KXB)。

摘　　要：提出了一种用于生成矩形毛坯二维下料方案的同质块两阶段排样方式算法。下料方案中仅允许一种尺寸的毛坯出现在指定大小的矩形块即同质块中,从而简化了切割过程。该算法使用隐式枚举方法来考虑所有可能的同质块大小,从中选择最优同质块;结合线性规划确定最佳两阶段排样方式,以达到最佳效果。通过文献中的测题,将该算法与2种普通两阶段排样方式算法及普通T型排样方式算法进行比较,实验结果表明,该算法在计算时间和材料利用率两方面均有优势。An algorithm is presented for generating the two-dimensional guillotine-cutting stock problem for rectangular blanks.It simpli es the cutting process by allowing only one size of blanks to appear in a rectangular block.The algorithm uses an implicit enumeration method to consider all possible homogeneous block sizes,and selects the optimal homogeneous block from them.Combined with linear programming,the optimal two-staged cutting pattern was determined to achieve the best results.Through the test problems in the literature,the algorithm is compared with two general two-staged cutting patterns algorithms and general T-shape cutting plan algorithms.Experimental results show that the algorithm is effective in both calculation time and material usage.

关 键 词：二维下料 优化 线性规划 两阶段排样 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]