对大规模矩形件排样问题提出一种精确、可生成一种新的满足剪冲下料工艺需求的排样方式:基于单毛坯条带的矩形件最优两段排样方式.采用动态规划算法生成最优单毛坯条带,通过一维背包算法确定条带在级中的排样方式和级在段中的最优排样方式,选择最优的两个段组成排样方式.对传统文献中的43道大规模基准测题进行计算,有38道测题达到最优,剩余5道测题的优化结果与最优化结果的比率达到99.9％,每题的平均计算时间仅用2.17s.结果表明,本文算法优于经典两段和著名的T型排样算法,在解决大规模矩形件排样具有高效性.%An efficient exact algorithm is presented for large-scale rectangular packing problem. This algorithm generates new cutting patterns-optimal two-segment cutting patterns for rectangular pieces based on the homogenous strip. Firstly, the algorithm uses a dynamic programming recursion to generate optimal homogenous strips. Secondly, the algorithm solves knapsack problems so as to obtain the strip layouts on the sections and the section layouts on segments of various lengths. Finally, the algorithm selects two optimal segments to compose the cutting pattern. The algorithm is tested on 43 large-scale benchmark problems. The number of.optimal solutions is 38 for this paper's algorithm,and the rate of the rest 5 problem's solution value and the optimal solution reaches 99.9%. The average computation time is 2.17seconds. Compared with the classic two segment and the well known T-shape algorithms, the solutions of this paper's algorithm are better. Experimental results show that the algorithm is efficient in solving large-scale instances.
展开▼
