摘要
赋时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.
出处
《计算机科学》
CSCD
北大核心
2012年第2期170-174,共5页
Computer Science
基金
国家自然科学基金项目(60563005
60243002
61063002)
广西可信软件重点实验室开放基金资助
关键词
赋时PETRI网
装配序列规划
零压缩二叉决策图
Timed Petri nets
Assembly sequence planning
Zero-suppressed binary decision diagram
