基于分组降维规则和遗传算法的人造板材矩形件优化下料方法  

Layout Method of Rectangular Wood Based Panel Parts Based on Grouping and Dimension Reducing Heuristic Rule and Genetic Algorithm

作　　者：张国梁[1,2,3] 侯晓鹏[1,3] 苗虎[1,3] 安源[1,3] 周玉成[1,3] 姚永和 

机构地区：[1]中国林业科学研究院林业新技术研究所,北京100091 [2]河北农业大学林学院,保定071000 [3]中国林业科学研究院木材工业研究所,北京100091 [4]上海跃通木工机械设备有限公司,上海201505

出　　处：《林业科学》2014年第6期181-186,共6页Scientia Silvae Sinicae

基　　金：中国林业科学研究院林业新技术所基本科研业务费专项(CAFINT2012K01)

摘　　要：人造板材矩形件优化下料属二维下料问题，并已经被证明是具有高度复杂性的 NP 完备问题（吴杰君，2004；卢开澄，1998），目前尚无有效的最优解算法。国内外对此类问题的研究主要考虑某种近似算法和启发式算法，很多专家和学者做了卓有成效的研究工作（ Suliman，2006；季君等，2012；Furini et al．，2013）。遗传算法的全局搜索和并行处理能力使其在优化下料问题中得到了大量应用，无论是标准遗传算法或与其他算法相结合都体现出其解决复杂问题的有效性（曹炬等，1999；马炫等，2007；蒋兴波等，2008）。然而，现有排样算法中大多考虑大规模零件的整体套排（岳琪，2005；高乐文，2010），排样方案虽能获得较高的基材利用率和较小的余料损失，但过多的零件组合导致开料锯在切割过程中锯路变化烦琐，从而降低开料速度。因此下料算法的设计应充分考虑实际的生产工艺。一般情况下，在一块完整的基材上允许参与排样的零件种类数应为2～3种（张文江，1999）。Algorithms which were available in most literatures for whole layout of large scale rectangular parts gave solutions that resulted in frequent change of saw line and therefore dropped sawing velocity down. To solve this problem, a grouping and dimension-reducing heuristic rule which took areas of rectangular parts as priority was put forward in this paper. According to this rule,no more than three kinds of rectangular parts were considered in each layout calculation. Corresponding mathematical model was set up. Hybrid punishment function that was the combination of interior point method and exterior point one was applied to deal with constrains. Genetic algorithm （ GA） was adopted to search global optimal solution for layout. It was proved by example that the algorithm used in this paper could provide layout solution which exactly fulfilled guillotine cutting requirement and had saw line in order and therefore was useful to increase of sawing efficiency.

关 键 词：优化下料 分组降维 混合惩罚函数 遗传算法 

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