生成最优单毛坯条带T型布局方式的精确算法  

Exact algorithm for generating optimal homogenous strip T-shape layouts

作　　者：季君[1] 陆一平[1] 查建中[1] 崔耀东[2] 

机构地区：[1]北京交通大学机械与电子控制工程学院,北京100044 [2]广西大学计算机与电子信息学院,南宁530004

出　　处：《计算机应用》2012年第9期2634-2637,共4页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61063031;60975046)

摘　　要：为解决大规模矩形件布局问题,提出一个生成单毛坯条带T型布局方式的精确算法。该算法不仅可在合理时间内取得好的优化结果,而且在满足实际下料工艺的同时化简了切割工艺。该算法首先确定最优单毛坯条带,然后通过求解一维背包问题确定单毛坯条带在级中的布局方式和级在段中的最优布局方式,最后选择两个最优段生成布局方式。通过文献中的63道基准测题,将该算法与5种著名算法(经典两阶段、普通T型、同质块两阶段、普通布局算法和启发式算法TABU500)进行了比较。实验结果表明,该算法在计算时间和材料利用率两方面都有效。This paper presented an algorithm for generating the homogenous strip T-shape layouts for large-scale rectangular piece packing. The algorithm not only achieved good results within reasonable time, but also met the shearing and punching process need. The algorithm generated optimal homogenous strips, solved knapsack problems to obtain the strip layouts on the sections and the section layouts on the segments, and optimally selected two segments to compose the layouts. The algorithm was tested on 63 benchmark problems, and compared with five famous algorithms （the classic two-stage, the general T shape, the two-stage homogenous block, the general cutting pattern and the heuristic algorithm TABU500）. The computational results indicate that the algorithm is efficient in both the computation time and the material utilization rate.

关 键 词：下料 二维无约束布局 单毛坯条带 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]