生成最优同质条带两阶段布局方式的精确算法

An exact algorithm for generating optimal two stage homogeneous strip layouts

传统最优解算法在解决大规模二维件布局问题时,计算时间较长。提出一种基于同质条带两阶段布局算法,此算法生成的同质两阶段布局方式,满足生产中的剪冲下料工艺,且计算时间合理。首先,竖直剪切线将板材分割成同质段;然后,水平剪切线将同质段分割成同质条带。通过求解动态规划算法生成最优同质条带布局方式,求解背包问题得到同质条带在同质段上和同质段在板材上的最优布局方式。利用经典文献中的基准测题,将此算法与普通两阶段算法、TABU500算法和最优解精确算法进行比较,结果表明此算法在布局价值优于普通两阶段和TABU500型算法,计算时间远远短于最优解精确算法,优化结果等于或极接近于最优解精确算法。

The time required by an optimal exact algorithm to solve the large-scale rectangle two-dimensional cutting problems may become unbearable. So an algorithm for two-stage homogeneous strip patterns for pieces is presented. The algorithm not only is appropriate for the shearing and punching process, but also reasonable in time. Firstly, vertical cuts divide the stock sheet into composite strips, and then horizontal cuts divide the composite strips into homogeneous strips. The algorithm uses a dynamic pro- gramming recursion to determine the optimal homogeneous strip layout, solves knapsack problems to obtain the homogeneous strip layout on the composite and the composite strip layout on the sheet. The algorithm is tested through benchmark problems, and compares with three famous algorithms, the classic two-stage algorithm, the TABU500 algorithm and optimal algorithm. The pattern value of this algorithm is better than that of the classic two-stage and TABU500 algorithm. What＇ s more, this algorithm can give solutions very close to optimal algorithm, and the computation time is shorter than optimal algorithm.