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

• 作者: 曹炬 陈仕军
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 矩形件排样 最优水平线 排放算法
• 年，卷（期）: 2010,（12）
• 所属期刊栏目: 工程与应用
• 页码范围: 230-232,238
• 分类号: TP301.6
• 字数: 5239字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2010.12.069

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	曹炬	华中科技大学数学与统计学院	46	435	12.0	19.0
2	陈仕军	华中科技大学数学与统计学院	4	70	4.0	4.0