一种基于赋时Petri网和ZBDD的装配序列规划方法  

Timed Petri and ZBDD Based Approach for Assembly Sequence Planning

作　　者：李凤英[1,2] 古天龙[2] 常亮[2] 徐周波[2] 

机构地区：[1]西安电子科技大学电子工程学院,西安710071 [2]桂林电子科技大学计算机科学与工程学院,桂林541004

出　　处：《计算机科学》2012年第2期170-174,共5页Computer Science

基　　金：国家自然科学基金项目(60563005;60243002;61063002);广西可信软件重点实验室开放基金资助

摘　　要：赋时Petri网为装配序列规划提供了有效的建模方法,但其在求解最优装配序列时受到组合复杂性的严重制约。零压缩二叉决策图(ZBDD)是处理大规模组合集合和0-1稀疏向量的一种有效符号技术,能够有效缓解组合爆炸问题。将赋时Petri网与ZBDD结合起来,给出了一种求解装配序列最优解的有效方法。首先通过转换算法将赋时Petri网转换为等价的普通Petri网,接下来给出普通Petri网可达状态及迁移引发函数的ZBDD表示方法,最后基于ZBDD给出最优装配序列求解算法。实例验证表明,该算法在求解过程中通过隐式符号操作实现了Petri网的可达状态搜索,有效缓解了计算过程中的组合复杂性。Timed Petri net is one of efficient modeling formalisms for assembly sequence optimization problems,but the state combination complexity renders it hard and even impossible for large scale assembly sequence optimization problems to be solved.Zero-suppressed binary decision diagram（ZBDD） is an efficient symbolic technique to represent and manipulate the combination sets and 0-1 sparse vectors.An algorithm for selecting the best assembly sequence was givenout based on timed Petri net and ZBDD.Firstly,the timed Petri net model of assembly was transformed into equivalent ordinary Petri net using a transformation algorithm.And then an approach of representing the reachable states set and transation firing function of Petri net by ZBDD was given out.Henceforth,a symbolic ZBDD based algorithom for selecting the best assembly sequence was developed.The experimental tests give the proof that the ZBDD based algorithm alleviates the computing complexity by using implicitly symbolic manipulation to search reachable states of Petri net.

关 键 词：赋时PETRI网 装配序列规划 零压缩二叉决策图 

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