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

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