多卷材二维下料问题的一种启发式算法

讨论多卷材二维剪切下料问题,即使用多种不同宽度的卷材剪切出若干种一定数量的矩形件,优化目标为材料利用率最高。提出一种顺序启发式下料算法,构造排样方式生成算法,首先根据卷材宽度方向切割废料最小原则,确定矩形件在卷材宽度方向上的排列方式;然后根据卷材长度方向切割废料最小原则,确定卷材的长度以及矩形件在卷材长度方向上的排列方式。按照当前矩形件需求量调用上述排样方式生成算法,生成一个排样方式满足部分矩形件需求量,重复该过程,直到所有矩形件需求量均得到满足为止。采用实际生产中的例题将本文下料算法和文献中排样系统进行比较,数值模拟结果表明:本文算法在优化结果和计算时间两方面均有效。

A heuristic algorithm for two-dimensional cutting problem with multiple coils

The problem of two dimensional cutting multiple coils was discussed. It used a variety of different width coils to cut a certain number of rectangles of several kinds, and the optimization goal was to make the material utilization rate reach the maximum. Then, a se-quential heuristic algorithm was proposed, and the pattern generation algorithm was constructed. Firstly, the arrangement of rectangle in coil width direction was determined according to the principle of minimum width trim loss, then the coil length and arrangement of rectan-gle in coil length direction was determined based on the principle of the minimum length trim loss. Furthermore, in view of the current de-mand on rectangle, the above pattern generation algorithm was applied to generate a pattern so as to meet some demand of rectangle, and the process was repeated until all the rectangle demand satisfied requirements. This sequential heuristic algorithm was compared with the nesting system in literature by practical examples, and numerical experiments show that the algorithms are effective in both optimization re-sults and calculation time.