[發明專利]基于有色Petri網的FMS生產仿真分配方法

在審

• 申請號: 201410105959.1
• 申請日: 2014-03-20
• 公開（公告）號: CN104463332A
• 公開（公告）日: 2015-03-25
• 發明（設計）人: 張衛星;陸文灝
• 申請（專利權）人: 蘇州工業職業技術學院;張衛星
• 主分類號: G06N7/06
• 分類號: G06N7/06
• 代理公司: 南京蘇科專利代理有限責任公司 32102
• 代理人: 陸明耀;陳忠輝

技術領域

本發明涉及一種仿真方法，尤其涉及一種基于有色Petri網的FMS生產仿真分配方法。

背景技術

就現有的生產仿真規劃來看，由于FMS具有離散、并行、路徑可變、資源競爭、批量可變等眾多重要特性，使得運用傳統方法很難準確的對其進行建模。Petri網是一種強大的DES建模工具，可以很好的表示系統中的動態性，并發關系，資源約束等。由于其既有易于理解的圖形化界面，又有較為豐富和嚴密的數學分析方法，因此Petri網被廣泛的應用在FMS的生產過程建模及生產調度仿真。

在目前的研究中，基于Petri網的生產調度有兩種實現方法：

第一種方法將調度問題轉換為狀態空間搜索問題。只要狀態空間有界，理論上一定可以找到最優解。但是當系統規模增大時，Petri網的狀態空間會呈爆炸式增長，計算狀態空間所需的存儲空間和運算求解時間將變得無法接受。使用第一種思路無法解決大規模系統的調度問題。

第二種方法利用了調度領域已有的研究成果，并發揮出Petri網的圖形表達能力，可較好地解決實際調度問題。然而，由于Petri網節點語義單義，用Petri網模型難以實現復雜的調度算法，在建立調度系統時，需要編制專用的軟件平臺支持Petri網建模和調度，無法利用已有的Petri網軟件，系統實現的難度與工作量較大。

Jensen提出了彩色Petri網的概念，彩色Petri網通常簡稱為CPN，特點是把系統中具有類同行為特性的元素歸屬到一個庫所節點或一個變遷節點中，并通過定義色彩集，使得其中的托肯能夠互相區別開來，從而使整個網的結構得到很大程度的簡化。另外，彩色Petri網還支持遞階的建模方法，允許我們在不同的層次上對系統進行抽象和建模，為我們的建模以及模型的修改、維護帶來了方便，特別是在描述復雜的大規模系統時，彩色Petri網更能顯示出明顯的優越性。可是，對于系統的分析卻變得更加復雜，因為雖然網的結構是簡化了，可是整個系統的狀態空間并沒有變小。而且，很多基本Petri網的分析方法并不能，或者說很難直接用于彩色Petri網的分析當中來。因此，人們開發了很多專用工具來支持CPN的建模和分析工作。丹麥的奧胡根大學和美國宇航局于2000年4月聯合推出的基于CPN的仿真軟件CPN?tools，該軟件支持標準元語言(standard?ML，SML)，本文詳細介紹了使用CPN實現FMS生產調度系統的防死鎖的方法。

相關理論介紹：

CPN的定義為：CPN=（Σ，P，T，A，N，C，G，E，I），該式中，Σ為有限類型集，亦稱為顏色集；P為有限庫所集，庫所具有顏色，庫所中包含的數據稱為token；T為有限變遷集；A為有限有向弧集，滿足P∩T=P∩A=T∩A=N為節點函數；C為顏色函數；G為變遷守衛函數；E為有向弧表達式；I為初始化函數。

（1）庫所

有三種標志：名字、類型和初始標志。名字（Name）用來區分其他庫所，類型（Place?type）用來說明放置托肯的顏色，初始標志（Init?mark）表示系統初始狀態時該庫所放置托肯的數目。

（2）變遷

有四種標志：名字、守護、時延和行動代碼。守護（Guard）為CPN?ML的布爾表達式，時延（Time?delay）為正整數或實數表達式以“@＋”開頭，行動代碼（Action）為CPN?ML代碼，它執行在變遷觸發時。

（3）有向弧

庫所和變遷間用帶箭頭的弧連接起來，弧上的標識表示當該變遷發生時，托肯隨之變化。

SML是一種函數式程序設計語言。SML的程序由函數組成。通常的Fortran、Pascal、C等高級語言屬于過程式語言，過程式語言的設計面向命令，命令的執行過程包含了狀態，而SML的設計面向表達式，其目的只是為了數值求解。SML程序不關心機器的狀態，如內存分配、垃圾收集等存儲管理由編譯器自動完成。SML具有惰性求值、模式匹配、多態類型等特性。用SML編寫的數學計算程序相比過程式語言要簡單而高效。

SML函數有如下形式：

fun?id?pat1=exp1

id?pat2=exp2

id?patn=expn。

id是函數的名稱，pat是形式參數，exp是函數體。函數體可以是一個簡單的數字，也可以是一段代碼。SML函數可以有多個模式的參數，SML會根據輸入的參數自動選擇合適的函數體。CPN?Tools使用SML實現對顏色集和函數的定義。CPN的顏色集使用了SML中的數據類型。CPN中的有向弧函數和變遷守衛函數使用SML編寫。

發明內容