基于赋时Petri网的装配序列规划符号求解  

A symbolic method for assembly sequence scheduling based on timed Petri net

作　　者：李凤英[1] 古天龙[1] 侯杰[1] 

机构地区：[1]桂林电子科技大学计算机与控制学院,广西桂林541004

出　　处：《桂林电子科技大学学报》2010年第2期146-149,共4页Journal of Guilin University of Electronic Technology

基　　金：广西自然科学基金(0832006Z)

摘　　要：赋时Petri网非常适合装配序列规划问题的建模,然而组合复杂性严重制约了基于赋时Petri网模型的装配序列规划问题的求解规模。OBDD能为Petri网的状态空间及装配序列规划过程中的数据提供符号表示,并在规划过程中实现隐式操作,有效地缓解了组合复杂性。通过将赋时Petri网中的赋时迁移用等价的赋时迁移结构代替,赋时Petri网转换为等价的普通Petri网,基于此提出符号有序二叉决策图OBDD装配序列规划算法,求解最优装配序列。Algorithms based on timed Petri net are efficient for solving the problem of assembly sequence planning（ASP）.However,they suffer from the state explosion problem.Both the marking vectors and the states of Petri nets can be formulated compactly by ordinary binary decision diagrams（OBDDs）;at the same time,the scheduling processes can be manipulated implicitly.As a result,the combinative complexity caused by the Petri net-based representation of assembly sequences can be alleviated efficiently.All the timed transitions in timed Petri nets were substituted by some technically designed timed transition structures.Then a symbolic assembly sequence scheduling algorithom based on ordinary binary decision diagrams（OBDDs） was presented.Compared with original algorithms,both the time performance and the space performance of the one presented in this paper were improved.

关 键 词：赋时PETRI网 装配序列规划 组合复杂性 有序二叉决策图 

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