摘 要：二维优化下料问题是一个NP-复杂性问题，每一种优化软件都是利用近似和启发式处理得到下料结果，不同的优化方法及其优化软件对不同的某些数据结构可能效果并不理想，企业又不可能购进大量不同的优化软件来选优。针对以上问题本文提出了一种基于Internet的二维优化下料解决方法，并给出了该方法的具体实现技术。实验表明，该方法将明显提高二维优化下料的总体优化效果。
关键词：二维优化下料；启发式算法；Internet
中图分类号：TP391.75
广义地讲，节约原材料，优化利用资源是经济可持续发展战略的重要内容之一，也是绿色制造研究的重要组成部分。在当今市场经济条件下，对某一个企业而言，节约原材料，提高原材料利用率，降低成本，是该企业在市场经济竞争中取胜的重要条件[1,2]。在某些行业所需要的原材料中，
板材占有相当的比重，如机械、船舶、飞机、
玻璃、家具、服装等制造业。如果单靠人工凭经验完成下料工作，原材料利用率和工作效率都很低。随着计算机的出现，计算机辅助完成下料工作就显得尤为必要和重要了[3]。自20世纪60年代，人们就已经开始二维优化下料方面的理论和计算机算法的研究，已有许多公司提供软件产品，但由于二维优化下料应用的多样性和算法的复杂性，限制了二维优化下料技术更好地发挥作用。
1 当前应用中存在的问题
1.1 二维优化下料的方式繁多，通用性软件设计较难
二维优化下料问题在许多行业中广泛存在，各行业对二维优化下料的具体要求不同，即使同一行业、同一单位，由于具体业务不一样，要求也可能不一样。一般二维下料根据原材料的种类多少可以划分为多原材二维优化下料和单原材二维优化下料；根据下料零件板材的形状来划分，可以分为两大类：矩形板材和异形材下料（但原材料一般是指矩形件）；根据
切割约束的不同可以分为直角切割、Guillotine 切割、两阶段切割、方向性切割、一维切割、非直角切割、异形材切割等。
面对不同情况的不同要求，做一种通用的效果理想的二维优化
下料软件是非常困难的，因此要根据不同的应用开发相应的软件，而对使用者而言，买全可能要用到的各种二维优化软件是不太现实的，这样制约了二维优化技术的进一步推广应用。
1.2 优化下料技术理论复杂，理想算法的实现困难[4-7]
优化下料技术的研究理论涉及到线性规划（LP）、动态规划、启发式算法（SHP）以及人工智能（AI）等多种学术研究前沿理论，国内外学者在优化下料问题上进行过不断的努力，寻求了各种方法。
Gilmore 和Gomory（1965）把优化下料问题描述为整数规划问题。Dyckhoff（1981）提出了另一种线性规划的模型。Christofides和Whitlock（1977）提出了一种解决二维单原材异形材Guillotine下料的树搜索算法。Albano（1980）则提出了一种人机交互的二维排样方法。Albano和Orsini（1980）提出了一种成组排列下料板材的方法来实现Guillotine的切割。对于原材料是矩形件的二维单原材异形材下料，Adamowicz和Albano（1976）以及Haims（1968）提出了两阶段的算法，后来Albano和Sapuppo（1980），Dagh和Nisaner（1981），Tatoglu（1983），Beasley（1984）以及Fabien Chauny等（1991）对两阶段法进行了改进，提出了不同的启发式算法，以改进对庞大数量排样方式的处理。此后的很多研究基本上是集中于可行启发式算法，但是人们发现在某些情况下，传统的启发式算法是不够有效的。Dagli和Stacey（1988）根据下料问题和调度问题的相似性，提出了一种集人工智能（AI）和运筹学（OR）的方法来解决优化下料问题；后来（1990）Cihan将这一方法加以改进，在求解过程引入了一种基于知识的调度表结构。Morabito R.N.（1992）、Viswanathan K.V.（1993），Daza V.P.（1995）和Arenales M.（1995）等利用AI中的AND\OR图搜索方法来研究二维背包问题的解法，其分支和计算量仍然很大。
以上方法都不能很好处理优化下料过程所面对的近乎无穷的变量和运算。由于下料问题需要处理数量庞大的可行切割方式，是一个NP-完备问题。在一维下料中，可行切割方式的数量就很容易超过百万，二维下料问题的可行切割数量更为巨大。无论对于整数规划的数学模型还是其他的模型都不可能通过对所有的可行切割方式一一列举方法来规划优选，因为即使是利用现在最先进的计算机处理稍复杂的下料问题也是无法胜任的。对于这样一个NP-复杂性问题，通常只能用启发式方法求解。所以在各种优化下料的数学模型求解中，几乎都利用了启发式算法来减少庞大数量给运算结果带来的障碍。
现在已经提出来了很多针对不同结果满意度的启发式算法及其改进算法，但它们的分支和计算量仍然很大。对于各种算法在实用软件的实现过程中，为了增加搜索速度、减少计算误差影响和避免计算时间过长，提出了一系列处理方法：包括设置某一阀值因子控制可行切割方式的生成数量、设置单一排样最低的优化效率、限制下料零件的组合、设置消减计算机计算误差的
精度、设置各种时间阀值等等，这一系列的处理包括启发式算法本身均会引起优化计算的结果偏差。总结各种优化下料程序误差起因，可以将误差分为系统误差、算法误差和人为误差三种。系统误差是指计算机本身处理引起的误差，是不可避免的，却可以通过一定消减计算机计算误差方法加以减少；算法误差源于算法本身，主要是指处理庞大数量的排样方式时，搜索的深度和广度而言，相同算法条件下，随搜索深度和广度的增加，搜索时间越长，所以任何启发式函数的设置都限制遍历全部排样，而引起算法误差；人为误差主要是指在软件设计中，人为设定的各种阀值和因子。算法误差和人为误差在实用程序中也是难以完全避免的。
上一页123下一页
