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

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

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

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