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

Distributed Cutting Stock System Based on Heuristic Search and Knapsack Algorithm

作　　者：魏群义[1] 彭晓东[1] 尹爱军[1] 

机构地区：[1]重庆大学机械工程学院,重庆400030

出　　处：《重庆大学学报（自然科学版）》2005年第3期57-60,共4页Journal of Chongqing University

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

关 键 词：矩形件优化排样 启发式搜索 背包算法 分布式系统 

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论]