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

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

人造板材矩形件优化下料属二维下料问题，并已经被证明是具有高度复杂性的 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.