1、生產系統建模與仿真Production System Modeling & Simulation 面向工程實際的應用型的基礎性課程，是工業工程專業的主導課程。課程介紹從課程的題目中可以看出： 離散系統建模與仿真其對象是：離散系統生產系統是一個典型的離散系統。物流系統也是一個離散系統。目的是：仿真。即用一種抽象的、能夠反映系統 研究本質的“虛假”系統，來模擬實際系 統。而這虛假系統就是系統模型。課程性質：征求答案什么是仿真？什么是離散系統的仿真？為什么需要做仿真？何時需要做仿真？如何進行仿真？仿真要做那些準備工作？仿真的可信度如何評價？對仿真模型如何作評價？你知道的仿真軟件有哪些？各自具有哪些特

2、征？你希望通過本課程的學習獲得些什么？課程試圖解決的問題：離散事件系統建模與仿真的基本原理離散事件系統建模與仿真的方法Petri網建模與仿真課程的先修課程：生產運作與管理運籌學計算機編程與應用技術概率論與數理統計課程的考核方法： 完成相關作業及期末考核。課程介紹課程主要內容：課程主要內容構成第一章 離散事件仿真的概述第二章 離散事件仿真的分析第三章 離散事件仿真的案例分析第四章 離散事件仿真的邏輯分析 Petri網第一章 離散事件仿真的概述 1.1 離散事件系統仿真的基本概念1.2 生產系統仿真的特征1.3 服務系統仿真的特征 1.4 離散系統仿真的基本步驟 1.1 離散事件系統仿真的基本概念

3、什么是系統？ 系統是按照某些規律結合起來的，相互作用、相互依存的所有元素的集合。系統有哪些種類？連續系統 & 離散系統 變量狀態靜態系統 & 動態系統 時域狀態確定系統 & 隨機系統存在隨機變量單變量系統 & 多變量系統 自由度數量1.1 離散事件系統仿真的基本概念什么是系統仿真(Systematic Simulation)?仿真：對現實中的現象通過某種抽象，建立表達現實變化規律或特征的模型，運用一定的手段加以描述，這就是仿真。系統仿真：首先針對真實系統建立模型，然后在模型上進行試驗，用模型代替真實系統，從而研究系統性能的方法。 系統仿真將能一一仿效實際系統的各種動態活動，并把系統動態過程的狀

4、態記錄下來。最終得到用戶所關心的系統統計性能。1.1 離散事件系統仿真的基本概念為什么要采用系統仿真?系統所涉及到的專業知識較為廣泛，如：機械、生產管理、人事管理、產品設計、生產工藝等現實問題的規律是復雜的，一般很難用一確定的數學方程或數學函數顯性地或隱性地表達。科學技術的發展難以適應生產系統研究的需要 仿真是系統特征無法用數學方程、數學函數描述時，為了研究系統特征所采用的一種研究方法。我們可以這樣說：仿真是一種“不得已而為之”的方法1.1 離散事件系統仿真的基本概念系統仿真方法適用怎樣的領域？系統仿真的方法適用于任何的領域工程類非工程類機械電子化工交通管理經濟政治1.1 離散事件系統仿真的基

5、本概念系統模型有哪些？系統模型確定型模型隨機型模型靜態動態靜態動態連續離散連續離散離散事件仿真蒙特卡洛仿真什么是離散事件系統？ 離散事件系統是包含事件的發生在時間或空間上都是離散的，例如交通管理、生產自動線、計算機網絡、通信系統和社會經濟系統都是離散事件系統。 離散事件系統定義為一組元素(實體)的集合，為了達到某些目的，這些元素以某些規則相互作用、關聯而集合在一起。例如制造系統由機器、部件以及操作工人組成，銀行系統由出納員和顧客組成。 離散事件系統的變量通常用狀態變量表示，如：實體的發生與不發生；事物的計數等等。1.1 離散事件系統仿真的基本概念離散事件仿真模型的特點 -隨機型：具有隨機性的狀

6、態變量 -動態性：隨時間演變是模型的重要特征 -離散事件：主要的變化發生在離散的時間點上1.1 離散事件系統仿真的基本概念事件的發生在時間和空間上都是離散的。系統的數字仿真則經常是面向事件的離散事件系統定義為一組元素(實體)的集合，為了達到某些目的，這些元素以某些規則相互作用、關聯而集合在一起。離散事件系統狀態變量僅僅在可數的一些時間點上才有變化 。系統變量是反映系統各部分相互作用的一些事件，系統模型則是反映這些事件狀態的數集，仿真結果是產生處理這些事件的時間歷程。 在離散事件系統中，各事件以某種順序或在某種條件下發生,并且大都是隨機性的，不能用常規的方法加以研究。 連續系統事件的發生在時間和

7、空間上都是連續的。在連續系統的數字仿真中，時間通常被分割成均勻的間隔，并以一個基本的時間間隔計時。在連續系統仿真中，系統動力學模型是由表征系統變量之間關系的方程來描述的。仿真的結果為系統變量隨時間變化的時間歷程。連續系統與離散系統有何區別？1.1 離散事件系統仿真的基本概念離散事件仿真時鐘的演變方法有哪些？時間離散 系統只在一些特定的時刻，即=t1 , t2, 上被考察。通常，為了便于研究，各時間間隔選定為整常數，t=常數。 事件離散 系統狀態的變化，即事件時刻是不連續的、跳躍式的， t= ti+1-ti，i，ti為事件發生時間。 1.1 離散事件系統仿真的基本概念l某些系統的建模困難，如，對

8、于大比例系統模型，建模會變得十分復雜，程序的編寫與程序的運行都是十分艱巨的。但是隨著優質的仿真專業軟件的誕生，對于這樣系統的仿真日趨簡便。l仿真需要大量的計算機機時。這一問題隨著計算機技術的發展正在逐步得到解決。l仿真需要大量實際的、準確的數據，這是一般企業所難以提供的，因此對仿真結果的準確性帶來了影響，導致了人們對仿真能力的懷疑。 總之，正是由于上述的種種因素，是人們對仿真留下了不好的印象。這里還要說明的是：仿真只是計算機編程的一種游戲，游戲的規則來自于問題的本身，游戲的范圍也是問題所約定的。 離散事件仿真運用存在哪些阻礙？1.1 離散事件系統仿真的基本概念離散事件仿真模型如何建立？如何為一

9、個離散事件系統建立一個模型確定一個系統目標或仿真目的建立概念性模型轉換為一個詳細模型制定仿真規則轉換為一個計算機計算模型編制程序代碼模型的運行檢驗特例檢驗模型的有效性檢驗模型檢驗、可信度檢驗典型事件的多次重復仿真循環過程1.1 離散事件系統仿真的基本概念離散事件仿真模型的三層次模型概念模型層極其概念性的層次模型（通常是語義性的系統描述）模型是如何構成的？什么是模型的狀態變量，哪些是動態變量，哪些是重要變量？詳細模型層模型的書面整理模型包括哪些方程，哪些偽隨機數，哪些輔助變量等模型參數如何輸入？計算模型層計算機程序通用編程語言或仿真語言1.1 離散事件系統仿真的基本概念系統與系統模型的實質關聯是

10、什么？系統：研究的本體系統模型：為研究系統所收集的有關信息的集合。通過研究系統模型來揭示系統的性能。 它和“系統”的定義比較，兩者都是集合，系統是以某些規律結合起來、有相互作用的元素組成；而系統模型是為了研究其結合規律相互作用所收集的有關信息。因為收集的信息有詳細、粗略之分，加上收集方法的差異和研究目的的不同，因此對于同一個系統就會出現多種不同的系統模型。模型是為系統服務的，因此，所揭示的性能規律應該是穩定的。1.1 離散事件系統仿真的基本概念離散事件仿真的輸入數據該如何收集和處理？仿真的輸入數據來源于事件采集穩定的數據仿真的輸入數據應該與實際數據有同樣的變化規律擬合度檢驗仿真的輸入數據應當是

11、相互獨立的相關性檢驗1.1 離散事件系統仿真的基本概念離散事件仿真的輸出數據應該有哪些分析？仿真結果的可信度分析仿真運行的效率分析仿真結果的性能分析離散事件系統仿真模型的簡例 某一個工作人員每日的工作是處理文件，他從每天開始工作時即處理文件，直至文件處理完畢或工作結束，每一個文件處理完畢后開始下一個文件的處理，工作間隔一小時休息一次，休息時間為5分鐘，但必須是在一個文件處理完畢之后。假設不考慮當天收到的文件，那么文件的數量可以預置，并隨著每個作業的完成遞減，直至為零。1.1 離散事件系統仿真的基本概念實例求解實例目標：了解仿真求解方法：手工仿真求解平臺：Excel求解原理：每個文件的處理時間（

12、工作時間tw）是一個隨機過程，符合一定的概率分布；該工作人員一上班就開始處理文件，所以第一個文件處理的開始時間就是仿真的開始時間（0時刻），后續文件的開始時間tf上一文件的結束時間或休息后的時間；每一個文件處理的結束時間文件處理的開始時間文件處理時間；設置一項統計量：累計工作時間tc=休息后的工作時間之和。當tc 1小時，則置為零，同時標識一次休息；仿真時間推進5分鐘。1.2 生產系統仿真的特征產品工藝技術與生產管理的結合相同的結果可以有不同的生產工藝生產管理策略對生產運作產生何種影響穩定的生產過程生產流程的穩定生產時間規律化變化生產過程存在不確定變化人工干預生產作業的不確定變化及學習變化機器

13、設備的不確定故障停機1.3 服務系統仿真的特征服務技術與服務管理的結合相同結果可以有不同的服務流程服務策略對服務運作產生何種影響客戶化的服務過程服務流程隨著客戶需求而改變服務時間的不確定變化服務過程存在不確定變化服務流程的不確定服務時間的不確定服務資源配置的不確定客戶數量、需求的不確定1.4 離散系統仿真的基本步驟明確離散系統仿真的需要解決的問題系統運作的流程（確定流程或可能流程）系統運作的管理策略運作規則系統的概念性建模：明確系統構成的元素系統的詳細建模：明確系統各元素的參數系統運行編程：根據管理策略形成系統的運行規則系統試運行系統模型的有效性檢驗和可信度檢驗系統正式運行第二章 離散事件仿真

14、的分析2.1 隨機數的產生2.2 離散事件仿真建模2.3 輸入數據分析2.4 輸出數據分析2.1 隨機數的產生為什么要產生隨機數?平時我們遇到的隨機數符合怎樣的分布？隨機數生產的方法有哪些？ 隨機事件是所有不確定事件中唯一可以分析的一種事件形式。因此，對于諸多不能明確解析的實際系統中最常見的就是隨機系統，隨機系統的運行首要解決的問題就是產生隨機數。（0，1）均勻分布的隨機數。 線性平移法（適用于均勻分布的隨機數產生） 同余法（適用于均勻分布的隨機數產生，常用方法） 逆變換法（密度函數的反函數可求的狀況） 舍取法（任意給定分布） 組合法（標準分布組合形成的復雜分布） 經驗生成法（特殊的常用分布，

15、運用經驗公式產生）2.1 隨機數的產生（0，1）隨機數的檢驗數字特征檢驗分布均勻性檢驗獨立性檢驗服從N(0，1)在給定顯著性水平后，即可根據正態分布確定臨界值，據此判斷與理論平均值及與X2理論平均值之差異是否顯著，從而決定能否將產生的隨機數看作是(0，1)均勻分布隨機變量的N個獨立取祥值。 服從自由度為k-1的2分布服從N(0，1)2.2 離散事件仿真建模排隊系統：由服務機構（服務模式）（可以是服務臺、加工機器、搬運設備等）、到達模式及排隊規則組成的集合。庫存系統：由訂單到達模式、訂單規模、補貨數量、交貨期及補貨策略（盤庫間隔、到貨規則）組成的集合。流程系統：由特定的一簇服務對象按照其自有的運

16、作流程（順序及滯留時間）將對應的服務機構（排隊系統、庫存系統）有序地連接在一起組成的集合。前后事件多對一 前后事件一對多 前后事件多對多 事件的返回 離散事件系統事件的合并 事件的拆分 離散事件系統 設備可用性。設備可以加工工件的前提是設備是可用的，設備可用的必要條件有：（1）當前時刻是生產系統工作日志所規定的正常工作時間，而不是休息、保養、大修的時間；（2）當前時刻設備是正常狀態，而不是處于損壞、維修、凍結、堵塞等狀態；（3）當前時刻設備具備正常運行所需的所有技術條件，包括操作工人、工裝、模具等；（4）當前時刻設備空閑或設備的某一工位空閑；離散事件系統1）單臺機器排序問題 （n/1/ /B)

17、 n個工件全部經由一臺機器處理離散事件系統常見單臺機器排序問題的目標函數 1) 平均流程時間最短 2）最大延期量最小 定義: 為最大延期量。 目標函數 為n個零件經由一臺機器的平均流程時間。 定義: 目標函數：使平均流程時間最短 Fi= Pi+ WiTi=max0, Li Li= Ci- di , 工件i的延誤時間 Li0 延誤生產系統離散事件系統Pi=任務i的作業時間 Wi=任務i的開始作業時間 根據排序目標的不同，可以選擇不同的排序規則，又稱為確定零件加工的優先權。常見的排序規則：SPT-Shortest Process Time, 優先選擇加工時間最短的工件EDD-Earliest Du

18、e Date 優先選擇交貨期緊的工件FCFS-First Come First Served 按工件到達的先后順序CR-Critical Rate 優先選擇臨界比最小的工件 CR=（交貨期-當前日期）/剩余加工時間離散事件系統2) 求平均流程時間最短的排序問題 求平均流程時間最短的作業順序，采用SPT原則。 按工件加工時間的長短，從小到大按排作業。 例：一臺加工中心，現有5個工件需要該機器加工。相關的加工時間和要求完成時間（交貨期）如下表所示，求平均流程時間最短的作業順序。 J1J2J3J4J5加工時間11293112交貨期6145313332離散事件系統解：根據SPT原則，得出：J4 -J5

19、 -J1 -J2 -J3有關項目的計算：發生延遲發生延遲加工時間開始時間完成時間交貨期延遲J4101330J5213320J111314610J2291443450J33143743143=43生產系統離散事件系統3）求最大延期量最小的排序問題 求最大延期量最小的作業順序采用EDD原則。 例：同上面的例子，按延期量(完工日期-交貨期）大小，從小到大排序。解：根據EDD原則，得出 J3 -J5 -J4-J2 -J1加工時間完成時間交貨期延遲J33131310J5233321J4134331J229634518J111746113生產系統離散事件系統=181、兩臺機器排序問題的含義(n/2/F/F

20、max) n個工件都必須經過機器1和機器2的加工，即工藝路線是一致的。 生產系統n項任務在兩臺機器的排序問題離散事件系統2、兩臺機器排序問題的目標 兩臺機器排序的目標是使生產周期Fmax最短。 Fmax的含義見如下圖。Fmax 時間 機器 A B在機器A上的作業時間總加工周期生產系統離散事件系統3、兩臺機器排序問題的算法 約翰遜法(Johnsons Law)， 約翰遜法解決這種問題分為4個步驟： (1)列出所有工件在兩臺設備上的作業時間。 (2)找出作業時間最小者。 (3)如果該最小值是在設備1上，將對應的工件排在前面，如果該最小值是在設備2上，則將對應的工件排在后面。 (4) 如果同時出現一

21、個以上的最小值,任意選區一個. (5)排除已安排好的工件，在剩余的工件中重復步驟(2)(4)，直到所有工件都安排完畢。 生產系統離散事件系統例：某一班組有A、B兩臺設備，要完成5個工件的加工任務。每個工件在設備上的加工時間如下表所示。求總加工周期最短的作業順序。 工件在兩臺設備上的加工時間工件編號 J1 J2 J3 J4 J5設備A 3 6 7 1 5設備B 2 8 6 4 3生產系統離散事件系統解：由約翰遜法可知，表中最小加工時間值是1個時間單位，它又是出現在設備1上，根據約翰遜法的規則，應將對應的工件4排在第一位，即得： J4 - * - * - * - * 去掉J4，在剩余的工件中再找最

22、小值，不難看出，最小值是2個時間單位，它是出現在設備2上的，所以應將對應的工件J1排在最后一位，即： J4 - * - * - * - J1 再去掉J1，在剩余的J2、J3、J5中重復上述步驟，求解過程為： J4 - * - * - J5 - J1 J4 - J2 - * - J5 - J1 J4 - J2 - J3- J5 - J1 當同時出現多個最小值時，可從中任選一個。最后得 J4 - J2 - J3- J5 - J1生產系統離散事件系統工件在兩臺設備上的加工時間工件編號 J1 J2 J3 J4 J5設備A 33 69 716 117 522設備B 25 817 623 427 330（

23、1）計算加工周期（按零件序號加工）生產系統離散事件系統工件在兩臺設備上的加工時間工件編號 J4 J2 J3 J5 J1設備A 11 67 714 519 322設備B 45 815 621 324 226（2）計算加工周期（按約翰遜法）生產系統離散事件系統(a) J1 - J2 - J3- J4 - J5 30AB26AB(b) J4 - J2 - J3- J5 - J1 生產系統離散事件系統離散事件系統仿真可在加入隨機因素（工時的變化、設備失效）的前提下以更直觀的方式獲知那種排序規則更好。離散事件系統仿真是在管理規范化的基礎上考慮到更為細節的因素，可使生產線的管理策略更好地適應現實世界。生產

24、系統離散事件系統2.3 輸入數據分析什么是輸入數據？什么是輸入數據分析？輸入數據分析些什么？ 仿真模型中，用于支撐仿真進行的各個已知元素的特征參數。有很多這樣的參數呈現出（假設為）隨機的特征。 對各個具有隨機特征的已知元素的特征參數，運用數理統計的方法來獲得其適當的隨機概率分布，以支持仿真過程中的隨機數產生。 隨機概率密度函數（什么分布？分布的參數是多少？） 分布的檢驗（擬合度檢驗、獨立性檢驗）2.3 輸入數據分析輸入數據分析的基本步驟數據過濾：消除非規律性影響因素。分布的假設：通過頻率圖的形狀估計，假設數據的理論分布假設分布的參數估計：估計假設給定理論分布函數的參數分布的擬合度檢驗：假設理論

25、分布與實際分布值之間的擬合程度檢驗（ f=k-s-1 的方檢驗）變量的相關性檢驗：系統仿真中隨機產生的數據應當符合數據本身獨立的特征（f=n-m-1的t檢驗）2.4 輸出數據分析離散事件仿真的數據特點？不確定性（不可重復性、理論上無統計規律）離散事件仿真數據的真實性是什么？給定置信水平的置信區間如何提高置信水平？增加重復運行的仿真次數。置信度為100%的仿真次數為2.4 輸出數據分析仿真輸出數據的性能測度上式成立的條件是的某一仿真性能參數之間是獨立的。（自相關函數為零）當自相關函數是負值，上式趨于保守。當自相關函數為正值，上式不成立。須進行詳細地檢驗。2.4 輸出數據分析終態仿真的輸出分析什么

26、是終態仿真？ 在某一個持續時間TE內的系統仿真。如：生產設備的使用壽命就是這一類的系統仿真。終態仿真的特征：系統仿真是在零時刻開始“開啟”，至TE時刻“關閉”，其中TE可以是一個隨機變量。研究的是不同持續時間TE或“開啟”時刻狀態對系統性能參數的影響。終態仿真的輸出分析獨立重復運行法 假設系統仿真進行了n次獨立重復運行，得到n個系統性能測度的仿真觀察值Y1, Y2, , Yn ，則系統性能測度的估計量為2.4 輸出數據分析 設仿真重復進行了R組，r(=1，2，R)為其中的一組仿真。令Yri為第r組仿真中的第i次系統性能測度的觀察值，i=1，2，nr。此時，對每一次運行r，其樣本均值為， r =

27、1，2，RR次獨立重復運行后，系統性能測度的估計量為 上式可以看到：標準差的估計量 隨著R的增加而減小。即仿真的可信度有所提高。2.4 輸出數據分析穩態仿真的輸出分析什么是穩態仿真？2.4 輸出數據分析提高仿真效率的數據處理方法第四章 離散事件仿真的邏輯分析 Petri網什么是Petri網？ 在定義Petri網(Petri Net)時，必須要區別PN結構與標識PN (Marked Petri Net)。它定義了DES (Discrete Event System)可能的狀態、事件、及其它們之間的關系，這相當于連續狀態變量系統CVDS的狀態方程。在PN中，用標識（Marking）描述DES的狀態

28、。后者又稱PN，它是指具有一定標識的PN，描述處于一定狀態下的DES，相當于給定了狀態方程的狀態變量在一定時刻值的CVDS。定義：PN的結構是由四要素描述的一個有向圖：PNS=(P, T, I, O)滿足： （1） P=p1, , pn是庫所(位置)的有限集合，n(0)為位置(庫所)的個數; （2） T=t1, , tm是變遷的有限集合，m(0)為變遷的個數； PT= ， PT ； （3） I：PTN是輸入函數，它定義了從P到T的有向弧的重復數 或權(Weight)的集合，這里N=0, 1, 為非負整數集； （4） O：TP N是輸出函數，它定義了從T到P的有向弧的重復數或權的集合。 在表示P

29、N結構的有向圖中，庫所用圓表示；變遷用長方形或粗實線段表示；若從位置p到變遷t的輸入函數取值為非負整數w，記為I(p, t)=w，則用從p到t的一有向弧并旁注w表示；若從變遷t到位置p的輸出函數取值非負整數w，記為O(p, t)= w，則用從t到p的一有向弧并旁注w表示。特別地，若w=1，則不必標注；若I(p, t)=0 或O(p, t)=0，則不必畫弧。I與O均表示為nm非負整數矩陣，O與I之差C=O-I 稱為關聯矩陣。Petri網的實例例：一PN結構如圖所示。按照PN的定義，該PN結構可描述如下： P=p1, p2, p3； T=t1, t2； I(p1, t1) = 1; I(p2, t

30、1) = 1; I(p3, t1) = 0; I(p1, t2) = 0; I(p2, t2) = 0; I(p3, t2) = 1;p2p3p1t1t2 O(p1, t1) = 0; O(p2, t1) = 0; O(p3, t1) = 1; O(p1, t2) = 0; O(p2, t2) = 1; O(p3, t2) = 0.輸入函數：輸出函數：關聯矩陣：第四章 離散事件仿真的邏輯分析 Petri網在PN結構中，p表示了離散事件系統(DES)的局部狀態，P表示DES的整體的狀態；T表示其所有可能的事件；某一庫所所表示的局部狀態實現情況(是否實現？實現了幾次？)用庫所中所包含的標記(Tok

31、en)數目m(p)來表示(用庫所p中圓點或數量表示標記)。特別地，m(p)=0，則p中無圓點，表示p所代表的局部狀態目前沒有實現。 t與 t分別表示t的所有輸入與輸出庫所的集合 ；p與p分別表示庫所p的輸入與輸出變遷 ；I與O描述所有可能的狀態與事件之間的關系，其中I描述事件發生的前提狀態(因)，而O描述事件發生所實現的狀態(果)。 Petri網有哪些功效？Petri網的實例 (續)p2p3p1t1t2例如，圖題中：（1）從p1與p2到t1有弧連接，既I(p1, t1)0，I(p2, t1)0，說明t1所表示的事件的發生以p1與p2所表示的局部狀態為前提條件；（2）而從p3到t1無弧連接，既I

32、(p3, t1)=0，說明t1所表示的事件的發生不取決于p3所表示的局部狀態；（3）從t1到p3有弧連接，即O(p3, t1)0，表明t1所表示的事件發生將影響p3所表示的局部狀態；（4）而從t1到其它庫所無弧連接，表明t1所表示的事件發生將不影響這些庫所所表示的局部狀態。Petri網的五要素定義標識PN為一5要素： PN=PNS, m=P, T, I, O, m此處： (1) PNS= P, T, I, O為PN結構，它由Petri網的四要素定義給出； (2) m: PN為標識PN的標識，它為一列向量，其第i個元素m(pi)表示第i個庫所中的標識數目。 m=(m(p1), m(p2), ,

33、m(pn)T特別地，DES的初始狀態用初始標識表示，記為m0。 相同結構的標識PN不是唯一的？Petri網的實例 (續)例題如圖（包括庫所中的圓點）一個標識PN，正規地描述如下：PN=P, T, I, O, m0* P, T, I, O見前例。* m0=(1, 1, 0)T, 其中第1個元素為m(p1)=1, 第2個元素為m(p2)=1, 第3個元素為m(p3)=0p2p3p1t1t2第四章 離散事件仿真的邏輯分析 Petri網Petri網的使能？在DES中某一事件必須在所有前提條件（狀態）得以滿足（實現）的情況下才可能發生。有時，要求某一前提條件（狀態）必須滿足多次（實現多次）。在DES的P

34、etri網中，我們以變遷t表示一事件，用變遷的使能(Enabling)表示事件因前提條件得以滿足而能夠發生。我們還用t的輸入庫所（通過指向t的弧連接的庫所）表示該事件的發生所需要的前提局部狀態，用由輸入庫所至t的輸入函數定義這些要求局部前提狀態實現的次數；而局部狀態的實現情況由庫所中所包含的標識數目來表示。因此，變遷t 的使能不僅與其輸入函數有關，而且與其所有輸入庫所中的標識數目有關。為此，引入以下變遷使能規則。使能的例子Petri網的使能定義 一變遷tT在標識m下使能，當且僅當：pt: m(p)I(p, t)。例如：在上例中，變遷t1的使能 t1=p1, p2， 由于m(p1)=1 I(p1

35、, t1)=1，m(p2)=1I(p2, t1)=1， 因此變遷t1使能的；而t2=p3，由于m(p3)=0 m。狀態轉換的例子 在右上圖所示的PN中，在m0=(1 ,1 ,0)T下使能的t1激發后，將產生新的標識m1(見右下圖)：m1(p1)= m0(p1)-I(p1, t1)+O(p1, t1) =1-1+0= 0；m1(p2)= m0(p2)-I(p2, t1)+O(p2, t1) =1-1+0= 0；m1(p3)= m0(p3)-I(p3, t1)+O(p3, t1) =0-0+1= 1； m1=(0, 0, 1)T p2p3p1t1t2p2p3p1t1t2上例的計算，似乎給我們告訴了

36、些東西：幾種特殊的PN: 若PN的所有變遷至多有1個輸入弧或輸出弧，即 I: PT0, 1, O: TP 0, 1，則此PN稱為普通PN（Ordinary Petri net）。 若PN無自閉環，即某一庫所同時是某一變遷的輸入與輸出庫所，則此PN稱為純PN（Pure Petri net）。 若PN的每一庫所都恰好有1個輸入變遷與1個輸出變遷，即pP: |p|=|p|=1，則該PN稱為標識圖(Marked graphs)。 若PN的每一變遷都恰好有1個輸入庫所與1個輸出庫所，tT: |t|=|t|=1，則該PN稱為狀態機(State machine)。 第四章 離散事件仿真的邏輯分析 Petri

37、網若干制造系統的基本PN模型緩沖區模型 考慮兩臺機器M1與M2之間的緩沖區B，假設它能夠存儲k個工件。t1：M1結束當前工件的加工并將該工件放入B中；t2：從B中取出一個工件并在M2上開始加工；pv：B的剩余容量；pb：B中存放的工件數量；puf：機器M2是空閑的； 當緩沖區滿時，pb中容納k個標識，而pv中無標識。此時t1被抑制而不能激發，機器M1堵塞(Blocked)。一旦一個工件從緩沖區移至機器M2，pv收到1個標識，則t1立即使能，生產得以恢復 。PN的抑制弧 （Inhibitor arc ） 按輸入函數的定義，pb中至少有k個標識是t1使能條件。但是，抑制弧的作用應理解為：一旦抑制弧

38、連接的輸入庫所中擁有與抑制弧的權相等數量的標識，則該抑制弧將抑制該變遷的激發 。抑制弧用一端帶由小圓并旁注權值k的弧表示。若干制造系統的基本PN模型存儲區溢出（Overflow）：當緩沖區存滿工件時，其存儲容量已耗盡的現象。當存儲區溢出時，其前端機器被堵塞。發生溢出時，期望提供存儲區溢出的信息，并改變堵塞在機器中工件的路徑，將其送至其它機器，而不是原路徑上的機器M2 。變遷toi的激發將輸出溢出指示。由于連接toi與pv的抑制弧的權為0，因此只要pv中包含1個及以上的標識(表明儲料取仍然有存儲空間)，則toi將被抑制激發，不產生溢出指示。當p1中包含1個標識(表示1工件被機器M1加工完畢，等待

39、從M1移出)，且pv中無標識(表明緩沖區堆滿工件)，toi立即激發，輸出溢出指示，將p1中的標識送至代表其它路徑的入口(圖中沒有畫出)，而不是pb。 若干制造系統的基本PN模型FCFS的工件隊列PN模型 傳送帶是典型的先來先享受服務(First-Come-First-Serve, FCFS)工件隊列的例子，因為先放置到傳送帶上的工件先從傳送帶的另一端離開。工件在傳送帶上傳送的過程可看作是暫時儲存在傳輸帶上 。ps表示工件在傳送之中，ta表示將工件放入傳送帶上。傳送帶所能夠傳送的最多工件數由ta的抑制弧的權N定義。只要ps中的標識數不超過N，抑制弧不起作用。此時，一當工件到達，ta立即激發， 將

40、1標識放入ps中，表示工件在傳送之中。只要ps中有標識，一旦pd中有1標識(表示請求將1工件從傳輸帶上移走)，則td激發，從ps中取走1標識，一工件離開傳送帶。 若干制造系統的基本PN模型描述制造系統的并行與同步特征PN模型 制造過程中，許多操作同時進行。例如，某一部件由2個零件裝配而成，2個零件分別由2條獨立的生產線加工，則裝配只能在每一零件加工完畢后才能進行。2個零件的加工過程是并行的(Concurrent)，通過裝配的開始而同步(Synchronized)。 左圖所示的PN，假設p1中的標識表示放置在一托盤上的2個工件到達，t1表示拆卸操作：將一個工件從托盤上移走并放入p2中，如此同時將

41、另一工件連同托盤送至p3。可以看到PN中的一個初始標識現在變為2個標識，也就是說，網中總標識數是可變的。還發現該模型中從t1分出2條不同的路徑，每一路徑代表一個加工過程，它們是并行的；兩個過程在t3處合并從而同步。若干制造系統的基本PN模型制造系統另一常見的現象是兩個以上的操作共享同一資源，例2臺機器共享一套刀具。對于資源的競爭將導致沖突(Conflict)。在PN中，資源表示為庫所，操作表示為變遷。因此，在PN中，資源的沖突表現為某一庫所被2個及其以上變遷共享同一個輸入庫所。根據標識圖的定義，它不能描述資源沖突。 左圖中2個加工過程都需要資源p4進行各自的操作，這是一典型的沖突問題。如前面剛

42、提到，t1與t3同時使能，但只有二者其一能夠激發。出現沖突時，必須作出決策一決定誰優先激發。最簡單的方法是采用隨機確定方法。若t1在沖突中獲勝，則t1激發并消耗p4中的標識。最終，t2激發從而將1標識放回p4，表示資源得以釋放。 基本PN性能系統的特性可分為行為（Behavioral）與結構(Structural)特性。行為特性是PN與初始標識有關的性能；而結構特性與初始標識無關，它們取決于PN的拓撲結構。重要的結構與行為特性: 可達性(Reachability);有界性(Boundness); 安全性(Safeness);守衡性(Conservativeness); 活性(Liveness)

43、;可逆性(Reversibility)。基本PN性能可達性是PN的一個重要行為特性: 給定一PN，我們期望知道從初始標識m0可以到達哪些標識; 給定一標識mt，是否可以激發一系列變遷從初試標識m0到達該標識。定義: 若從m0始標識開始激發一個變遷序列產生標識mr，則稱mr是從m0可達的。若只要從m0開始激發一個變遷即可產生mr，則稱mr是從m0立即可達的(Immediately reachable)。所有從m0可達的標識的集合稱為可達標識集或可達集，記為R(m0)。 一般地，從m0到mr所激發的變遷序列表示為: srtj1, , tjr, 這里j1, , jr為1到m之間的整數。從m0激發sr

44、產生mr表示為：m0srmr。例 在右圖的PN中，m0= (1, 0, 0, 1, 1, 0, 0)T，m0s4m4，這里m4= (0, 0, 1, 1 , 0, 0, 1)T，s4=t3, t4, t1, t2。 對于每一個激發的變遷序列sr，都可以關聯一個m1激發向量vr，該向量的第i個元素，對應著變遷ti在sr中出現的次數ni。一般地，vr=(n1, , nm)T。對于一定的vr，其對應的激發的變遷序列可能不是唯一的。例如，上面例子中提到的從m0到達m4，v4=(1, 1, 1, 1)T 所激發的對應變遷序列就有t3, t4, t1, t2與t1, t2, t3, t4 兩個。基本PN性

45、能可達性可描述制造系統的兩個問題：(1)系統按照一定的軌跡運行 系統是否能夠實現一定的狀態。典型的問題是生產調度計劃的驗證，即按照一定的生產調度計劃進行生產，一定的生產任務是否能夠得以完成；(2)要求到達一定的狀態 如何確定系統的運行軌跡，典型的問題是生產調度問題。第一個問題可以描述為：給定sr、初始標識m0以及期望達到的標識mr，則有m0srmr，若mr=mr則答案是肯定的；若mrmr，則答案是否定的。第二個問題可以描述為：給定m0與mr，尋找sr，使得m0srmr成立。必須指出sr可能不是唯一的，通常都在一定的準則下選取優化的sr。 基本PN性能有界性與安全性 :定義: 給定PN= (P,

46、 T, I, O, m0)以及其可達集R(m0)，對于庫所pP，若mR(m0)，有m(p)k，則稱p是k-有界的，此處k為正整數；若PN的所有庫所都是k-有界的，則PN是k-有界的。 特別地，k=1時，即當某庫所或PN是1-有界的，則稱該庫所或PN 是安全的。若對與任意初始標識m0，PN都是k-有界的，則PN是結構有界的(Structurally bounded)。 基本PN性能意義： 庫所用于表示制造系統中的工件、工具、托盤以及AGV的存放區（工件的存放區就是緩沖區），還用于表示資源的可利用情況。確認這些存放區是否溢出(Overflow)或資源的容量是否溢出是非常重要的。 PN的有界性是檢查

47、系統是否存在溢出的有效尺度：當庫所用于描述一操作，該庫所的安全性能夠確保不會重復啟動一正在進行的操作。我們可直觀地看到，右圖所示的PN是1-有界的，因此它是安全的。定義: 對于一變遷tT，在任一標識mR下，若存在一變遷序列sr，該變遷序列的激發使得此變遷t使能，則稱該變遷是活的(Live)。若一PN的所有變遷都是活的，則該PN是活的。死變遷(Dead transition)或者死鎖(Deadlock)從反面描述PN的活性。若存在mR，不存在從m開始的變遷序列，該序列的激發使得t使能，則變遷t為死變遷。若存在mR，在此m下無任何變遷使能，則稱PN包含一死鎖、該標識為死標識(Dead markin

48、g)。 基本PN性能死變遷(Dead transition)或死鎖(Deadlock)基本PN性能出現死鎖的原因是不合理的資源分配策略或某些或全部資源的耗盡。在自動制造系統中，許多資源（如機器、包括AGV與機器人在內的物料搬運設備、以及緩沖區存放空間）是共享的。在這樣的資源共享系統中，下列4個情況可能同時滿足，從而導致鎖死：互斥：一資源不可以為2個或2個以上過程同時使用，一過程排斥其它過程對于該資源的占用。占用且等待：一過程已被許可占用某一或某些資源，同時又在請求占用其它資源。無搶占：已分配給某一過程的資源不能從該過程中搶走，除非該過程使用此資源完畢后而釋放。循環等待：2個或更多過程排成一個鏈

49、，鏈上每一過程都在等待一個正在被鏈上下一個過程占用的資源。 制造系統出現死鎖的例子 柔性制造系統的某一機器入出緩沖區占用著一托盤，其上存放著已加工完畢的零件。而另一存放待加工工件的托盤也被自動導向車(AGV)傳送至該入出緩沖區。假設入出緩沖區只能存放一個托盤，而AGV也只能放置一個托盤。此時，存放著已加工的零件托盤不能從入出緩沖區移至AGV上，AGV也不能進入緩沖區將其上面存放著的待加工的工件的托盤送至入出件堆放區。 緩沖區與AGV為2個資源，將托盤從緩沖區移至AGV上與將托盤從AGV上送至緩沖區為2個過程。前者占用著緩沖區而等待著AGV，而后者占用著AGV而等待緩沖區，上述4個條件同時成立，

50、因而出現死鎖。基本PN性能可逆性(Reversibility)與主宿狀態(Home state) 制造系統研究中的一個重要問題是如何使得系統自動地從差錯中復原。例如，在利用機器人裝配中，零件間可能無法配合，從而出現差錯。我們希望在不需要人為干預的情況下，就能夠從這一差錯中復原。若一PN用于描述裝配操作，該操作配備有可行的恢復方案，則可逆網意味著自動地從差錯中復原是可能的。 定義：一PN是可逆的，若對于每一標識mR(m0)，m0R(m)。標識mrR(m0)稱為主宿狀態，若mR(m0)，mr是從m可達的。 基本PN性能 由上述定義，可逆性表示初始標識m0是從所有可達標識可達的。這意味著模型可以自身

51、初始化，它對于系統自動地從差錯中恢復過來是極為重要的。因為經過有限步驟，系統將回到期望的狀態。因此，若PN模型不是可逆的，則控制器應該力圖使之可逆；若無法做到，則不得不認為干預。 可逆性還確保系統的周期特性，例如重復制造系統。這一特性與可逆性與主宿狀態密切相關。可逆行是主宿狀態的特例，若mr=m0，即若主宿狀態為初始標識，則系統是可逆的。還必須注意，若PN包括一死鎖，則它不可能是可逆的。 一般地，有界性/安全性、活性、以及可逆性彼此間是獨立的。一個PN可以是活的、有界的、可逆的，活的、有界的、不可逆的，或者不是活的、無界的、不可逆的，共有8種組合。基本PN性能PN不是活的，是有界的，是不可逆的

52、。 基本PN性能定義：對于一PN=(P, T, I, O, m0)，若存在一矢量w=(w1, w2, , wn)T且wi0, i=1, 2, , n，使得對于所有mR(m0)：wTm=wTm0，則稱該PN相對于矢量w守衡。若PN相對于w=(1, 1, , 1)T守衡，即對于所有mR(m0)： ，則稱PN為嚴格守衡的。 定義：對于一PN=(P, T, I, O, m0)，若存在一矢量w=(w1, w2, , wn)T且wi0, i=1, 2, , n，但w0，使得對于所有mR(m0)：wTm=wTm0，則稱該PN相對于矢量w部分守衡。 基于PN制造系統性能分析 基于可達圖與覆蓋圖的分析 從初始標

53、識m0開始，期望到處PN所有可能的標識，這些標識通過變遷而關聯。我們將所有標識以及產生這些標識的變遷用一圖形表示，圖中的節點為標識，節點之間用表示變遷的帶箭頭的線或弧連接，帶箭頭的線起端所連接的標識通過由該線所代表的變遷的激發，產生該線末端所連接的標識。這樣的圖稱為可達圖。 若PN是無界的或PN所描述的系統具有無限個狀態，則可達圖將無止境擴展。取而代之，我們將構建覆蓋樹(Coverability tree)，它是無限可達圖的有限表達方法。基于PN制造系統性能分析定義：標識m2覆蓋m1，即m2m1，若pP： m2(p)m1(p)。移入一特別符號，它代表“準-無限大”，用于表示任意大的標識數。遵循

54、以下四個運算規則，使得對于任意正數k，都有：(1) k m），則對于那些使m(p)m(p)成立的p：用取代 m(p)； 3) 以m為一節點，從m至m畫一有向線，將其并記為t，并將m記為“new”；5. 除去m的“new”標志； 基于PN制造系統性能分析例: 構建圖(a)所示的具有無限儲料空間之間緩沖區的二機器生產線的覆蓋樹。初始標識為m0=(1 0 0 1 0)T 在m0下只有t1使能。激發t1將產生m1=(0 1 0 1 0)T。由于m1即不大于m0又不等于m0，因此將記為“new”，并從m0至m1畫一有向線并記為t1。 m1為當前唯一的“new”標識，在m1下只有t2使能。激發t2將產生標

55、識m2=(1 0 1 1 0)。由于m2m0且m2(p3)m0(p3)，因此，根據步驟4.2，在m2=(1 0 1 1 0)T中用取代m(p3)，從而得到標識m2=(1 0 1 0)T。 在當前唯一的“new”標識下，t1與t3使能。激發t1將產生m3=(0 1 1 0)T，它不等于從m0至m3路徑上任何標識。雖然它大于m1=(0 1 0 1 0)T，但沒有必要進行步驟4.2，原因是其第3個元素已經是。 激發t3產生m4=(1 0 -1 0 1)T=(1 0 0 1)T（根據-k=）。 目前存在m3=(0 1 1 0)T與m4=(1 0 0 1)T2個“new”標識。在m3=(0 1 1 0)

56、T下，t2與t3使能。激發t2產生m5=(0 1 +1 1 0)T=(0 1 1 0)T，它等于先前產生的m3，因此記為“old”。激發t3產生m6=(0 1 0 1)T，它是一“new”標識。目前仍然存在2個“new”標識：m3=(1 0 0 1)T與m6=(0 1 0 1)T 。繼續進行，直至無“new”標識存在. 基于PN制造系統性能分析根據上述方法，由圖(b)所示的覆蓋樹可知，圖(a)所示的PN是無界的，且除了p3其它庫所是安全的。還可知該PN不包含死變遷，因為所有變遷都在樹中出現。由于樹中出現，我們無法作出該PN是否活的與可逆的結論。 基于PN制造系統性能分析基于覆蓋樹或可達樹，可以

57、做如下分析：當且僅當樹中所有節點上均不出現時，PN網是有界的；此時，我們可以在樹中找出某一庫所中最大的標識數，比如說k，則該庫所是k-有界的；若k是樹中所有庫所中的最大的標識數，則PN是k-有界的。當且僅當樹中所有的節點上僅包含0或1時，則PN網是安全的。沒有任何死點包含，則樹中死點的個數就是PN死標識的數目；若樹中死點之一包含，則PN包含無數個死標識；若某變遷在樹中不出現，則該變遷是死變遷。在不包含的樹中，若給定任何兩個節點之間，都存在一有向路徑，在該路徑上所有變遷都出現，則PN是活的。在無出現的樹中，若從任何節點到根節點之間都存在一有向路徑，則PN是可逆的。 上述(5)僅適用于不包含的覆蓋

58、樹，即可達樹的活性分析（也即有界PN的活性分析），這是因為在出現的覆蓋樹中，由于的移入而損失一些信息。有研究表明，兩個不同的PNs具有相同的覆蓋樹，其中之一個PN是活的，而另一個不是活的3。 基于PN制造系統性能分析定義：一PN是關于初始表示m0一致的，若其覆蓋樹上存在一有向回路（不必要是基本回路），所有變遷都在起上出現至少一次。若該回路，只包含某些變遷，則為部分一致的。定義：一PN是關于初始標識m0重復的，若其覆蓋樹上存在一有向回路（不必要是基本回路），該有向回路包含所有的變遷無數次。若該有向回路經包含某些變遷，則為部分重復的。 連貫性(Consistency)與重復性(Repetitive

59、ness) 有向回路(Directed circuit)的概念：一有向回路為從某一節點(庫所或變遷)出發并返回該節點的路徑。若在有向回路上除了起始節點外，其它的節點出現的次數不多于一次，則該有向回路稱為基本有向回路或基本回路 基于不變量的PN分析：是一種基于矩陣線性代數。這一方法的優點是依據簡單的線性代數方程，就能正規地確定PN性能。這里所建立的線性代數方程決定著由PN所描述的分布系統的動態特性，這與同自動控制理論中狀態方程的概念，但其解局限于非負整數，因為它表示某一變遷激發的次數 。用mk表示第k次運行(k0)后PN的標識(一次運行就是激發一個變遷序列，它可能包括若干變遷的激發，一個變遷可能

60、在一次運行中激發多次)，則第k+1次運行后PN的表示為： mk+1=mk+Cvk， k0 (1)這里vk為激發記數向量，它為一(m1)向量，其第i個元素表示在第k+1次運行中變遷ti激發了的次數。上式稱為PN的狀態方程。特別地，若一次運行僅包含激發某一變遷1次，即vk只有1個元素為1，而其它元素均為0，則上式將表示PN的激發規則 。 mk+Cvk 0，對于所有 k0 上式可用于檢驗在mk下激發某一變遷序列是否合法。 基于PN制造系統性能分析定義3：P-不變量為一(n1)非負整數向量x，并滿足：xTC=0;(2)而T-不變量為 (m1)非負向量y，并滿足：Cy=0(3) 將(1)式兩邊左乘xT，