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

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

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

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

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

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

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

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

9、個離散事件系統(tǒng)建立一個模型確定一個系統(tǒng)目標(biāo)或仿真目的建立概念性模型轉(zhuǎn)換為一個詳細(xì)模型制定仿真規(guī)則轉(zhuǎn)換為一個計(jì)算機(jī)計(jì)算模型編制程序代碼模型的運(yùn)行檢驗(yàn)特例檢驗(yàn)?zāi)Ｐ偷挠行詸z驗(yàn)?zāi)Ｐ蜋z驗(yàn)、可信度檢驗(yàn)典型事件的多次重復(fù)仿真循環(huán)過程1.1 離散事件系統(tǒng)仿真的基本概念離散事件仿真模型的三層次模型概念模型層極其概念性的層次模型（通常是語義性的系統(tǒng)描述）模型是如何構(gòu)成的？什么是模型的狀態(tài)變量，哪些是動態(tài)變量，哪些是重要變量？詳細(xì)模型層模型的書面整理模型包括哪些方程，哪些偽隨機(jī)數(shù)，哪些輔助變量等模型參數(shù)如何輸入？計(jì)算模型層計(jì)算機(jī)程序通用編程語言或仿真語言1.1 離散事件系統(tǒng)仿真的基本概念系統(tǒng)與系統(tǒng)模型的實(shí)質(zhì)關(guān)聯(lián)是

10、什么？系統(tǒng)：研究的本體系統(tǒng)模型：為研究系統(tǒng)所收集的有關(guān)信息的集合。通過研究系統(tǒng)模型來揭示系統(tǒng)的性能。 它和“系統(tǒng)”的定義比較，兩者都是集合，系統(tǒng)是以某些規(guī)律結(jié)合起來、有相互作用的元素組成；而系統(tǒng)模型是為了研究其結(jié)合規(guī)律相互作用所收集的有關(guān)信息。因?yàn)槭占男畔⒂性敿?xì)、粗略之分，加上收集方法的差異和研究目的的不同，因此對于同一個系統(tǒng)就會出現(xiàn)多種不同的系統(tǒng)模型。模型是為系統(tǒng)服務(wù)的，因此，所揭示的性能規(guī)律應(yīng)該是穩(wěn)定的。1.1 離散事件系統(tǒng)仿真的基本概念離散事件仿真的輸入數(shù)據(jù)該如何收集和處理？仿真的輸入數(shù)據(jù)來源于事件采集穩(wěn)定的數(shù)據(jù)仿真的輸入數(shù)據(jù)應(yīng)該與實(shí)際數(shù)據(jù)有同樣的變化規(guī)律擬合度檢驗(yàn)仿真的輸入數(shù)據(jù)應(yīng)當(dāng)是

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29、N結(jié)構(gòu)的有向圖中，庫所用圓表示；變遷用長方形或粗實(shí)線段表示；若從位置p到變遷t的輸入函數(shù)取值為非負(fù)整數(shù)w，記為I(p, t)=w，則用從p到t的一有向弧并旁注w表示；若從變遷t到位置p的輸出函數(shù)取值非負(fù)整數(shù)w，記為O(p, t)= w，則用從t到p的一有向弧并旁注w表示。特別地，若w=1，則不必標(biāo)注；若I(p, t)=0 或O(p, t)=0，則不必畫弧。I與O均表示為nm非負(fù)整數(shù)矩陣，O與I之差C=O-I 稱為關(guān)聯(lián)矩陣。Petri網(wǎng)的實(shí)例例：一PN結(jié)構(gòu)如圖所示。按照PN的定義，該P(yáng)N結(jié)構(gòu)可描述如下： 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.輸入函數(shù)：輸出函數(shù)：關(guān)聯(lián)矩陣：第四章 離散事件仿真的邏輯分析 Petri網(wǎng)在PN結(jié)構(gòu)中，p表示了離散事件系統(tǒng)(DES)的局部狀態(tài)，P表示DES的整體的狀態(tài)；T表示其所有可能的事件；某一庫所所表示的局部狀態(tài)實(shí)現(xiàn)情況(是否實(shí)現(xiàn)？實(shí)現(xiàn)了幾次？)用庫所中所包含的標(biāo)記(Tok

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

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

33、m(pn)T特別地，DES的初始狀態(tài)用初始標(biāo)識表示，記為m0。 相同結(jié)構(gòu)的標(biāo)識PN不是唯一的？Petri網(wǎng)的實(shí)例 (續(xù))例題如圖（包括庫所中的圓點(diǎn)）一個標(biāo)識PN，正規(guī)地描述如下：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網(wǎng)Petri網(wǎng)的使能？在DES中某一事件必須在所有前提條件（狀態(tài)）得以滿足（實(shí)現(xiàn)）的情況下才可能發(fā)生。有時，要求某一前提條件（狀態(tài)）必須滿足多次（實(shí)現(xiàn)多次）。在DES的P

34、etri網(wǎng)中，我們以變遷t表示一事件，用變遷的使能(Enabling)表示事件因前提條件得以滿足而能夠發(fā)生。我們還用t的輸入庫所（通過指向t的弧連接的庫所）表示該事件的發(fā)生所需要的前提局部狀態(tài)，用由輸入庫所至t的輸入函數(shù)定義這些要求局部前提狀態(tài)實(shí)現(xiàn)的次數(shù)；而局部狀態(tài)的實(shí)現(xiàn)情況由庫所中所包含的標(biāo)識數(shù)目來表示。因此，變遷t 的使能不僅與其輸入函數(shù)有關(guān)，而且與其所有輸入庫所中的標(biāo)識數(shù)目有關(guān)。為此，引入以下變遷使能規(guī)則。使能的例子Petri網(wǎng)的使能定義 一變遷tT在標(biāo)識m下使能，當(dāng)且僅當(dāng)：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。狀態(tài)轉(zhuǎn)換的例子 在右上圖所示的PN中，在m0=(1 ,1 ,0)T下使能的t1激發(fā)后，將產(chǎn)生新的標(biāo)識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上例的計(jì)算，似乎給我們告訴了

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

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

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

39、從M1移出)，且pv中無標(biāo)識(表明緩沖區(qū)堆滿工件)，toi立即激發(fā)，輸出溢出指示，將p1中的標(biāo)識送至代表其它路徑的入口(圖中沒有畫出)，而不是pb。 若干制造系統(tǒng)的基本PN模型FCFS的工件隊(duì)列PN模型 傳送帶是典型的先來先享受服務(wù)(First-Come-First-Serve, FCFS)工件隊(duì)列的例子，因?yàn)橄确胖玫絺魉蛶系墓ぜ葟膫魉蛶У牧硪欢穗x開。工件在傳送帶上傳送的過程可看作是暫時儲存在傳輸帶上 。ps表示工件在傳送之中，ta表示將工件放入傳送帶上。傳送帶所能夠傳送的最多工件數(shù)由ta的抑制弧的權(quán)N定義。只要ps中的標(biāo)識數(shù)不超過N，抑制弧不起作用。此時，一當(dāng)工件到達(dá)，ta立即激發(fā)， 將

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

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

42、提到，t1與t3同時使能，但只有二者其一能夠激發(fā)。出現(xiàn)沖突時，必須作出決策一決定誰優(yōu)先激發(fā)。最簡單的方法是采用隨機(jī)確定方法。若t1在沖突中獲勝，則t1激發(fā)并消耗p4中的標(biāo)識。最終，t2激發(fā)從而將1標(biāo)識放回p4，表示資源得以釋放。 基本PN性能系統(tǒng)的特性可分為行為（Behavioral）與結(jié)構(gòu)(Structural)特性。行為特性是PN與初始標(biāo)識有關(guān)的性能；而結(jié)構(gòu)特性與初始標(biāo)識無關(guān)，它們?nèi)Q于PN的拓?fù)浣Y(jié)構(gòu)。重要的結(jié)構(gòu)與行為特性: 可達(dá)性(Reachability);有界性(Boundness); 安全性(Safeness);守衡性(Conservativeness); 活性(Liveness)

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

44、產(chǎn)生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。 對于每一個激發(fā)的變遷序列sr，都可以關(guān)聯(lián)一個m1激發(fā)向量vr，該向量的第i個元素，對應(yīng)著變遷ti在sr中出現(xiàn)的次數(shù)ni。一般地，vr=(n1, , nm)T。對于一定的vr，其對應(yīng)的激發(fā)的變遷序列可能不是唯一的。例如，上面例子中提到的從m0到達(dá)m4，v4=(1, 1, 1, 1)T 所激發(fā)的對應(yīng)變遷序列就有t3, t4, t1, t2與t1, t2, t3, t4 兩個?；綪N性

45、能可達(dá)性可描述制造系統(tǒng)的兩個問題：(1)系統(tǒng)按照一定的軌跡運(yùn)行 系統(tǒng)是否能夠?qū)崿F(xiàn)一定的狀態(tài)。典型的問題是生產(chǎn)調(diào)度計(jì)劃的驗(yàn)證，即按照一定的生產(chǎn)調(diào)度計(jì)劃進(jìn)行生產(chǎn)，一定的生產(chǎn)任務(wù)是否能夠得以完成；(2)要求到達(dá)一定的狀態(tài) 如何確定系統(tǒng)的運(yùn)行軌跡，典型的問題是生產(chǎn)調(diào)度問題。第一個問題可以描述為：給定sr、初始標(biāo)識m0以及期望達(dá)到的標(biāo)識mr，則有m0srmr，若mr=mr則答案是肯定的；若mrmr，則答案是否定的。第二個問題可以描述為：給定m0與mr，尋找sr，使得m0srmr成立。必須指出sr可能不是唯一的，通常都在一定的準(zhǔn)則下選取優(yōu)化的sr。 基本PN性能有界性與安全性 :定義: 給定PN= (P,

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

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

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

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

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

51、初始化，它對于系統(tǒng)自動地從差錯中恢復(fù)過來是極為重要的。因?yàn)榻?jīng)過有限步驟，系統(tǒng)將回到期望的狀態(tài)。因此，若PN模型不是可逆的，則控制器應(yīng)該力圖使之可逆；若無法做到，則不得不認(rèn)為干預(yù)。 可逆性還確保系統(tǒng)的周期特性，例如重復(fù)制造系統(tǒng)。這一特性與可逆性與主宿狀態(tài)密切相關(guān)?？赡嫘惺侵魉逘顟B(tài)的特例，若mr=m0，即若主宿狀態(tài)為初始標(biāo)識，則系統(tǒng)是可逆的。還必須注意，若PN包括一死鎖，則它不可能是可逆的。 一般地，有界性/安全性、活性、以及可逆性彼此間是獨(dú)立的。一個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，則稱該P(yáng)N相對于矢量w守衡。若PN相對于w=(1, 1, , 1)T守衡，即對于所有mR(m0)： ，則稱PN為嚴(yán)格守衡的。 定義：對于一PN=(P, T, I, O, m0)，若存在一矢量w=(w1, w2, , wn)T且wi0, i=1, 2, , n，但w0，使得對于所有mR(m0)：wTm=wTm0，則稱該P(yáng)N相對于矢量w部分守衡。 基于PN制造系統(tǒng)性能分析 基于可達(dá)圖與覆蓋圖的分析 從初始標(biāo)

53、識m0開始，期望到處PN所有可能的標(biāo)識，這些標(biāo)識通過變遷而關(guān)聯(lián)。我們將所有標(biāo)識以及產(chǎn)生這些標(biāo)識的變遷用一圖形表示，圖中的節(jié)點(diǎn)為標(biāo)識，節(jié)點(diǎn)之間用表示變遷的帶箭頭的線或弧連接，帶箭頭的線起端所連接的標(biāo)識通過由該線所代表的變遷的激發(fā)，產(chǎn)生該線末端所連接的標(biāo)識。這樣的圖稱為可達(dá)圖。 若PN是無界的或PN所描述的系統(tǒng)具有無限個狀態(tài)，則可達(dá)圖將無止境擴(kuò)展。取而代之，我們將構(gòu)建覆蓋樹(Coverability tree)，它是無限可達(dá)圖的有限表達(dá)方法?；赑N制造系統(tǒng)性能分析定義：標(biāo)識m2覆蓋m1，即m2m1，若pP： m2(p)m1(p)。移入一特別符號，它代表“準(zhǔn)-無限大”，用于表示任意大的標(biāo)識數(shù)。遵循

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

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

56、T下，t2與t3使能。激發(fā)t2產(chǎn)生m5=(0 1 +1 1 0)T=(0 1 1 0)T，它等于先前產(chǎn)生的m3，因此記為“old”。激發(fā)t3產(chǎn)生m6=(0 1 0 1)T，它是一“new”標(biāo)識。目前仍然存在2個“new”標(biāo)識：m3=(1 0 0 1)T與m6=(0 1 0 1)T 。繼續(xù)進(jìn)行，直至無“new”標(biāo)識存在. 基于PN制造系統(tǒng)性能分析根據(jù)上述方法，由圖(b)所示的覆蓋樹可知，圖(a)所示的PN是無界的，且除了p3其它庫所是安全的。還可知該P(yáng)N不包含死變遷，因?yàn)樗凶冞w都在樹中出現(xiàn)。由于樹中出現(xiàn)，我們無法作出該P(yáng)N是否活的與可逆的結(jié)論。 基于PN制造系統(tǒng)性能分析基于覆蓋樹或可達(dá)樹，可以

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

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

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

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