关键词: 一刀切, 二叉树, 矩形件排样, 动态寻优, 启发式算法

Abstract: To improve the use rate of plates, meanwhile improve the reuse rate of remainders, two-dimensional guillotine cutting stock problem was studied. An optimized binary tree heuristic algorithm based on realistic constraints was proposed. Based on rules such as largest parts into the smallest hole, parts placed on the lower left, determine the direction of parts by modulus operation, and cutting plate on integer coordinate, the dynamic optimization algorithm process which was compatible for multi-sheet was presented. To get a fast solution by dynamic optimization for guillotine problem, an idea of remainders'dynamic split and merge was put forward, as well as a series of operators like Division, Merging, Strip, Shake, etc. The remainders were divided into two types of cavities I and II according to neighborhood relationship between them. The practical application of the computational system in the enterprise which was developed based on this algorithm showed that the algorithm could not only improve the utilization of blanks but also contribute to the improvement of the reuse rate of remainders by preventing the fragmentation of remainders.

Key words: guillotine, binary tree, rectangular packing, dynamic optimization, heuristic algorithms