[發明專利]車間制造系統的啟發式二叉決策圖變量序優化表示方法

有效

• 申請號: 201710989077.X
• 申請日: 2017-10-22
• 公開（公告）號: CN107808214B
• 公開（公告）日: 2022-05-27
• 發明（設計）人: 黃波;丁高瞻;蔡志成;張皓明;楊余旺
• 申請（專利權）人: 南京理工大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/04
• 代理公司: 南京理工大學專利中心 32203
• 代理人: 朱顯國

本發明公開了一種車間制造系統的啟發式二叉決策圖(OBDD)變量序優化表示方法，包括以下步驟：采用Petri網對企業車間生產系統建模；計算Petri網各個庫所之間相互關聯度；以資源庫所為中心，依據庫所之間關聯度大小對庫所進行分組；采用深度優先策略尋找資源庫所對應分組及所有庫所的OBDD編碼順序。本發明以制造車間Petri網模型為對象，采用啟發式OBDD變量序優化技術，緩解了在系統模型分析中存在的狀態爆炸問題，具有有效減小模型表示結構、加快模型分析速度的優點。

技術領域

本發明涉及自動制造系統建模與控制技術，具體是涉及一種車間制造系統的啟發式二叉決策圖變量序優化表示方法。

背景技術

Pastor等建立了基于OBDD的Petri網符合分析方法，使用OBDD表示Petri網的庫所標識的特征函數，對Petri網的各種性能進行分析。OBDD的節點數對變量序非常敏感，同一函數在不同變量序下對應OBDD表的節點數可能具有線性和指數的差別。因此變量排序是OBDD應用中的重要問題。

M.Fujita提出的在一定范圍內交換變量的window算法，其時間復雜度和排序后OBDD節點的數量都依賴于窗口的大小k，k值越大，時間復雜度越高，節點數越少，但隨著k的不斷增大，其時間復雜度會趨于指數級別，并且排序效果改善很小(M.Fujita,Y.Matsunaga,and T.Kakuda.On Variable Ordering ofBinary Decision Diagrams forthe Application ofMulti-level Logic Synthesis.In Proceedings EuropeanDesignAutomation Conference,pages 50-54,March 1991.)。Rudell等提出的動態變量排序算法sifting已廣為應用，其核心思想為：對于給定的初始OBDD，首先把所有變量按照對應層次上的節點數降序排列，然后依該次序對每一個變量，在保持其它變量相對次序不變的情況下通過相鄰變量的交換操作改變該變量的位置，尋找一個使對應OBDD節點數最少的最佳位置。sifting算法可以得出局部較優變量序，但其時間復雜度高，且嚴重依賴初始變量序(Rudell R.Dynamic variable ordering for ordered binary decisiondiagrams.In:Proceedings of International Conference on Computer aidedDesign,1993.42～47)。

發明內容

本發明的目在于提供一種車間制造系統的啟發式二叉決策圖變量序優化表示方法，為Petri網的OBDD分析法找到一種快速有效的啟發式變量序，緩解Petri網在系統模型分析時的狀態組合爆炸問題。

實現本發明目的的技術解決方案為：車間制造系統的啟發式二叉決策圖變量序優化表示方法，包括以下步驟：

步驟1、使用Petri網子類S³PR網對車間制造系統進行建模；

步驟2、求取系統Petri網模型中各個庫所之間的關聯度矩陣；

步驟3、基于步驟2求得的庫所之間關聯度矩陣，以資源庫所為中心，對Petri網所有庫所分組；

步驟4、求取資源庫所對應分組的順序；

步驟5、基于步驟3和步驟4，采用啟發式規則生成系統Petri網模型的OBDD變量優化順序；

步驟6、基于步驟5得出的OBDD優化變量序，構建車間制造系統Petri網模型的OBDD。

本發明與現有的技術相比，其顯著的優點為：1)本發明采用OBDD符號化表示技術，有效減小系統模型表示的結構大小，并能加快模型計算分析的速度；2)本發明在OBDD建模的基礎上，利用啟發式方法，快速獲取系統模型表示的OBDD優化變量序，能進一步減小模型表示的結構，且系統優化變量序獲取速度明顯快于現有的非啟發式算法。