CAPP系统中工序工步排序研究的现状与发展

作者：常德高等专科学校 肖伟

欢迎访问e展厅 展厅 3 PDM/PLM/CAPP展厅 图文档管理系统, CAPP... CAPP这一课题的研究始于60年代后期，而将其正式命名为CAPP则是在发展史上具有里程碑意义的美国计算机辅助制造国际组织CAM—I(Computer Aided Manufacturing—International)于1976 年所推出的CAM— I’ S Automated Process Plannign系统。到目前为止，对于CAPP的理论研究与实际应用已取得了长足的进步。作为CAPP中的关键技术之一—工序工步排序，也已取得了一些进展。工序工步排序是工艺设计与否的关键，也是工艺设计的难点之一。它在很大程序上决定了CAPP 系统的应用水平，同时也是衡量CAPP系统智能化和实用化程度的一个重要标志。本文将简要介绍 CAPP中工序工步排序的发展过程，并对排序所采用的几种典型方法进行评述，最后在分析当前排序的理论与方法基础上，提出作者对工序工步排序未来发展趋势的看法。 一、工序工步排序的发展过程 CAPP的早期意图主要是建立包括工艺卡片生成、工艺内容存储及工艺规程检索在内的计算机国债系统。它并不进行工艺设计工作，而帮助减少工艺人员所作的事务性工作。这样的系统没有工艺决策能力和排序功能，因而不具有通用性。 真正具有通用意义的CAPP系统是1969年以挪威开发的AUTOPROS系统为开端，其后很多的 CAPP系统都受到这个系统的影响，如美国CAM—I的CAPP系统(1976年)、美国LockHeed公司的GENPLAN(1980年)、美国Metcut的AUTOPLAN(1980年)、美国OIR的MIPLAN(1980年)以及中国同济大学的TOJICAP(1982年)等等。这类系统的共同特点是在成组技术和数据库技术的基础上，利用零件的结构和工艺相似性，通过检索和修改零件族主样件的标准工艺而获得当前零件的工艺规程。从排序的角度来划分，这可以认为是一种“标准工艺法”。由于标准工艺是工艺人员事先拟定的，其工序工步间的逻辑关系已经确定，而对标准工艺的修改又仅仅是一系列的删减操作，不会改变工序或工步原来的排列顺序。所以，从本质上讲，这类系统的排序完全是由人工来完成的，是一种数据检索系统。 继“标准工艺法”之后的是所谓“自动排序”的创成式系统。该系统是将工艺决策知识用决策表、决策树或公理模型等技术来实现，实际上是把这种工艺决策逻辑用是非判断的决策形式固化在程序中，或采用数据文件结构由系统调入程序中，而零件的工艺规程是根据工艺数据库中的零件信息在没有人 工干预的条件下自动创成出来的，如西德Aachen工业大学的AUTAP、美国Purdue大学的TIPPS、美 国CAM—I的XPS—1等。由于工艺设计过程的复杂性和多样性，这种功能齐全、能够自动排序的 真正完全创成式系统的实现难度太大，至今也没有开发出来。上述系统充其量只能算是半创成型，即在系统中包含有一部分决策逻辑，而其关键部分—工序工步排序或采用前述的标准工艺法来实现或通 过人机交互方式来完成。如美国发表的CORE— CAPP系统就属于此类。 从80年代中后期到90年代初期，人工智能技术特点是专家系统得到广泛应用，开发出了的一大 批基于规则推理的专家系统。这些系统与以往系统的显著区别在于它们具有一个将工艺知识与经验以产生式规则表示的知识库和模拟工艺设计专家进行工艺决策的推理机。其基本原理都是通过零件的输人信息与系统的决策规则匹配。按照系统的推理方式和控制策略生成零件的工艺规程。就排序决策而言，尽管都是以规则的组织形式由系统激活来实现，但所采取的方式却各有不同。大体上可分为三类： 一是根据加工阶段的划分原则和各种加工方法之间的逻辑关系来构造排序规则。如叶军君的XJDCAP： 二是根据工艺理论中的基准原则(如基准先行、基准重合、基准统一等)、表面生成规律(如先粗后精、先主后次、先面后孔等)和工艺习惯来安排规则。有极少数的CAPP系统也能获得较好的排序方案。 最近几年，国内外研究人员对CAPP的工序工步排序理论与方法进行了广泛的研究和深入的控索，将人工智能技术、人工神经网络、面向对象方法和特征技术待引入到CAPP系统中，提出了一些适用于CAPP的系统富有特色的排序方法。吴会林通过建立工艺过程的标准AOV—网，采用拓扑排序算法生成零件的工艺路线；李建锋提出采用ARTI网络根据各种排序因素的能量大小(即重要程序)进行工序排序；马国强则采用“综合加权排序法”基本上达到了工序排序的目的；买立峰提出工艺规程的AOS树表示法，从而有助于工序工步排序的自动设计；赵学军等针对标准AOV—网和标准拓扑排序法的缺陷，提出了修改AOV—网和修正拓扑排序法的排序思路。上述研究人员的开发工作对工序工步排序研究起到了极大的促进和推动作用。 二、工序工步排序的理论与方法 机械制造中的工艺设计，由于受产品品种多样性、制造过程离散性、生产环境复杂性和系统状态模糊性的综合影响，使得工序工步排序变成一种极其复杂的决策过程。在传统机械加工中，通常是工序数目较多，一个工序内的工步数较少，工序排序是其关键；而在现代数控加工中，一般工序数目较少。一个工序内的工步数较多，有时在一次装夹下的工步数达到50以上，此时的工步排序成为关键，并且比之工序排序可能更为复杂、更加详细。目前，这方面的研究内容可以概括为以下二个方面。 1.排序理论的系统化和形式化 CAPP系统中采用的工序决策方式可以划分为三种类型、即计算决策、逻辑决策和创造性决策。其中某些决策内容(如工序尺寸计算、切削参数计算、机床与刀具选择等)理论成熟、内涵明确、规律性强，其工艺规则易于形式化表达。而另一些决策内容(如工序工步排序、定位基准选择、装夹方案确定等)则只有零散的实践经验可供参考，既不具有规律性，也不具有系统性，不仅缺乏科学基础，而且知识内容相互冲突，彼此矛盾，难以形式化，尤其是在有关排序的理论方面更是如此。这有必要加强排序的基础理论研究，使其从工艺处理中抽象出排序规则，以达到系统化、形式化的要求。 2．排序方法的应用研究 就目前的研究现状来看，工序工步排序在理论与方法上几乎没有实质性突破，众多的CAPP系统仍然采用传统的排序方法、即根据工艺准则分级分段进行排序，并由操作人员对最后结果进行修订。其主要问题一是难以提取决策知识，决策过程难以实现并缺乏柔性；二是系统的智能化、集成化水平不高，难以达到工艺规程的标准化和通用化。所以，总体上说，工序工步排序还处于经验决策阶段，仍需要操作人员参予决策。由于操作人员知识水平的不一致和生产实践经验的局限性，往往不能考虑到影响排序的各方面因素，因而编排的工艺路线往往不是最佳方案，基于于连好的方案都谈不上，已逐渐成为CAPP系统智能化、集成化的瓶颈之一。这是一个亟待解决的研究问题。 当前，在积极寻求更优秀、更实用的排序方法的同时，也不应排斥采用以逻辑推理为主的排序策略。但必须认识到：迄今的逻辑推理理论仍然很不完善，还没有一套完整的模糊推理理论、非单调推理理和柔性推理理论，因而有很大的局限性，应考虑采用其它的智能技术来弥补。 三、工序工步排序的研究与发展 事实已经证明， CAPP并不单纯是一个基于知识的决策系统。在很大程序上，它又是一个最优化 的过程。因此。单独采用工艺知识进行推理不能有效地解决工序工步排序问题，特别是当排序的规模较大、环境趋于复杂时，要寻找出最优方案，即使是资深的工艺设计师也难以胜任，更何况是广大的普通工艺人员。由此可见，工艺设计是一个极为复杂的智能过程，它是特征技术、逻辑决策、组合最优化等多种过程的复合体，不可能采用单一的数学模型来实现其所有功能。所以， CAPP今后的研究方向应该是基于知识的工艺系统与组合优化过程的有机综合，这样才有可能真正解决工序工步的排序问题。 组合优化是一个离散最优化问题，在规划、调度、资源分配、决策等问题中有着非常广泛的应用。但由于给合优化问题的计算复杂度高，属于NP(Nondeterministic Polynomial—bounded)“难”一类的问题，除了枚举一部分解决之外，没有更好的解法。事实上，工序工步排序问题就属于NT问题。当排序的规模较小时，可以采用传统的逻辑决策方式，一般能够得到较好的可行解，也可考虑采用运筹学的经典算法，如整数规划、动态规则、分支定界或切多面体等方法求解。当排序的规模较大时，由于组合的可行解数目呈指数函数增长，要全部枚举这些解决并找出最优的，实际上已不可能。例如，若有21个工步的排序问题，可能的排序方式共有21!＝5．1 x1019种，即使引入工艺约束，符合此约束的排序总数也是惊人的。 由于NP问题的以上特别，启发式方法被用来解决这类问题。这种方法是建立在经验和判断的基础上，尽量削减解的搜索范围，力求避免盲目搜索，同时又能得到较好的近似最优解。所以，组合优化与传统排序方法的本质不同就在于它是利用启发式搜索方法而非创成式方法来寻找合理的工艺路线。 组合优化问题求解的最基本方法是局部搜索法(Local Search简称， LS)，可对LS作如下描述： (1)用随机法、贪心法或其它方法产生一个初始解x1，把x1作为暂定解。并由x1定义解的集合 N(x1)，令k＝1。 (2)若N(x1)内有比x1更好的解x2，令x1，x2， k＝k+1，Goto(2)。 (3)若N(x1)内不存在比x1更好的解，输出暂定解，终止。 由于LS是一种局部最优解，在未搜索到的区域内，有可能存在着更好的解。为了改进局部搜索法的弱点，人们提出了以下一些改进方法： (1)从多个不同的初始解出发，从最终解中选择最好的一个。这就是多起点局部搜索法(Multi— Start Local Search简称， MLS)。 (2)在局部搜索过程中加入随机的行为就成为模拟退火法(Simulated Annealing简称， SA)。 (3)同时保留若干局部最优解，则是遗传算法(Genetic A1gorithm简称， GA)。它通过两个或多个解的交叉重组和单个解的变异来寻找整体最优解。 (4)在搜索过程中利用解的履历信息，从而调节后继的搜索过程。这就是(Tabu Search简称TS)。 上述各种搜索方法在工序工步排序这一类组合优化问题方面已经有所应用。例如有的将模拟退火算法应用于工步规划的原理，较好地解决了数控加工中心上的工步排序问题。但有关这方面的报道极少，而GA、 TS等应用于CAPP系统排序的论文还未见报道。这显然是今后一段时期应深入研究的方向，也是工序工步排序得已真正解决的发展趋势。 (end)

文章内容仅供参考 (投稿) (如果您是本文作者，请点击此处) (4/20/2005)