两阶段启发式算法在矩形件排样中的应用  

Application of two-stage heuristic algorithm for rectangle packing

作　　者：张兆东[1] 薛立仲 翁朝阳 陆宝春[2] Zhang Zhaodong;Xue Lizhong;Weng Chaoyang;Lu Baochun(School of Electrical and Automotive Engineering,Yangzhou Polytechnic College,Yangzhou 225009,China;School of Mechanical Engineering,Nanjing University of Science and Technology,Nanjing 210094,China)

机构地区：[1]扬州市职业大学电气与汽车工程学院,江苏扬州225009 [2]南京理工大学机械工程学院,江苏南京210094

出　　处：《南京理工大学学报》2023年第6期767-773,共7页Journal of Nanjing University of Science and Technology

基　　金：国家重点研发计划(2018YF308300)。

摘　　要：针对定制式木门家具生产过程中板材资源利用率低和常规启发式排样算法得到的排样结果切割工艺复杂的问题,采用启发式排样和优化排序相结合的方式,提出了两阶段排样方式和遗传算法相结合的组合式矩形板材排样算法。以两阶段排样方式为基础,通过对排样过程中物块摆放时会遇到的5种情况分别给出对应处理方案,提出了两阶段启发式排样算法,同时利用改进的遗传算法进行板材组号的排序优化。测试结果表明,该文算法取得了98.11%的最高资源利用率,算法输出排样方案的板材切割工艺得到了优化,提高了实际生产中板材切割的生产效率并降低了生产与时间成本。To address the issue of low utilization of board resources and the generation of pattern results with only complex cutting processes by conventional heuristic layout algorithms during the production process of custom wooden door furniture,a combined rectangular board layout algorithm based on two-stage nesting and genetic algorithm is proposed by integrating heuristic nesting and optimized sorting.Using the two-stage layout method as the foundation,the corresponding processing plan for five situations those may occur when arranging the blocks during the nesting process is given,and a two-stage heuristic layout algorithm is proposed.Meanwhile,an improved genetic algorithm is utilized for the optimization of board grouping.The test results show that the algorithm here achieves the highest resource utilization rate of 98.11%,optimizes the cutting process of the algorithm’s output layout plan,improves the production efficiency of board cutting in actual production,and reduces production and time costs.

关 键 词：二维矩形排样 启发式算法 优化排序 两阶段排样 遗传算法 资源利用率 板材切割 生产效率 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TB34[自动化与计算机技术—控制科学与工程]