高级检索

矩形件排样优化的一种近似算法

AN APPROXIMATE ALGORITHM FOR RECTANGULAR CUTTING STOCK PROBLEM

  • 摘要: 本文对理论上属于NP-完备问题的二维矩形件优化排样问题,构造了一个效率高、速度快、可令人满意的一种近似算法。该算法的主要思想是在排样过程中根据一种局部最优原则不断地动态产生一些较小的矩形,然后对这些小矩形区域排样,同时也消去一些已排过的矩形区域,直至所有的矩形件被排完。根据本文算法我们开发了一个矩形件排样系统。

     

    Abstract: This paper constructs an approximate algorithm for the two-dimensional layout of the rectangular pieces on the rectangular stocks.The problem belongs to NP-complete problem, so it is usually impossible to find its optimal solution. The main idea of the algorithm is to continuously produce some smaller rectangles on the stock by a local optimal principle, then allocate these rectangles with the rectangular pieces and delete the filled rectangles at the same time until all the rectangular pieces have been allocated.

     

/

返回文章
返回