计算机应用 ›› 2012, Vol. 32 ›› Issue (09): 2634-2637.DOI: 10.3724/SP.J.1087.2012.02634

• 典型应用 • 上一篇    下一篇

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

季君1*,陆一平1,查建中1,崔耀东2   

  1. 1.北京交通大学 机械与电子控制工程学院,北京 100044;
    2.广西大学 计算机与电子信息学院,南宁 530004
  • 收稿日期:2012-03-07 修回日期:2012-05-07 发布日期:2012-09-01 出版日期:2012-09-01
  • 通讯作者: 季君
  • 作者简介:季君(1979-),女,山东泰安人,博士研究生,主要研究方向:智能设计与布局、优化计算; 陆一平(1965-),男,广西上林人,副教授,博士,主要研究方向:智能设计及布局、先进设计; 查建中(1947-),男,北京人,教授,博士,主要研究方向:智能工程、先进制造、网络制造; 崔耀东(1957-),男,河南林州人,教授,博士,主要研究方向:优化计算、CAD。
  • 基金资助:

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

Exact algorithm for generating optimal homogenous strip T-shape layouts

JI Jun1*,LU Yi-ping1,ZHA Jian-zhong1,CUI Yao-dong2   

  1. 1.School of Mechanical,Electronic and Control Engineering,Beijing Jiaotong University,Beijing 100044,China;
    2.School of Computer,Electronics and Information,Guangxi University,Nanning Guangxi 530004,China
  • Received:2012-03-07 Revised:2012-05-07 Online:2012-09-01 Published:2012-09-01

摘要: 为解决大规模矩形件布局问题,提出一个生成单毛坯条带T型布局方式的精确算法。该算法不仅可在合理时间内取得好的优化结果,而且在满足实际下料工艺的同时化简了切割工艺。该算法首先确定最优单毛坯条带,然后通过求解一维背包问题确定单毛坯条带在级中的布局方式和级在段中的最优布局方式,最后选择两个最优段生成布局方式。通过文献中的63道基准测题,将该算法与5种著名算法(经典两阶段、普通T型、同质块两阶段、普通布局算法和启发式算法TABU500)进行了比较。实验结果表明,该算法在计算时间和材料利用率两方面都有效。

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

Abstract: 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.

Key words: cutting stock, unconstrained two-dimensional layout, homogenous strip

中图分类号: