生成装配与或图的直接算法

Direct algorithm for the generation of assembly AND/OR graph

为了提高产品装配序列规划的效率,提出一种生成装配与或图的高效算法,直接模拟产品的装配过程。通过在装配与或图节点的数据结构中增加零部件的关联信息检查子装配间的关联关系,通过检查装配优先关系避免非法节点的生成,通过限定装配与或图节点的组合范围、分批地生成装配与或图节点以避免装配与或图节点的重复组合,整个装配与或图采用自底向上的方式生成。理论分析和实验比较的结果均表明,本文算法的时间复杂度明显低于现有算法,空间复杂度和现有算法基本相等。

To improve the efficiency of assembly sequence of product planning,a novel and efficient algorithm for generating Assembly AND/OR Graph（AAOG）was presented.This algorithm directly simulated the assembly process of a product.Association information among components was included in the data structure of AAOG＇s node to checked efficiently the liaisons among sub-assembly,and the assembly precedence was checked to avoid the generation of illegal nodes,and the combination ranges of nodes were limited and nodes were generated in batches to avoid the repetition of combinations.Then,the whole AAOG was generated in a bottom-up way.The results of the theoretical analysis and experimental comparison showed that time complexity of the algorithm was remarkably lower than existing algorithms,and space complexity of the algorithm was almost equal to existing algorithms.