科研之友
微信
新浪微博
Facebook
分享链接
摘要
针对矩形件二维板材排样问题，提出递归多块排样方式及其动态规划生成算法。这种排样方式首先将板材划分成多个块，然后递归地对每个块进行多块划分，直到每个新产生的块中排放一种最优矩形件为止。为了均衡考虑排样方式的计算复杂度和板材排样价值，对于一刀切排样问题将多块划分的块数定为两块，对于非一刀切排样问题将多块划分的块数定为五块。动态规划算法首先计算每个块中分别排放一种矩形件所得到的1阶多块排样方式的最大价值，然后计算每个块中分别排放一个1阶多块排样方式所得到的2阶多块排样方式的最大价值，以此递推，得到任意阶数的多块排样方式的最大价值。通过比较块的排样价值的上界和下界来剔除不必要的多块划分，通过离散化划分线位置来控制算法的时间复杂度。采用文献典型例题和实际生产实例，将本文算法与一刀切排样算法和非一刀切排样算法进行对比，结果表明，本文算法排样价值较高，计算时间可满足实际应用需要。
- 单位
