基于赋权图的复杂产品装配序列优化方法研究

The assembly sequence optimization problem is one of the NPC (NP complete) problems. The asembly sequence optimization based on the weighted graph will be researched.Three main contents are concerned, (1) The assembly qualitative constraints and the quantitative constraints concluding the assembly feasibility and cost relevent to the adjacent parts will be categorized and represented in the graph, the weighted graph of assembly will be conceived to support the assembly sequence optimization of complex products; (2) The factors affecting the assembly cost of the assembly sequences,the qualitative constraints and the quantitative constraints restricting the parts or components to generate the optimum assembly sequences of the complex products will be focused on, and the objective function, qualitative and quantitative constraints of assembly sequences will be formulated and integrated into the optimization model of the assembly sequence; (3) The characteristics and computation complexity of the graph (tree) polynomial search algorithms will be researched, and the polynomial appropriation algorithms or polynomial algorithms to resolve the optimization model of assembly sequence will be proposed through improvement or combination of these graph (tree) search algorithms; The feasibility and effectiveness of the introduced methods will be verified and tested with concrete instances. The objective of the research is to discover the fundamental rules or displines followed by the parts or components to turn into the optimum assembly sequences, and propose the polynomial algorithm or polynomial approximation algorithm to resolve the optimization model of the assembly sequence, and an applicable approach to tackle the assembly sequence optimization problem of complex products will be formed.

复杂产品装配序列优化本质上属于约束条件下的NPC问题，开展基于赋权图的复杂产品装配序列优化方法研究。包括：（1）研究决定装配体中相邻零部件装配可行性与装配成本的定性（推理）和定量（计算）约束条件，以及它们在赋权图中的表达方法，建立支持复杂产品装配序列优化的装配体赋权图模型；（2）研究影响装配序列装配过程成本的因素与复杂产品零部件生成最优装配序列的定性、定量约束条件，以及它们在装配序列优化模型中的表达方法，建立较为完备的装配序列优化模型，为复杂产品装配序列优化奠定理论基础；（3）研究图（树）多项式搜索算法并进行改进，建立装配序列优化模型求解的多项式算法或多项式近似算法，同时开展基于算例的模型和算法验证研究。通过研究，揭示复杂产品零部件生成最优装配序列遵循的规则或规律，提出复杂产品装配序列优化模型求解的多项式算法或多项式近似算法，为复杂产品装配序列优化这类NPC问题求解开辟一条新的渠道。

装配序列优化属于制造自动化领域内的组合优化问题，这类问题由于最优解搜索空间随着问题规模成指数增长而至今难以求解。当前的方法只能获得小规模问题的最优解，对于大规模问题，不能保证获得最优解。因此，开展这类问题的求解方法研究，就制造领域来讲，对于促进装配自动化的发展，意义重大。.课题研究首先从建立装配体赋权拓扑图模型开始。装配体赋权拓扑图模型包含多种装配约束，这些装配约束被分为定性和定量约束。定性约束包括零部件之间的装配拓扑关系、几何约束和部分装配工艺约束。定性装配约束统一采用bool变量表示，用于推理出可行的装配序列。定量装配约束包括影响装配成本的功能、结构和部分工艺约束，采用FAHP方法量化，作为启发式信息引导算法搜索最优装配序列。.第二部分研究并建立了装配序列优化模型。基于装配体赋权图，首先建立了装配序列线性规划模型，各种线性规划算法和多种启发式算法都可以求解该优化模型。同时，对最优装配序列定量约束和相邻零部件定量约束之间的关系进行了探索，推导出四点三线不等式，该不等式揭示了零部件在定量约束条件下转化为局部最优装配序列遵循的规律。四点三线不等式的另一作用是降低最优解的搜索空间。通过实验证明：该不等式起到加速算法搜索出最优解和近似解的积极作用。.第三部分研究并设计出几类针对装配序列优化问题的算法。基于装配体赋权图，首先设计出MST-based多项式算法，该算法的计算复杂度为O(n3)。原则上讲，任何复杂装配序列优化问题均可以采用该算法求解。通过实验验证，该算法在装配约束限制下，能够快速地搜索到最优装配序列。另外，将四点三线不等式并入到模拟退火、蚁群算法和遗传算法内，设计出多项式近似算法。实验结果表明：即使这些算法不能搜索到最优解，但算法性能得到很大提升，不但近似解的质量大大提高，计算时间也有所降低。