基于边收缩的最优装配序列求解方法  

A Method for Generation the Optimal Assembly Sequence By Using Edge Contraction

作　　者：梁勇强[1] 

机构地区：[1]玉林师范学院计算机科学与工程学院,广西玉林537000

出　　处：《玉林师范学院学报》2014年第5期108-117,共10页Journal of Yulin Normal University

摘　　要：为确保最优装配序列的求解,本文提出一种新的最优装配序列求解方法.首先扩展装配有向图结点的信息为一个边被收缩图,在此基础上给出扩展的装配有向图的概念,接着通过连续的边收缩生成扩展的装配有向图.为了便于装配序列评价,又给出了装配任务有向图的概念,并将扩展的装配有向图转换成装配任务有向图,最后采用动态规划算法在装配任务有向图中搜索从初始任务到终止任务的最短路径以求解最优装配序列.To ensure the generation of the optimal assembly sequence, a novel algorithm for generating optimal assembly sequence is proposed. On the basis of the information extension of the node of assembly directed graph（ADG） based on edge contracted graph（ECG）, the notion of extended assembly directed graph（EADG） is presented firstly. And then, EADG is generated by iterative contraction of edges of ECG. To facilitate the assembly sequence evaluation, EADG is converted to assembly task directed graph（ATDG） after the notion of ATDG is presented. Finally, the optimal assembly sequence is generated by using the dynamic programming algorithm to search the shortest path from the initial assembly task to the final assembly task in ATDG.

关 键 词：装配有向图 边被收缩图 装配过程 动态规划 

分 类 号：TP391.73[自动化与计算机技术—计算机应用技术]