基于多级排样方式的单一矩形件卷材下料算法

Coil cutting algorithm of single rectangular pieces based on multi-stage layout

讨论了单一矩形件卷材下料问题,即采用剪切工艺将卷材切割出一定数量的同种矩形件,目标为使得所耗费的卷材长度最小。提出一种基于隐式枚举法和动态规划算法的优化下料算法。切割过程由2个阶段组成,第1阶段将卷材切割成宽度相同、长度不大于剪刃长度的段,第2阶段将段切割成矩形件。首先,采用隐式枚举法确定所有需要考察的段的长度,并采用动态规划算法确定不同长度段中矩形件的多级排样方式;然后,选择材料利用率最高的段,按照该段使用数量最大且不产生多余矩形件的原则确定该段的使用数量;最后,选择一个长度最小的段来满足矩形件的剩余需求量。与普通下料算法进行对比,实验结果表明:基于隐式枚举法和动态规划算法的优化下料算法可以有效地解决单一矩形件卷材下料问题。

The coil cutting problem of single rectangular piece was discussed, that was, a certain number of the same kind of rectangular pieces were cut from the coil by the shearing process, and the goal was to minimize the length of the coil consumed. Then, an optimal cutting algorithm was proposed based on the implicit enumeration method and the dynamic programming algorithm, and the cutting process consisted of two stages. In the first stage, the coil was cut into segments with the same width and the length less than the cutting blade length, and in the second stage, the segments were cut into rectangular pieces. First, the length of all the segments to be investigated was determined by the implicit enumeration method, and the multi-stage layout of rectangular pieces in the segments of different lengths was determined by the dynamic programming algorithm. Then, the segment with the highest material utilization rate was selected, and the number of use for this segment was determined according to the principle of the largest use for this section and no redundant rectangular pieces. Finally, the segment with the smallest length was selected to meet the remaining demand of rectangular pieces, and the above-mentioned cutting algorithm was compared with the ordinary cutting algorithm. The experimental results show that the optimal cutting algorithm based on implicit enumeration method and dynamic programming algorithm can effectively solve the coil cutting problem of single rectangular piece.