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

摘要

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