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

Application of two-stage heuristic algorithm for rectangle packing

针对定制式木门家具生产过程中板材资源利用率低和常规启发式排样算法得到的排样结果切割工艺复杂的问题,采用启发式排样和优化排序相结合的方式,提出了两阶段排样方式和遗传算法相结合的组合式矩形板材排样算法。以两阶段排样方式为基础,通过对排样过程中物块摆放时会遇到的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.