玻璃切割机二维排料优化问题的研究

　　二维优化排料问题是指玻璃切割机在一定尺寸的矩形区域内尽可能多的排放一系列形状的维几何图形，要求几何图形排放在矩形区域内，各图形互不重叠，并满足一定的工艺要求，从而使得此矩形区域的利用率尽可能的高。这项工作广泛应用于玻璃、造船、汽车电力、钣金、皮革、家具、服装及造纸等生产行业。材料费用在产品成本占有很大比重，据资料显示:材料的费用约占零件总成本的60%左右，格外是大批量生产时，只要对优化排料算法有所改进，减小材料的废料率，即使是材料的利用率提高1%，也就可以大大减少成本，提高产品竞争力，从而收到显明的经济效益。而合理排料是提高材料利用率的主要办法。

　　排料是优化组合的一类典型问题，从数学计算的复杂性理论来看，它属于具有较高复杂性的一类问题一-NP(多项式复杂程度的非确定性问题)整体问题。根据计算和难解性理论，目前还没有解决整体类问题的多项式算法，凭当前的计算技术和便件条件去求该问题的较优解是很困难的，而由于玻璃切割机生产实际的需要，人们又迫切需要利用现代科学手段得到一些能满足生产需要的算法。这些算法应该在可以接受的好解，即虽不是越优解，但接近越优解，并且比人工排料效率高，能达到或大于人们所期望的材料利用率。排料优化的目的就是要考虑选用什么样的排样模式来获得较高的材料利用率，从而使消耗的原材料板材数越少，达到使企业的经营成本较低的目的。二维排料问题大致分为两类：

　　一、矩形件排样问题：

　　这类问题可以说是排样问题研究的热点，在工业生产中常见的要求有两类:一是材料数量没限制，而要求的矩形件数量是固定的，要求耗用材料量越少;二是材料数量有限，要求排列出尽可能多的矩形，使废料越少。

　　二、不规则件的排样问题：

　　这类问题是较难处理的，由于零件和材料均为任意形状，使得玻璃切割机每次排料均得重新排样，因此，增加了问题的难度，所以排样问题的解法只是寻找一个较好的解决问题的方法。对该问题的研究方法大致分为两类：

　　1、矩形近似：

　　此类解法的主要思想是为单个或多个不规则零件的组合找出其较小包容矩型转化为矩形排料问题进行处理。此方法的优点是使得问题比较简单，缺点是对于高不规则度的零件会造成很大限度原料的浪费，失去可行性。

　　2、对不规则零件进行直接处理：

　　此种方法采用模拟人们手工排料思路进行排料。每次玻璃切割机只排定一个零件，以构成理想的结果，但需花费大量的排放和搜索时间，造成人力和财力的浪费。