一种求解矩形块装填问题的拟人算法

在货物装载、木材下料、超大规模集成电路（VLSI）设计等工作中提出了矩形块装填与切割问题，对这一问题，国内外学者提出了诸如模拟退火算法、遗传算法及其它一些启发式算法等求解算法。本文利用人类的智慧和他们上万年以来形成的经验，提出了一种求解矩形块装填问题的拟人算法。谊算法使用了两个主要的思想策略，即矩形块选择策略和矩形块放置策略。用本文提出的算法，对21个测试算例进行了实算测试，测试结果表明：算法所得装填结果的优度高，计算时间短。对这21个测试算例。用本文算法计算，得到了其中16个算例的最优解，而计算时间都在2秒以内。进一步的测试表明，本文提出的算法对求解矩形块装填问题十分有效。

A Quasi-human Heuristic Algorithm for Rectangle Packing Problem

Rectangle packing/cutting problem is often raised in loading,timber cutting,Very Large Scale Integration (VLSI)design,and so on.For solving this problem,many algorithms such as simulated annealing,genetic algorithm, and other heuristic algorithms have been proposed.In this paper,an efficient quasi-human heuristic rectangle packing algorithm is proposed according to ten-thousand-year experience and wisdom of human being.The algorithm utilizes two important strategies,i.e.,how to select the rectangle based on its value and how to pack it according to the corner occupying place.21 rectangle packing test instances are tested by the produced algorithm,16 instances of them achieve optimum solutions,and the runtime is less than 2 seconds for each instance.The integrated performance of the pro- duced algorithm is rather satisfied.Experimental results demonstrate that the algorithm proposed in this paper is rather efficient for solving rectangle packing problem.