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

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

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