求解矩形和圆形装填问题的最大穴度算法

• 作者: 陈端兵 黄文奇
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 装填 矩形和圆 占角动作 穴度
• 年，卷（期）: 2007,（4）
• 所属期刊栏目: 博士论坛
• 页码范围: 1-3
• 页数: 3页
• 分类号: TP301.6
• 字数: 2929字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2007.04.001

摘要

在超大规模集成电路设计,裁缝裁剪布料,玻璃切割等工作中提出了矩形和圆形装填问题,即把不同大小的矩形块和圆饼装入一个矩形容器中,以最大化容器的面积利用率为优化目标.对这一问题,可采用模拟退火,遗传算法等国际流行算法进行求解,但这些方法计算时间较长,计算结果的优度也不甚理想.利用人类的智慧和经验,提出了一种求解此问题的最大穴度算法.并对3个随机生成的测试实例进行了实算测试,所得结果的平均面积利用率为90.80%,平均计算时间为8.38 s.测试结果表明,算法对求解矩形和圆形装填问题是行之有效的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄文奇	华中科技大学计算机科学与技术学院	88	1090	21.0	27.0
2	陈端兵	华中科技大学计算机科学与技术学院	6	110	6.0	6.0