基于启发式搜索和背包算法的分布式排样系统

针对理论上属于NP完全问题的二维矩形件优化排样问题,构建了一个排样效率高、计算速度快和排样效果好的一种近似算法.并结合计算机网络的大量应用,将算法应用于分布式排样系统.算法的主要思想是采用启发式搜索和背包算法,使每次排样都达到局部最优,从而得到近似最优解.并与其它2种近似算法进行了比较,指出了它们的不足之处,还给出了一个排样实例.

Distributed Cutting Stock System Based on Heuristic Search and Knapsack Algorithm

A approximate algorithm is presented by which satisfactory results of two dimensional optimal layout belonged to NP complete problems can be obtained efficiently and rapidly. The algorithm integrated with widespread of computer network has been applied to the distributed cutting stock system Adopting Heuristic search and Knapsack algorithm, the algorithm makes each layout optimal locally and obtained the approximate optimal solution. It is compared with other two approximate algorithms and pointed out their shortcomings. In the end of the article a layout example was presented.