摘   要：二维优化下料问题是一个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-复杂性问题，通常只能用启发式方法求解。所以在各种优化下料的数学模型求解中，几乎都利用了启发式算法来减少庞大数量给运算结果带来的障碍。

     现在已经提出来了很多针对不同结果满意度的启发式算法及其改进算法，但它们的分支和计算量仍然很大。对于各种算法在实用软件的实现过程中，为了增加搜索速度、减少计算误差影响和避免计算时间过长，提出了一系列处理方法：包括设置某一阀值因子控制可行切割方式的生成数量、设置单一排样最低的优化效率、限制下料零件的组合、设置消减计算机计算误差的精度、设置各种时间阀值等等，这一系列的处理包括启发式算法本身均会引起优化计算的结果偏差。总结各种优化下料程序误差起因，可以将误差分为系统误差、算法误差和人为误差三种。系统误差是指计算机本身处理引起的误差，是不可避免的，却可以通过一定消减计算机计算误差方法加以减少；算法误差源于算法本身，主要是指处理庞大数量的排样方式时，搜索的深度和广度而言，相同算法条件下，随搜索深度和广度的增加，搜索时间越长，所以任何启发式函数的设置都限制遍历全部排样，而引起算法误差；人为误差主要是指在软件设计中，人为设定的各种阀值和因子。算法误差和人为误差在实用程序中也是难以完全避免的。

    由上面可见，二维优化下料理论研究很多，但在实际应用中没有一种能够彻底消除程序误差。程序误差的存在，使实际应用中往往出现这种情况：将原始下料的数据做微小改变，结果会大大不同；将程序中某一阀值因子改变，优化结果会很大变化；将消除计算机误差处理的精度改变，结果也会发生一定变化；一个优化程序可能对某一组数据效果相对很好，对另外一组数据效果相对并不理想等等。这些都是由优化下料本身的复杂性和算法本身所决定的，软件实现中的参数、因子等数值的设置只能保证有一个良好的数学期望值，却很难根据原始数据和下料约束本身来产生一个最佳的值。如果通过浮动变化的参数、因子来替代设定的值，就可能得到更优的优化结果，而必然引起计算时间的大量开销，这种计算时间有时甚至是用户所不能容忍的。

    2  新的优化处理模型

     从以上问题分析可以看出，很难编制一种软件，使之满足各种下料方式和下料数据。在用户实际应用过程中，下料情况和数据千变万化，对于某一个软件用户，应用一种软件，可能在某种情况下料效果好，在有些情况下可能下料效果就不是很理想。而对每一次下料，可能直接影响用户的工程成本、资源的利用率，因此研究一种在各种情况下均能得到满意下料结果的下料方法具有非常重要的现实意义。

    不同算法，相同算法参数不同，可能对一些数据的效果不同，而目前很难从数学算法和软件设计上彻底解决这个问题，很难研究出一种在各种情况下优化效果都很好的应用软件。在研究中构建了图1所示的优化处理模型。在图1的优化处理模型中，优化软件可能是不同下料算法编制的软件、也可能是相同下料算法参数调整后形成的软件。前处理模块是将各种统一数据格式的下料数据转化为某种优化软件专用的数据格式，后处理模块是将各种格式的结果数据转化为统一的输出格式，结果评判负责将各个应用程序的优化结果进行比较，得出一个最优的结果。

    由图1模型可以看出，该模型并不是从优化算法上进行研究，而是一种集成当前优化下料软件的研究成果的方法。对于一组下料数据，事先很难知道用那些软件能得到较优的下料结果，而通过多个软件的并行优化下料，最后选出一个相对最优的结果，必将进一步提高优化下料的总体效果。模型具有良好的扩充和更新能力，可以充分跟随各种优化研究的最新成果，动态调整优化软件，发挥各种优化软件的优势，以达到适宜多种下料方式和对各种数据都具有满意的优化利用率的目的。模型在提高优化利用率的同时，由于各优化软件可以分布于不同的机器，可实现并行优化，减少下料时间。

    3 基于Internet的方法及其实现

    图1中的优化处理模型，可以同时解决多种优化方式、优化利用率和下料时间的问题。但对于一个具体用户，要构建这个模型是非常困难的。一方面多种优化软件的购买，二次接口开发将耗费大量的人力、物力、财力，另一方面构建该模型需要大量的计算机设备。对于一个特定用户，构建此模型显然是不现实的。此模型要发挥效果，考虑一种切实可行的应用方式是非常必要的。

    近年来，Internet技术得到了飞速的发展，许多计算机软件开发商为了提高产品性能、方便产品维护和升级，渐渐将产品转变为通过Internet提供服务，人们也渐渐习惯软件租用和利用互联网来提供服务的思想。我们利用前面提出的优化处理模型结合Internet技术，提出了一种基于Internet的二维优化下料方法。具体实现技术如图2，图2中认证中心负责对用户进行身份验证，并将有效用户任务提交给调度中心，调度中心根据任务类型、任务要求完成时间、各优化软件性能和优化软件任务情况等进行任务调度和分发，评判中心将各处理机得到的优化结果进行比较，并将最优结果反馈给用户。优化处理机上安装各种优化软件，这些优化软件可能是用不同的算法实现，也可能是同一算法软件实现中采用的参数不一样。中央数据库上存放用户数据、优化处理数据，其中优化处理数据经过一定时间的应用累积，可用于进行算法研究和对优化处理机上的软件性能进行评价。

　　4  应用前景

    在长期从事二维优化下料技术研究工作的基础上，我们所开发的二维优化下料软件已经在全国600多家企业中得到应用，为企业带来了明显的经济效益。在软件的实际推广应用中，由于优化软件的特殊性，软件只能保证在各种下料数据下的一个良好的数学期望值，但不能保证对每种下料数据都有相对于其他方式或软件更好的优化利用率。目前本文提出的优化软件应用方法已经在本单位处于实验阶段，实验结果证明，用本文提出的方法，可以得到单一软件无法得到的总体优化效果，随着优化软件种类的不断增加，优化效果将得到进一步的提高。随着Internet在我国各单位的进一步普及应用，我们经过实验阶段后基于该方法构建的优化服务网站将为需要二维优化下料技术的用户提供更多更优的服务。

    5  结论

    二维优化下料技术应用面很广，但由于下料算法的复杂性和下料方式的多样性，很难形成一套能够满足各种应用并取得良好优化效果的软件，阻碍了二维优化技术更好地发挥功效。本文提出了一种基于Internet的二维优化下料方法，该方法利用多种优化下料软件并行优化，通过Internet为用户服务，可以在不增加优化处理时间的情况下，取得比单一软件更好的优化效果，这将对二维优化下料技术进一步提高优化下料效果及其推广应用发挥积极作用。