基于均匀条带排样方式的二维下料启发式算法

条带结构排样方式在机械制造业下料领域有广泛的应用。针对矩形件二维下料问题,提出一种基于均匀条带排样方式的启发式下料算法。下料方案包含多个排样方式,每个排样方式满足部分矩形件的需求量。首先构造均匀条带四块排样方式的约束排样算法;然后采用列生成法反复调用上述约束排样算法生成各个排样方式,直到所有矩形件需求量得到满足为止。采用文献中的基准例题,将本文下料算法和文献中下料算法进行比较,数值实验结果表明本文下料算法能有效地提高板材利用率,且计算时间能满足实际应用要求。

A heuristic algorithm for two dimensional cutting stock problem based on uniform strip pattern

Strip structure pattern was widely used in the field of machinery manufacturing industry.For the problem of two dimensional cutting stock for rectangles, a heuristic algorithm was proposed based on uniform strip pattern.However, the cutting plan included a number of patterns, each of which met the demands of some rectangles.Firstly, the constrained packing algorithm for generated uniform strip four-block pattern was constructed, and then every pattern was generated by applying column generation method to call the constrained packing algorithm repeatedly until all demands of rectangles were met.At last, the literature benchmark instance was applied, and this algorithm was compared with the cutting stock algorithm in literature.The numerical results show that this algorithm can effectively improve the utilization ratio of plates, and the calculation time can meet the requirements of practical application.