计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (12): 230-232.DOI: 10.3778/j.issn.1002-8331.2010.12.069

• 工程与应用 • 上一篇    下一篇

矩形件优化排样的一种启发式算法

陈仕军,曹 炬   

  1. 华中科技大学 数学与统计学院,武汉 430074
  • 收稿日期:2008-10-27 修回日期:2009-01-13 出版日期:2010-04-21 发布日期:2010-04-21
  • 通讯作者: 陈仕军

Heuristic algorithm for rectangular cutting stock problem

CHEN Shi-jun,CAO Ju   

  1. School of Mathematics & Statistics,Huazhong University of Science & Technology,Wuhan 430074,China
  • Received:2008-10-27 Revised:2009-01-13 Online:2010-04-21 Published:2010-04-21
  • Contact: CHEN Shi-jun

摘要: 对大规模矩形件正交排样问题,提出了一种快速高效的启发式排放算法。对当前的可排放位置(水平线),用贪婪算法从未排矩形件中选择可排放于该水平线的最优矩形件组合块;根据各个排放位置与其对应的矩形件组合块的匹配程度,选择最优的可排放位置(最优水平线)优先排放。在排放时,为了便于后续排放,先将待排放位置对应的矩形件组合块从低到高进行排序,再排放。对E.Hopper提供的规模最大的一类实例进行计算,排样率都在99%以上,平均排样率达到了99.38%,平均计算时间只用了1.12秒。与相关文献最好结果进行了比较,结果表明该文算法解决大规模的矩形件排样具有高效性。

Abstract: A fast and efficient heuristic packing algorithm is presented for large-scale orthogonal packing problem.For the present packing position(horizontal line),this paper uses greedy method to choose the combination of unpacked rectangles that satisfy packing condition.According to the matching degree of packing position and its corresponding combination of rectangles,it chooses optimal packing position(optimal horizontal line) for packing.For the convenient of later packing,it ranks the rectangles combination of packing position with height before packing.Three largest-scale test instances containing 196 or 197 pieces supplied by E.Hopper are computed by the algorithm of this paper,the utilization ratios of all are beyond 99%,the average utilization ratio and consumed time are 99.38% and 1.12 seconds respectively.Compared with the best results that have been published in related papers,it is showed the efficiency of algorithm of this paper for solving large scale rectangle packing problem.

中图分类号: