基于OBDD的符號Petri網(wǎng)分析與FMS調度算法研究.pdf

1、Petri網(wǎng)是一種適宜描述和研究分布式、異步、并發(fā)現(xiàn)象的系統(tǒng)工具,已經(jīng)在計算機網(wǎng)絡、通訊系統(tǒng)、計算機體系結構、分布式系統(tǒng)、電路設計與驗證、生產過程控制、自動化制造系統(tǒng)和協(xié)議工程等諸多領域得到廣泛應用?；?Petri網(wǎng)的生產調度就是 Petri網(wǎng)應用研究的重要問題之一。然而,受狀態(tài)組合復雜性影響,常規(guī)的幾種Petri網(wǎng)分析方法都存在較大的局限性,能處理的問題規(guī)模及復雜度相當有限,這嚴重制約了 Petri方法的實用性。符號計算方法是解決狀

2、態(tài)組合復雜性問題的一種新的有效技術。
　　本文對Petri網(wǎng)的常規(guī)分析方法、基于Petri網(wǎng)的生產調度問題的傳統(tǒng)求解方法以及有序二叉決策圖(OBDD-Ordered Binary Decision Diagram)等進行了系統(tǒng)分析和深入研究;在深入探討Pastor等給出的有界Petri網(wǎng)符號分析方法的基礎上,對其中的核心算法—映像(image)計算算法進行了改進,給出了一種不需額外引入另一套變量的有界Petri網(wǎng)image計算算法

3、;并把Petri網(wǎng)符號分析技術和基于Petri網(wǎng)的FMS調度問題結合起來進行了研究,給出了一種有界Petri網(wǎng)模型下FMS生產調度問題的符號OBDD求解算法。此外,本文還對有界Perti網(wǎng)符號分析技術進行擴展,給出了針對賦時Petri網(wǎng)的一種符號分析算法。實驗結果表明:基于OBDD的Petri網(wǎng)符號分析算法及FMS生產調度問題的符號求解算法可以有效改善問題的空間復雜度,在一定程度上緩解了問題的狀態(tài)組合復雜性,能處理較大規(guī)模Petri網(wǎng)模