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

摘要

赋时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 given out 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.