欢迎访问《图学学报》
分享到：
摘要：为解决大规模矩形件布局问题，提出一种动态规划算法生成基于匀质条带的矩形
件最优三块布局方式。这种算法将板材分为三个块，同一块中只包含方向和长度均相同的匀质
条带。通过求解背包模型生成块中的条带最优布局，隐枚举的讨论所有可能尺寸的块，确定所
有三块组合的布局价值，选择布局价值最大的一个组合作为最优解。通过文献中的测题，将该
算法与经典两段布局算法和启发式布局算法TABU500 进行比较。实验结果表明：该算法在计
算时间和材料利用率两方面都有效，且生成的布局方式简化了下料切割工艺。
Abstract: With the purpose of solve the large scale rectangular blanks packing problem, a dynamic#br# programming algorithm for generating the optimal homogeneous strip three block layouts is presented.#br# The plate is divided into 3 blocks, and every block contains only uniform strips which have the same#br# direction and length. The knapsack model to generate the optimal strip layout on the block is firstly#br# solved, and all possible sizes of blocks through implicit enumeration are discussed. All three block#br# layout value is determined, and a layout of the maximum value is selected as the optimal solution.#br# The algorithm was tested on some problems in the literature, and compared with the two algorithms#br# which are classical two segment layout algorithm and heuristic algorithm of TABU500. The#br# experimental results show that the algorithm not only can improve the utilization rate of material, but#br# also has a reasonable computation time and can simplify the cutting process.
