Journal of Computer Applications ›› 2011, Vol. 31 ›› Issue (06): 1689-1691.DOI: 10.3724/SP.J.1087.2011.01689

• Typical applications • Previous Articles     Next Articles

Two-stage segment optimal packing of single size rectangles

JIANG Yongliang1,YANG Zhiqiang2,ZHANG Chengyi3   

  1. 1. Department of Information Technology, Qiongtai Teachers College, Haikou Hainan 571100, China
    2. International College, Huanghai University, Zhumadian Henan 463000, China
    3. School of Mathematics and Statistics, Hainan Normal University, Haikou Hainan 571158, China
  • Received:2010-12-17 Revised:2011-01-23 Online:2011-06-20 Published:2011-06-01
  • Contact: ZHANG Chengyi

基于两阶段的分段单一矩形优化排样

姜永亮1,杨志强2,张诚一3   

  1. 1. 琼台师范高等专科学校 信息技术系,海口 571100
    2. 黄淮学院 国际关系学院,河南 驻马店 463000
    3. 海南师范大学 数学与统计学院,海口 571158
  • 通讯作者: 张诚一
  • 作者简介:姜永亮(1980-),男,河南漯河人,讲师,硕士,主要研究方向:计算机优化排样、智能算法;
    杨志强(1979-),男,河南汝南人,讲师,硕士,主要研究方向:数据库;〓
    张诚一(1955-),男,河南新野人,教授,主要研究方向:智能信息处理、决策分析与优化设计。
  • 基金资助:
    国家自然科学基金资助项目;海南省重点科技基金资助项目;海南省自然科学基金资助项目

Abstract: A two-stage approach was proposed which can solve the optimal packing of single size rectangles effectively. The best cutting patterns of standard sub-segment were solved and the problem was transformed into one-dimensional cutting stock problems in the first stage. In the second stage the best ideal solution was found with different methods for the one-dimensional cutting stock problems. With this method, an optimal packing of single size rectangles system was developed. The system not only can solve the segment layout of single size rectangles but also can solve other kinds of optimal packing of single size rectangles. Enterprise applications show that this method is an effective solution to the problem of single size rectangles packing.

Key words: single size ractangle, optimal packing, multi-level layout, segment layout, branch and bound algorithm

摘要: 为有效解决分段单一矩形优化排样问题,给出一个求解分段单一矩形优化排样问题的两阶段方法。第一阶段完成标准子段最佳排样方式求解,并将二维排样问题转化为一维下料问题,第二阶段使用适合于一维下料问题求解的算法完成板材最佳排样方式求解。使用该方法开发了一个单一矩形优化排样系统,该系统既可以解决分段单一矩形排样问题也可以解决其他类型的单一矩形优化排样问题。企业应用实例表明该方法是求解分段单一矩形优化排样问题的一个较为有效的方法。

关键词: 单一矩形, 优化排样, 多级排样, 分段排样, 分支定界算法

CLC Number: