基于复合装配图进行装配序列规划的研究

摘要/Abstract

摘要： 为了构建一个有效且便于使用的装配序列规划系统，给出了一个开放式装配模型——复合装配图，以有向装配连接图表述零件之间的优先关系，利用检查有向圈、删除冗余有向边确保该图正确、简洁。在此基础上，用无向边连接没有优先关系的零件，并根据装配代价和装配可行性对有向边、无向边赋权值，得到复合装配图。将装配序列规划描述为在复合装配图中求解特殊的最优H回路，并且基于分支定界法给出了满足优先关系、装配可行性、装配代价优化的装配顺序规划算法。最后通过实例验证了算法的有效性。

关键词: 复合装配图, H回路, 分支定界法, 装配序列规划

Abstract: To construct a system of assembly sequence planning, a compound assembly graph (CAG) model was proposed. The graph was created with four steps: establishing a directed assembly graph (DAG) to describe the precedence relations between components; keeping DAG correct and compendious by checking precedence conflict and deleting redundant information; adding undirected arcs between each pairs of parts that have no precedence relations; weighting all arcs with assembly cost and feasibility. Then, the assembly sequence planning was converted into searching a special optimal H-circle in CAG. A branch-and-bound algorithm was presented to find an optimal assembly sequence that satisfied the precedence constrains and assembly feasibility. Finally, the effectiveness of the strategy was illustrated by an example.

Key words: compound assembly, H-circle, branch-and-bound, assembly sequence plan

中图分类号:

TP391

谢龙，付宜利，马玉林. 基于复合装配图进行装配序列规划的研究[J]. .

XIE Long, FU Yi-li, MA Yu-lin. Assembly sequence planning based on compound assembly graph[J]. .

参考文献

［1］HOMEM de Mello L, LEE S, EDITORS. Computer-aided mechanical assembly planning[M]. Kluwer,1991.

[2]FAZIO T L De，WHITNEY D E. Simplified generation of all mechanical assembly sequences[J]. IEEE Journal of Robotics and Automation, 1987,3(6):640-658.

[3]BAI Fangni, LI Lei,et al. Research on generation of assembly sequences based on decomposition of graph[J]. Mechanical Science and Technology，2000,19(6):1035-1037(in Chinese).[白芳妮,李磊,等.基于图分解的装配序列生成算法研究[J].机械科学与技术, 2000,19(6):1035-1037.]

[4]CHANG Kaihsiung, WEE W G.A knowledge-based planning system for mechanical assembly using robots[J]. IEEE Expert, 1988, 3(1):18-30.

[5]LAZZERINI B，MARCELLONI F. A genetic algorithm for generating optimal assembly plans[J].Artificial Intelligence in Engineering，2000,14(4):319-329.

[6]HAN Shuihua, LU Zhengding, CHEN Chuanbo. Automatic assembly process planning based on geometric inference[J]. Journal of Computer Aided Design and Computer Graphics，2000,12(7):528-532(in Chinese).[韩水华,卢正鼎,陈传波.基于几何推理的装配序列自动规划研究[J].计算机辅助设计与图形学学报，2000,12(7):528-532.]

[7]JONES R E, WILSON R H. On constraints in assembly planning[J]. IEEE Transactions on Robotics and Automation，1998,16(6):849-863.

[8]DINI G，SANTOCHI M. Automatic sequencing and subassembly detection in assembly planning[J]. Annals of the CIRP, 1992, 41(12):3447-3465.

[9]LIU Shixin, WANG Mengguang, TANG Jiafu. The optimization algorithms for solving resource-constrained project scheduling problem:a review[J]. Control and Decision, 2001,16(11):647-651(in Chinese).[刘士新,王梦光,唐加福.资源受限工程调度问题的优化方法综述[J].控制与决策，2001,16(11):647-651.]

[10]XIAO Weishu. Graph theory and the algorithm[M]. Beijing：Aviation Industry Press，1993.221-247(in Chinese).[肖位枢. 图论及其算法［M］. 北京：航空工业出版社，1993.221-247.]

[1]	王豆,段晓强,邵晓东,高峰. 一种反射面天线面板装配优化方法[J]. 计算机集成制造系统, 2020, 26(6): 1679-1690.
[2]	刘江伟,郭宇,查珊珊,王发麟,章诗晨. 基于改进粒子群算法的多工位装配序列规划[J]. 计算机集成制造系统, 2018, 24(第11): 2701-2711.
[3]	王豆,邵晓东,刘焕玲,葛晓波. 基于混合算法的反射面天线面板装配序列规划[J]. 计算机集成制造系统, 2017, 23(第6期): 1243-1252.
[4]	包云霞,鲁法明,王艳晓,段华,林泽东. 向量目标整数线性规划问题及其在工作流网分析中的应用[J]. 计算机集成制造系统, 2017, 23(第5期): 947-954.
[5]	徐周波,肖鹏,古天龙,宁黎华. 基于混沌混合算法的装配序列规划[J]. 计算机集成制造系统, 2015, 21(第12期): 3200-3208.
[6]	刘翊,李世其,王峻峰,曾洪梅,鲁明上. 产品分层分级的交互式拆卸装配序列规划[J]. 计算机集成制造系统, 2014, 20(4): 785-.
[7]	曾冰,李明富,张翼. 基于改进萤火虫算法的装配序列规划方法[J]. 计算机集成制造系统, 2014, 20(4): 799-.
[8]	王松,孙振忠,郭建文,张智聪. 基于混合蛙跳算法的复杂产品装配序列规划[J]. 计算机集成制造系统, 2014, 20(12): 2991-2999.
[9]	刘亚杰,古天龙,徐周波,常亮. 基于改进遗传编程的并行装配序列规划[J]. 计算机集成制造系统, 2013, 19(06 ): 1238-1248.
[10]	张志英，李殿勤. 船舶平面分段的非完全混合流水线调度[J]. , 2012, 18(11): 0-0.
[11]	安玉伟,,,严洪森,. 一类两阶段生产系统生产计划与调度的集成优化[J]. , 2012, 18(04): 0-0.
[12]	赵燕伟，盛猛，苏楠，邢莉. 基于关联函数的复杂产品装配序列规划方法[J]. , 2011, 17(06): 0-0.
[13]	王成恩,，于宏，于嘉鹏,，张闻雷,，袁辉,. 复杂产品装配规划系统[J]. , 2011, 17(05): 0-0.
[14]	王成恩,，于宏，于嘉鹏,，张闻雷,，袁辉,. 复杂产品装配规划系统[J]. , 2011, 17(05): 0-0.
[15]	常亮，刘华，古天龙，韦林. 基于启发式DCPM-FGA的产品装配序列规划[J]. , 2011, 17(02): 0-0.