生成匀质块排样方式的递推算法

Recursive algorithm for uniform block patterns

讨论矩形毛坯有约束二维剪切排样问题:将一张板材剪切成已知尺寸的一组毛坯,使排样方式的价值(板材中所含毛坯的总价值)最大;排样方式中每种毛坯的数量不能超过需求量。采用匀质块排样方式,每刀都从当前板材上切下一根水平或竖直的同质条带,其中仅含相同尺寸的毛坯。采用动态递推算法生成匀质块排样方式,在保证解的质量的前提下,有效地缩短计算时间,达到节约材料的目的。

The constrained two-dimensional cutting problem of rectangular items is discussed. Several types of rectangular items are produced from a single rectangular plate using guillotine cuts, so as to maximize the pattern value （that is, the total value of the items produced from the plate）, where the number of each type included in the pattern cannot exceed the demand. Uniform block patterns are used, where each cut on the current plate produces just one homogenous strip that contains items of the same type, the directions of two strips cut successively are either parallel or orthogonal. An algorithm based on a dynamic program- ming recursion is proposed. It can generate solutions of high quality in short computation time, and is useful in saving material.