摘要
针对理论上属于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.
出处
《重庆大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
2005年第3期57-60,共4页
Journal of Chongqing University
关键词
矩形件优化排样
启发式搜索
背包算法
分布式系统
orthogon optimal layout
heuristic search
knapsack algorithm
distributed system
