三個自動化製造系統偵查法則設計方法的計算複雜度比較

Abstract

對描述自動化製造系統的互動行為來說，歐氏記號圖是一種有效的控制模式。為了能夠及時的偵測出自動化製造系統之故障，必須要從歐氏記號圖中設計獨立的偵查法則。根據擬陣理論，最近發展出來三種偵查法則的設計方法：圖形擬陣、可表達擬陣與覆點擬陣。圖形擬陣設計方法是從圖形結構觀察出偵查法則。可表達擬陣設計方法係直接從法則矩陣計算出偵查法則。覆點擬陣設計方法則是將歐氏記號圖轉換成双集圖，再從其路徑的匹配中選出偵查法則。本論文由計算複雜度方面分析了三種方法，此外也驗證並比較此三種設計方法的優缺點。

Eulerian marked graph is an effective control model for describing the concurrent behavior of a given automated manufacturing system. Also for detecting the malfunction of the given automated manufacturing system in a real-time way, it is necessary to design independent monitor rules from the specified Eulerian marked graph. Recently three useful monitor rule design methods based on matroid theory have been developed: graphic matroid, representable matroid, and transversal matroid. The graphic matroid method is to pick the monitor rules out visually from its graphic structure. The representable matroid method is to generate the monitor rules directly from computing its rule matrix. The transversal matroid method is to transform the Eulerian marked graph into a bipartite graph; then the monitor rules are screened out from their matching paths. In this thesis, three kinds of methods are analyzed from a computational complexity viewpoint. Moreover the advantages and disadvantages of each design method are examined and compared.