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

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

Maximum caving degree algorithm for rectangle and circle packing problem

The rectangle and circle packing problem is concerned with packing a subset of different size rectangles and circles into a rectangular container,with the objective of maximizing the container's area usage.It has many industrial applications,such as very large scale integration design,sewing,glass cutting,etc.Some popular algorithms can be utilized to solve it,for example,the simulated annealing and the genetic algorithm.However,these algorithms are time consuming and the performance is not satisfying.In this paper,a maximum caving degree algorithm is recommended according to the ten-thousand-year experience and wisdom of human being.We have applied three randomly generated instances to the algorithm developed.The average container's area usage is 90.80% with an average runtime of 8.38 seconds.Experimental results demonstrate that the algorithm developed is fairly efficient for solving the rectangle and circle packing problem.