柔性制造系统中生产调度问题的零压缩二叉决策图算法  

Symbolic ZBDD-based algorithm for scheduling in flexible manufacturing systems

作　　者：李凤英[1,2] 古天龙[2] 

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

出　　处：《控制与决策》2010年第5期657-662,共6页Control and Decision

基　　金：国家自然科学基金项目(60903010;60903079);广西自然科学基金重点项目(0832006Z)

摘　　要：针对赋时有界Petri网模型下柔性制造系统的生产调度问题,给出了有界Petri网的零压缩二叉决策图表示方法,进而建立了此类生产调度问题求解的符号零压缩二叉决策图算法.该算法在求解过程中对状态空间及其搜索过程中的相关数据,采用零压缩二叉决策图表示,避免了状态和搜索的显式枚举,实现了隐式高效操作,有效地改善了算法的计算性能.实验结果表明了算法的有效性.To solve the production scheduling in flexible manufacturing systems（FMS） based on timed and bounded Petri net models,the bounded Petri net is represented symbolically by zero-suppressed binary decision diagrams（ZBDD）,and the symbolic ZBDD-based algorithm is developed.In this scheme,the marking vectors or states in Petri net are formulated compactly,and the search processes are manipulated explicitly.Thereby the time and space performances of searching Petri net are improved.The experimental results show the effectiveness of the symbolic algorithm.

关 键 词：柔性制造系统 赋时有界Petri网 生产调度 零压缩二叉决策图 符号算法 

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