计算机排样问题是指在在特定底料内排放衣片,使区域的利用率达到最大,鉴于衣片均是不规则二维图形,所以该计算机排版问题可抽象成二维不规则图形优化排样问题。优化排样问题是指寻求二维图形在特定长度,宽度区域内的摆放尽可能多,以使区域的利用率达到最优。它在服装、皮革制品、体育用品、机械等制造行业中都有应用。国内有成千上万家这样的企业,大部分企业仍处于手工排样下料阶段,下料利用率较低,造成原材料的浪费。因此有效提高原材料的利用率,降低生产成本,是增加企业效益的有效途径之一。二维不规则图形的优化排样问题是一个在许多生产实践中有关键应用的重要问题,也是一个计算机科学和运筹学中的基本问题。在理论上属于NP-完全(困难)问题,因为存在实际形状的复杂性和计算上的复杂性,求解十分困难。 本文应用BLF启发式算法,同时结合有序边横截线扫描法以及局部最优算法。它是一种基于对不规则零件直接处理的方法。该算法在排样过程中对相邻的两个和两排的图形进行向左,向下的移动,通过减少它们之间的空隙来实现此目的。在排样计算的过程中,确定衣片处于相接触但不相交是一个关键的问题,整体布局使底料利用率最大是另一个关键问题。此外,本文还采用了另外一种算法-分类随机局部最优搜索算法,该算法包含了局部最优搜索的思想,衣片判交方面采用了调用API函数实现该功能,整体布局方面采用BLF算法。