《系統(tǒng)建模與仿真》第三章離散事件系統(tǒng)建模管理科學(xué)與工程學(xué)院付赟2023/7/29《系統(tǒng)建模與仿真》23.1離散事件系統(tǒng)離散事件系統(tǒng)的性質(zhì)與連續(xù)系統(tǒng)完全不同，這類系統(tǒng)的狀態(tài)只在離散的時(shí)間點(diǎn)上發(fā)生變化，而且這些離散的時(shí)間點(diǎn)是不確定的。例1：理發(fā)店就是一個(gè)典型的離散事件系統(tǒng)的例子。2《系統(tǒng)建模與仿真》2023/7/292023/7/29《系統(tǒng)建模與仿真》33.1離散事件系統(tǒng)對(duì)于離散事件系統(tǒng)來說，系統(tǒng)的內(nèi)部狀態(tài)變化是隨機(jī)的，同一個(gè)內(nèi)部狀態(tài)可以向多種狀態(tài)轉(zhuǎn)變，因此很難用函數(shù)形式來描述系統(tǒng)內(nèi)部狀態(tài)的變化，通常所關(guān)心的是系統(tǒng)內(nèi)部狀態(tài)變化的統(tǒng)計(jì)規(guī)律。系統(tǒng)的內(nèi)部狀態(tài)只在離散的隨機(jī)時(shí)間點(diǎn)上發(fā)生變化，且狀態(tài)在一段時(shí)間內(nèi)保持不變。因此在建立離散事件系統(tǒng)模型時(shí)，只需考慮系統(tǒng)內(nèi)部狀態(tài)發(fā)生變化的時(shí)間點(diǎn)以及產(chǎn)生這些狀態(tài)變化的原因，而不用描述系統(tǒng)內(nèi)部狀態(tài)發(fā)生變化的過程。3《系統(tǒng)建模與仿真》2023/7/292023/7/29《系統(tǒng)建模與仿真》41、實(shí)體1）定義：實(shí)體(Entity)是指一個(gè)系統(tǒng)邊界內(nèi)部的客觀對(duì)象，離散事件系統(tǒng)是由實(shí)體組成的。2）分類：臨時(shí)實(shí)體

先進(jìn)入系統(tǒng)并經(jīng)過相應(yīng)的環(huán)節(jié)后再離開系統(tǒng)，且在系統(tǒng)中的數(shù)量經(jīng)常變化的實(shí)體，又稱為主動(dòng)實(shí)體、活動(dòng)實(shí)體。永久實(shí)體

經(jīng)常處于系統(tǒng)之內(nèi)，其數(shù)量保持穩(wěn)定的實(shí)體，又稱為被動(dòng)實(shí)體。3.1.1離散事件系統(tǒng)要素4《系統(tǒng)建模與仿真》2023/7/292023/7/29《系統(tǒng)建模與仿真》53.1.1離散事件系統(tǒng)要素系統(tǒng)的工作過程實(shí)質(zhì)上就是臨時(shí)實(shí)體流動(dòng)和接受加工、處理的過程。如：排隊(duì)的顧客，待加工的工件等永久實(shí)體只要系統(tǒng)處于活動(dòng)狀態(tài)，它就一定存在。如：商店的營(yíng)業(yè)員，加工設(shè)備等臨時(shí)實(shí)體按一定規(guī)律不斷到達(dá)，在永久實(shí)體作用下通過系統(tǒng)，最后離開系統(tǒng)。系統(tǒng)狀態(tài)的變化主要是由實(shí)體的狀態(tài)變化而產(chǎn)生的。5《系統(tǒng)建模與仿真》2023/7/292023/7/29《系統(tǒng)建模與仿真》62、事件1）定義

事件(Event)是引起系統(tǒng)狀態(tài)發(fā)生變化的行為。離散事件系統(tǒng)可以看做是由事件驅(qū)動(dòng)的，它是在某一時(shí)間點(diǎn)的瞬間行為，如：待加工工件、顧客等的“到達(dá)”或“離開”等。事件不僅用來協(xié)調(diào)兩個(gè)實(shí)體之間的同步活動(dòng)，還用于各實(shí)體之間的信息傳遞。3.1.1離散事件系統(tǒng)要素6《系統(tǒng)建模與仿真》2023/7/292023/7/29《系統(tǒng)建模與仿真》73.1.1離散事件系統(tǒng)要素2）分類時(shí)間事件和狀態(tài)事件時(shí)間事件：依照系統(tǒng)的作業(yè)規(guī)則在預(yù)訂時(shí)間發(fā)生的事件。狀態(tài)事件：當(dāng)系統(tǒng)狀態(tài)符合某種條件下發(fā)生的事件?；臼录投问录臼录浩浒l(fā)生可以事先加以預(yù)測(cè)的事件。二次事件：發(fā)生與否則取決于其他事件。如：顧客到達(dá)和接受服務(wù)7《系統(tǒng)建模與仿真》2023/7/292023/7/29《系統(tǒng)建模與仿真》83.1.1離散事件系統(tǒng)要素3、活動(dòng)活動(dòng)(Active)是實(shí)體在兩個(gè)事件之間保持某一狀態(tài)的持續(xù)過程。

如：顧客接受服務(wù)的過程，工件被加工的過程活動(dòng)因某一事件的發(fā)生而開始，因下一事件的發(fā)生而結(jié)束，因此它標(biāo)志著實(shí)體狀態(tài)遷移的一個(gè)片段。

如：在“顧客到達(dá)”與“服務(wù)開始”兩個(gè)事件之間存在一個(gè)“排隊(duì)等候”活動(dòng)；“服務(wù)開始”與“服務(wù)結(jié)束”之間存在“顧客接受服務(wù)”活動(dòng)。

8《系統(tǒng)建模與仿真》2023/7/292023/7/29《系統(tǒng)建模與仿真》93.1.1離散事件系統(tǒng)要素4、進(jìn)程進(jìn)程(Process)是由與某類實(shí)體相關(guān)的事件和若干活動(dòng)組成的，它描述了這些事件和活動(dòng)間的相互邏輯關(guān)系和時(shí)序關(guān)系。如：“顧客到達(dá)系統(tǒng)—排隊(duì)—開始接受服務(wù)—服務(wù)結(jié)束”的過程就構(gòu)成了一個(gè)進(jìn)程。進(jìn)程是事件與活動(dòng)的組合，它可以更加完整地描述實(shí)體狀態(tài)的遷移過程。9《系統(tǒng)建模與仿真》2023/7/293.1.1離散事件系統(tǒng)要素2023/7/29《系統(tǒng)建模與仿真》10理發(fā)店例子中進(jìn)程的含義10《系統(tǒng)建模與仿真》2023/7/292023/7/29《系統(tǒng)建模與仿真》11

3.1.1離散事件系統(tǒng)要素5、屬性

屬性(Attribute)是實(shí)體特征的描述，是實(shí)體所擁有的全部特征的一個(gè)子集，用特征參數(shù)變量表示。在仿真建模中，只需要使用與研究目的相關(guān)的一部分就可以了。11《系統(tǒng)建模與仿真》2023/7/292023/7/29《系統(tǒng)建模與仿真》123.1.1離散事件系統(tǒng)要素6、狀態(tài)狀態(tài)(State)是指在某時(shí)間點(diǎn)上對(duì)系統(tǒng)的所有實(shí)體屬性和活動(dòng)的描述。當(dāng)一個(gè)系統(tǒng)的所有實(shí)體處于狀態(tài)協(xié)調(diào)并定義狀態(tài)的屬性時(shí)，則認(rèn)為系統(tǒng)處于特定狀態(tài)。

如：在隨機(jī)服務(wù)系統(tǒng)模型中，“顧客”有“等待服務(wù)”和“接受服務(wù)”等狀態(tài)，“服務(wù)員”有“忙”和“閑”等狀態(tài)。活動(dòng)總是與一個(gè)或幾個(gè)實(shí)體的狀態(tài)相對(duì)應(yīng)，狀態(tài)可作為動(dòng)態(tài)屬性進(jìn)行描述。12《系統(tǒng)建模與仿真》2023/7/292023/7/29《系統(tǒng)建模與仿真》133.1.1離散事件系統(tǒng)要素13《系統(tǒng)建模與仿真》2023/7/292023/7/29《系統(tǒng)建模與仿真》143.1.1離散事件系統(tǒng)要素7、仿真時(shí)鐘仿真時(shí)鐘用于表示仿真時(shí)間的變化及作為仿真過程的時(shí)序控制，它是系統(tǒng)運(yùn)行時(shí)間在仿真過程中的表示。仿真時(shí)鐘推進(jìn)的方式：固定步長(zhǎng)時(shí)間推進(jìn)機(jī)制下次事件時(shí)間推進(jìn)機(jī)制

仿真時(shí)鐘推進(jìn)的時(shí)間間隔稱為仿真步長(zhǎng)，離散事件系統(tǒng)仿真時(shí)鐘的推進(jìn)步長(zhǎng)是隨機(jī)的，取決于系統(tǒng)的當(dāng)前狀態(tài)和事件發(fā)生的條件。14《系統(tǒng)建模與仿真》2023/7/292023/7/29《系統(tǒng)建模與仿真》153.1.1離散事件系統(tǒng)要素8、系統(tǒng)環(huán)境

系統(tǒng)環(huán)境(SystemEnvironment)是系統(tǒng)周圍的對(duì)象及過程(實(shí)體和活動(dòng))。發(fā)生于系統(tǒng)內(nèi)部的活動(dòng)稱為內(nèi)生活動(dòng)，發(fā)生于系統(tǒng)環(huán)境中并對(duì)系統(tǒng)產(chǎn)生影響的活動(dòng)稱為外生活動(dòng)，將活動(dòng)劃分為內(nèi)生活動(dòng)和外生活動(dòng)就確定了系統(tǒng)的邊界。15《系統(tǒng)建模與仿真》2023/7/293.1.1離散事件系統(tǒng)要素確定系統(tǒng)的狀態(tài)變量是很重要的。由于進(jìn)行仿真研究的系統(tǒng)狀態(tài)變量并不總是固定唯一的，它應(yīng)當(dāng)根據(jù)系統(tǒng)仿真研究的目的而確定。描述系統(tǒng)狀態(tài)變化的流程到達(dá)并進(jìn)入系統(tǒng)中實(shí)體的類型和數(shù)目使系統(tǒng)狀態(tài)發(fā)生變化的事件類型事件發(fā)生時(shí)間的分布規(guī)律等2023/7/29《系統(tǒng)建模與仿真》1616《系統(tǒng)建模與仿真》2023/7/292023/7/29《系統(tǒng)建模與仿真》173.1.1離散事件系統(tǒng)要素系統(tǒng)實(shí)體屬性活動(dòng)系統(tǒng)狀態(tài)事件工業(yè)生產(chǎn)機(jī)器、零件生產(chǎn)能力、故障加工要求加工時(shí)間、故障時(shí)間機(jī)器忙、機(jī)器閑加工開始、加工結(jié)束通信信號(hào)、信道信號(hào)長(zhǎng)度、傳輸終端傳輸信道發(fā)送忙、信道發(fā)送閑信號(hào)開始傳輸、信號(hào)傳輸結(jié)束倉(cāng)儲(chǔ)倉(cāng)庫(kù)、物品庫(kù)房容量進(jìn)貨庫(kù)存水平、欠付需求需求交通道路、交叉口車輛信號(hào)機(jī)車道數(shù)、車型、車速周期運(yùn)動(dòng)時(shí)間、信號(hào)時(shí)間系統(tǒng)總車數(shù)、紅綠燈車輛到達(dá)、綠燈開始離散系統(tǒng)實(shí)例17《系統(tǒng)建模與仿真》2023/7/292023/7/29《系統(tǒng)建模與仿真》183.1.2離散事件系統(tǒng)建模方法建模是仿真的前提，是計(jì)算機(jī)仿真的關(guān)鍵技術(shù)內(nèi)容之一；模型不正確，仿真的結(jié)果也失去意義由于隨機(jī)事件系統(tǒng)的模型很難用常規(guī)的微分方程、差分方程來描述；隨著系統(tǒng)科學(xué)和管理科學(xué)的發(fā)展機(jī)及其在各領(lǐng)域中應(yīng)用的不斷深入，逐步形成了一些與連續(xù)系統(tǒng)不同的建模方法主流方法：流圖和網(wǎng)絡(luò)圖18《系統(tǒng)建模與仿真》2023/7/293.1.2離散事件系統(tǒng)建模方法1、實(shí)體流圖法與計(jì)算機(jī)程序流程圖類似可以描述實(shí)體產(chǎn)生、流動(dòng)、消亡及其被永久實(shí)體加工、處理的過程和邏輯關(guān)系實(shí)體流圖模型易于轉(zhuǎn)換為面向事件的仿真模型2023/7/29《系統(tǒng)建模與仿真》1919《系統(tǒng)建模與仿真》2023/7/293.1.2離散事件系統(tǒng)建模方法2、活動(dòng)周期圖法針對(duì)實(shí)體的行為模式進(jìn)行建?？梢灾庇^地表示出某類實(shí)體生命周期中的活動(dòng)和狀況具有規(guī)范化的特點(diǎn)對(duì)不同實(shí)體之間協(xié)同關(guān)系的描述清晰、明確易于轉(zhuǎn)換為面向活動(dòng)的仿真模型2023/7/29《系統(tǒng)建模與仿真》2020《系統(tǒng)建模與仿真》2023/7/293.1.2離散事件系統(tǒng)建模方法3、Petri網(wǎng)法適于建立加工系統(tǒng)等多種離散事件系統(tǒng)的模型對(duì)網(wǎng)系統(tǒng)的特性進(jìn)行較嚴(yán)密的數(shù)學(xué)分析處理并發(fā)、沖突、死鎖等現(xiàn)象2023/7/29《系統(tǒng)建模與仿真》2121《系統(tǒng)建模與仿真》2023/7/292023/7/29《系統(tǒng)建模與仿真》223.2實(shí)體流圖法系統(tǒng)要對(duì)臨時(shí)實(shí)體產(chǎn)生作用，就必須有永久實(shí)體的活動(dòng)，也就是必須有永久實(shí)體。臨時(shí)實(shí)體和永久實(shí)體協(xié)同完成了某項(xiàng)活動(dòng)，永久實(shí)體作為活動(dòng)的資源而被占用。理發(fā)店的服務(wù)員，交通路口的紅綠燈等都是永久實(shí)體的例子。22《系統(tǒng)建模與仿真》2023/7/293.2.1實(shí)體流圖法概述

實(shí)體流圖法(EntityFlowChart，EFC)采用與計(jì)算機(jī)程序流程圖相類似的圖示符號(hào)和原理，建立表示臨時(shí)實(shí)體產(chǎn)生、在系統(tǒng)中流動(dòng)、接受永久實(shí)體“服務(wù)”，以及消失等過程的流程圖。

借助實(shí)體流程圖，可以表示事件狀態(tài)變化及實(shí)體間相互作用的邏輯關(guān)系。

在離散事件系統(tǒng)中實(shí)體流圖法應(yīng)用比較普遍，原因如下：1）計(jì)算機(jī)程序框圖的思想和方法已廣為人們所接受；2）實(shí)體流圖法簡(jiǎn)單，且對(duì)離散事件系統(tǒng)的描述比較全面。23《系統(tǒng)建模與仿真》2023/7/293.2.2實(shí)體流圖法的建模思路對(duì)建模者的兩點(diǎn)要求：1）對(duì)實(shí)際系統(tǒng)的工作過程有深刻的理解和認(rèn)識(shí)2）將事件、狀態(tài)變化、活動(dòng)和隊(duì)列等概念貫穿于建模過程中常用的圖示符號(hào)：菱形框（判斷）；矩形框（事件、狀態(tài)、活動(dòng)）；圓角矩形框（開始和結(jié)束）；箭頭（邏輯關(guān)系）24《系統(tǒng)建模與仿真》2023/7/293.2.2實(shí)體流圖法的建模思路建模的一般步驟如下：1）明確組成系統(tǒng)的各個(gè)實(shí)體及其屬性2）分析各種實(shí)體的狀態(tài)和活動(dòng)，及其相互間的影響。3）考察那些導(dǎo)致活動(dòng)的開始或結(jié)束的事情，或者是可以作為活動(dòng)開始或結(jié)束的標(biāo)志的事件，以確定引起實(shí)體狀態(tài)變化的事件，并將條件事件合并。4）分析各種事件發(fā)生時(shí)實(shí)體狀態(tài)是如何變化的。5）在一定的服務(wù)流程下，分析與隊(duì)列實(shí)體有關(guān)系的特殊操作(如換隊(duì)等)。25《系統(tǒng)建模與仿真》2023/7/293.2.2實(shí)體流圖法的建模思路6）根據(jù)以上分析，以臨時(shí)實(shí)體的流動(dòng)為主線，用約定的圖示符號(hào)畫出被仿真系統(tǒng)的實(shí)體流圖。7）確定模型參數(shù)的取值、參變量的計(jì)算方法及屬性描述變量的取值方法。屬性描述變量(例如顧客到達(dá)時(shí)間、服務(wù)時(shí)間等)既可以取一組固定值，也可以由某一公式計(jì)算得到，還可以是一個(gè)隨機(jī)變量。如果屬性描述變量是隨機(jī)變量，就應(yīng)該給出其分布函數(shù)。8）確定隊(duì)列的排隊(duì)規(guī)則。當(dāng)有多個(gè)隊(duì)列存在時(shí)，還應(yīng)給出其服務(wù)規(guī)則，例如隊(duì)列的優(yōu)先權(quán)、換隊(duì)規(guī)則等。26《系統(tǒng)建模與仿真》2023/7/293.2.3實(shí)體流圖法的實(shí)例分析例1：理發(fā)店服務(wù)系統(tǒng)

——單服務(wù)臺(tái)、單隊(duì)列服務(wù)系統(tǒng)有一個(gè)小理發(fā)店只有一個(gè)理發(fā)員，顧客來到理發(fā)店后，如果有其他顧客正在理發(fā)就坐在一旁等候。理發(fā)員按先來先理的原則為每一位顧客服務(wù)，而且只要有顧客就不停歇。建模目的是在假定顧客到達(dá)時(shí)間間隔和理發(fā)花費(fèi)的時(shí)間服從一定的概率分布時(shí)，考察理發(fā)員的忙閑情況。2023/7/29《系統(tǒng)建模與仿真》2727《系統(tǒng)建模與仿真》2023/7/293.2.3實(shí)體流圖法的實(shí)例分析（1）辨識(shí)系統(tǒng)實(shí)體三個(gè)實(shí)體：理發(fā)員是永久實(shí)體，顧客是臨時(shí)實(shí)體，顧客隊(duì)列是一類特殊實(shí)體（2）分析實(shí)體的狀態(tài)和活動(dòng)類實(shí)體的組成理發(fā)員的活動(dòng)有“理發(fā)”和“休息”，對(duì)應(yīng)“忙”和“閑”兩種狀態(tài)顧客與理發(fā)員協(xié)同完成理發(fā)活動(dòng)，有“等待服務(wù)”和“接受服務(wù)”兩種狀態(tài)顧客隊(duì)列的狀態(tài)由隊(duì)列長(zhǎng)度來標(biāo)識(shí)三類實(shí)體的活動(dòng)及狀態(tài)之間存在邏輯上的關(guān)系2023/7/29《系統(tǒng)建模與仿真》2828《系統(tǒng)建模與仿真》2023/7/293.2.3實(shí)體流圖法的實(shí)例分析（3）分析實(shí)體狀態(tài)的變化情況某一顧客到達(dá)時(shí)，如果理發(fā)員處于“忙”狀態(tài)，則該顧客進(jìn)入“等待服務(wù)”狀態(tài)；否則進(jìn)入“接受服務(wù)”狀態(tài)理發(fā)員完成對(duì)某一顧客的服務(wù)時(shí)，如果隊(duì)列處于“非零”狀態(tài)，則立即開始服務(wù)活動(dòng)；否則進(jìn)入“閑”狀態(tài)處于排隊(duì)等待中的顧客，如果理發(fā)員完成了對(duì)前一顧客的服務(wù)，則進(jìn)入“接受服務(wù)”狀態(tài)；否則保持“等待服務(wù)”狀態(tài)2023/7/29《系統(tǒng)建模與仿真》2929《系統(tǒng)建模與仿真》2023/7/293.2.3實(shí)體流圖法的實(shí)例分析（4）分析引起狀態(tài)變化的事件“顧客到達(dá)”或“顧客結(jié)束排隊(duì)”導(dǎo)致“服務(wù)”活動(dòng)的開始；而“顧客理完離去”導(dǎo)致“服務(wù)”活動(dòng)的結(jié)束；這三個(gè)瞬時(shí)行為均可以作為事件看待?！邦櫩徒Y(jié)束排隊(duì)”是以理發(fā)員狀態(tài)是“閑”為條件的；而隊(duì)列狀態(tài)是“非零”時(shí)理發(fā)員狀態(tài)為“閑”是以事件“顧客理完離去”為條件的；以上兩個(gè)條件事件順序、互為因果。將“顧客結(jié)束排隊(duì)”事件并入“顧客理完離去”事件，不予單獨(dú)考慮，即合并條件事件?！邦櫩偷竭_(dá)”將使理發(fā)員由“閑”變?yōu)椤懊Α?，或使“?duì)列長(zhǎng)度”增加1?！邦櫩屠硗觌x去”將使理發(fā)員由“忙”變?yōu)椤伴e”?！邦櫩徒Y(jié)束排隊(duì)”將使“隊(duì)列長(zhǎng)度”減少1，并使理發(fā)員由“閑”變?yōu)椤懊Α薄?023/7/29《系統(tǒng)建模與仿真》3030《系統(tǒng)建模與仿真》2023/7/293.2.3實(shí)體流圖法的實(shí)例分析（5）分析隊(duì)列實(shí)體的操作該問題只有一個(gè)隊(duì)列，而且顧客不會(huì)因?yàn)榕抨?duì)人數(shù)太多而離去，因此隊(duì)列規(guī)則簡(jiǎn)單，沒有換隊(duì)等特殊的隊(duì)列操作。（6）畫出系統(tǒng)實(shí)體流程圖基于實(shí)體、活動(dòng)和事件的分析從實(shí)體進(jìn)入系統(tǒng)開始，按照事件和活動(dòng)相互交替的原則，按順序畫出實(shí)體在系統(tǒng)中的流動(dòng)過程。對(duì)條件事件，可在事件框前加入條件判斷2023/7/29《系統(tǒng)建模與仿真》3131《系統(tǒng)建模與仿真》2023/7/293.2.3實(shí)體流圖法的實(shí)例分析2023/7/29《系統(tǒng)建模與仿真》32單線框：事件雙線框：活動(dòng)理發(fā)員為忙、理發(fā)員為閑：設(shè)置系統(tǒng)標(biāo)志的特殊操作，可以不畫32《系統(tǒng)建模與仿真》2023/7/293.2.3實(shí)體流圖法的實(shí)例分析（7）確定模型參變量顧客的到達(dá)時(shí)間（隨機(jī)變量）理發(fā)員為一個(gè)顧客理發(fā)所需的服務(wù)時(shí)間（隨機(jī)變量）（8）給出排隊(duì)規(guī)則隊(duì)列的排隊(duì)規(guī)則是先到先服務(wù)（FIFO）說明：實(shí)體流圖是為描述實(shí)體流動(dòng)和相互間邏輯關(guān)系而繪制的，與計(jì)算機(jī)程序框圖不同2023/7/29《系統(tǒng)建模與仿真》3333《系統(tǒng)建模與仿真》2023/7/293.2.3實(shí)體流圖法的實(shí)例分析例2：售票窗口服務(wù)系統(tǒng)

——兩類顧客競(jìng)爭(zhēng)資源電影院雇用一名售票員同時(shí)負(fù)責(zé)電影票的銷售和對(duì)電話問詢者的咨詢服務(wù)。窗口服務(wù)比電話服務(wù)優(yōu)先級(jí)高。問詢者打來的電話由電話系統(tǒng)存儲(chǔ)后按先來先服務(wù)的規(guī)則一一予以答復(fù)。建模的目的是研究售票員的忙閑率。2023/7/29《系統(tǒng)建模與仿真》3434《系統(tǒng)建模與仿真》2023/7/293.2.3實(shí)體流圖法的實(shí)例分析（1）辨識(shí)系統(tǒng)實(shí)體售票員：永久實(shí)體；購(gòu)票者和電話問詢者：臨時(shí)實(shí)體；購(gòu)票隊(duì)列和問詢隊(duì)列：特殊實(shí)體。2023/7/29《系統(tǒng)建模與仿真》3535《系統(tǒng)建模與仿真》2023/7/293.2.3實(shí)體流圖法的實(shí)例分析（2）分析實(shí)體狀態(tài)和活動(dòng)類實(shí)體組成售票員有“空閑”、“售票”和“接電話”3個(gè)活動(dòng)，對(duì)應(yīng)的是“閑”和“忙”兩種狀態(tài)購(gòu)票者有“排隊(duì)”和“購(gòu)票”2個(gè)活動(dòng)，對(duì)應(yīng)的是“等待”和“購(gòu)票”兩種狀態(tài)問詢者有“排隊(duì)”和“問詢”2個(gè)活動(dòng)，對(duì)應(yīng)的是“等待”和“問詢”兩種狀態(tài)顧客隊(duì)列的狀態(tài)以隊(duì)列長(zhǎng)度標(biāo)識(shí)4類實(shí)體的活動(dòng)及狀態(tài)存在邏輯上的聯(lián)系36《系統(tǒng)建模與仿真》2023/7/293.2.3實(shí)體流圖法的實(shí)例分析（3）分析實(shí)體狀態(tài)變化的情況購(gòu)票者或者問詢者到達(dá)時(shí)，如果售票員處于“忙”狀態(tài)，則該顧客進(jìn)入“等待”狀態(tài)；否則，進(jìn)入“購(gòu)票”或“問詢”狀態(tài)處于排隊(duì)等待中的顧客，如果售票員完成了對(duì)前一顧客的服務(wù)，則進(jìn)入“購(gòu)票”或“問詢”狀態(tài)；否則，繼續(xù)保持“等待”狀態(tài)37《系統(tǒng)建模與仿真》2023/7/293.2.3實(shí)體流圖法的實(shí)例分析（4）分析引起狀態(tài)變化的事件“購(gòu)票者到達(dá)”、“問詢者到達(dá)”、“購(gòu)票者結(jié)束排隊(duì)”或者“問詢者結(jié)束排隊(duì)”導(dǎo)致售票員“服務(wù)”活動(dòng)的開始“購(gòu)票者買票后離去”或“問詢者咨詢后離去”導(dǎo)致售票員“服務(wù)”活動(dòng)結(jié)束38《系統(tǒng)建模與仿真》2023/7/293.2.3實(shí)體流圖法的實(shí)例分析（5）分析隊(duì)列實(shí)體的操作該問題有兩個(gè)隊(duì)列，但兩個(gè)隊(duì)列中的顧客不會(huì)互換隊(duì)列（6）畫出系統(tǒng)實(shí)體流程圖以臨時(shí)實(shí)體為主線，畫出實(shí)體流程39《系統(tǒng)建模與仿真》2023/7/293.2.3實(shí)體流圖法的實(shí)例分析40《系統(tǒng)建模與仿真》2023/7/293.2.3實(shí)體流圖法的實(shí)例分析（7）確定模型參變量購(gòu)票者到達(dá)時(shí)間電話問詢者到達(dá)時(shí)間售票服務(wù)時(shí)間電話服務(wù)時(shí)間（8）給出排隊(duì)規(guī)則排隊(duì)規(guī)則：FIFO服務(wù)規(guī)則：購(gòu)票者和問詢者分別排隊(duì)，優(yōu)先進(jìn)行購(gòu)票活動(dòng)41《系統(tǒng)建模與仿真》2023/7/293.2.3實(shí)體流圖法的實(shí)例分析兩個(gè)與服務(wù)規(guī)則有關(guān)的判斷和特殊操作當(dāng)“電話問詢者”和“窗口購(gòu)票者”同時(shí)到達(dá)，且售票員處于“閑”的狀態(tài)，后者接受服務(wù)，前者加入電話隊(duì)列當(dāng)服務(wù)完畢，且購(gòu)票隊(duì)列和電話隊(duì)列均不為空時(shí)，先進(jìn)行購(gòu)票服務(wù)由于本例中有兩類臨時(shí)實(shí)體同時(shí)流動(dòng),因此可能出現(xiàn)資源沖突,對(duì)此類問題的描述,活動(dòng)周期圖有其獨(dú)到之處.42《系統(tǒng)建模與仿真》2023/7/293.2.4模型的人工運(yùn)行建立實(shí)體流程圖模型后，選取有代表性的例子將流程圖全部走一遍，即所謂人工運(yùn)行。人工運(yùn)行模型要求遍歷流程圖的各個(gè)分支和實(shí)體的各種可能狀態(tài)，在時(shí)間逐步變化的動(dòng)態(tài)條件下，分析事件的發(fā)生及狀態(tài)的變化過程，以檢查模型的組成和邏輯關(guān)系是否正確。2023/7/29《系統(tǒng)建模與仿真》433.2.4模型的人工運(yùn)行例1中，假定：（1）系統(tǒng)的初始狀態(tài)包括永久實(shí)體“理發(fā)員”的狀態(tài)及特殊實(shí)體“隊(duì)列”的狀態(tài)初始時(shí)刻是仿真開始的時(shí)刻，理發(fā)員為“閑”，隊(duì)列長(zhǎng)度為0（2）模型參數(shù)及變量的取值第i個(gè)顧客與第i-1個(gè)顧客到達(dá)的時(shí)間間隔Ai理發(fā)員為第i個(gè)顧客的理發(fā)時(shí)間Si兩個(gè)都是隨機(jī)變量，可根據(jù)其分布函數(shù)來產(chǎn)生2023/7/2944《系統(tǒng)建模與仿真》3.2.4模型的人工運(yùn)行模型需按照一定的規(guī)則運(yùn)行，本模型的人工運(yùn)行規(guī)則如下：規(guī)則1——確定當(dāng)前時(shí)間模型人工運(yùn)行開始時(shí)，取當(dāng)前時(shí)間TIME=t0（初始仿真時(shí)刻）人工運(yùn)行開始后，當(dāng)前時(shí)間逐步向前推移，且遞取下一最早發(fā)生事件的發(fā)生時(shí)刻如果當(dāng)前時(shí)間有顧客到達(dá)事件發(fā)生，轉(zhuǎn)規(guī)則2若有顧客離去事件發(fā)生，則轉(zhuǎn)規(guī)則32023/7/2945《系統(tǒng)建模與仿真》3.2.4模型的人工運(yùn)行規(guī)則2——顧客到達(dá)事件處理假定在時(shí)刻TIME有顧客i到達(dá)，如果理發(fā)員“忙”，則入隊(duì)列等待，隊(duì)列長(zhǎng)度加1否則，置理發(fā)員為“忙”狀態(tài)，顧客開始理發(fā)，且在di=TIME+Si時(shí)刻理畢離去規(guī)則3——顧客離去事件處理假定在時(shí)刻TIME有顧客i離去，如果此時(shí)隊(duì)列長(zhǎng)度為0，置理發(fā)員為“閑”狀態(tài)否則，隊(duì)列中排在隊(duì)首的一名顧客開始理發(fā)，隊(duì)列長(zhǎng)度減1，顧客在di=TIME+Si時(shí)刻理畢離去2023/7/2946《系統(tǒng)建模與仿真》3.2.4模型的人工運(yùn)行令A(yù)1=15，A2=32，A3=24，A4=40，…令S1=43，S2=36，S3=34，S4=28，…（1）在TIME=t0時(shí)刻，無任何事件發(fā)生下一最早發(fā)生的事件為“顧客1到達(dá)”，發(fā)生時(shí)刻為a1=TIME+A1=15（2）在TIME=15時(shí)刻，顧客1到達(dá)按規(guī)則2，理發(fā)員開始為顧客1理發(fā)，狀態(tài)由“閑”變“忙”顧客1離去時(shí)刻d1=TIME+S1=15+43=58下一最早發(fā)生的事件為“顧客2到達(dá)”，顧客2到達(dá)的時(shí)刻為a2=a1+A2=15+32=47<582023/7/2947《系統(tǒng)建模與仿真》3.2.4模型的人工運(yùn)行（3）在TIME=47時(shí)刻，顧客2到達(dá)因理發(fā)員“忙”，顧客2排隊(duì)等待，隊(duì)列長(zhǎng)度變成1下一最早發(fā)生的事件為“顧客1離去”，離去時(shí)刻

d1=58<a3=71（4）在TIME=58時(shí)刻，顧客1離去按規(guī)則3，隊(duì)列長(zhǎng)度為1，理發(fā)員為顧客2理發(fā)，隊(duì)列長(zhǎng)度變?yōu)?顧客2離去時(shí)刻d2=TIME+S2=58+36=94下一最早發(fā)生的事件為“顧客3到達(dá)”，到達(dá)的時(shí)刻為a3=a2+A3=47+24=712023/7/2948《系統(tǒng)建模與仿真》3.2.4模型的人工運(yùn)行（5）在TIME=71時(shí)刻，顧客3到達(dá)，…2023/7/2949《系統(tǒng)建模與仿真》3.3活動(dòng)周期圖法實(shí)體流圖法中，實(shí)體的行為模式在有限的幾種情況之間周而復(fù)始地變化，表現(xiàn)出一定的生命周期形式如：理發(fā)員在“忙”和“閑”之間不斷變化；顧客在“到達(dá)”、“等待”、“理發(fā)”和“離去”之間變化活動(dòng)周期圖法（ActivityCycleDiagram，ACD）正是基于這樣的思想而逐步形成的一種離散事件建模方法2023/7/2950《系統(tǒng)建模與仿真》3.3.1活動(dòng)周期圖概述以直觀的方式顯示了實(shí)體的狀態(tài)變化歷程和各實(shí)體之間的交互作用關(guān)系，便于理解和分析。充分反映各類實(shí)體的行為模式，并將系統(tǒng)的狀態(tài)變化以“個(gè)體”狀態(tài)變化的集合方式表示出來，因此可以更好地表達(dá)眾多實(shí)體的并發(fā)活動(dòng)和實(shí)體之間的協(xié)同關(guān)系。但是，它只描述了系統(tǒng)的穩(wěn)態(tài)，而沒有表示系統(tǒng)的瞬態(tài)，即活動(dòng)的開始和結(jié)束事件。2023/7/2951《系統(tǒng)建模與仿真》活動(dòng)周期圖建模方法將實(shí)體的狀態(tài)分為靜寂(Dead)和激活(Active)兩種。(a)靜寂狀態(tài)

(b)激活狀態(tài)激活狀態(tài)通常是實(shí)體的活動(dòng)，模型中活動(dòng)的忙期可采用隨機(jī)采樣等方法事先加以確定。

靜寂狀態(tài)通常表示無活動(dòng)發(fā)生，是實(shí)體等待參加某一活動(dòng)時(shí)的狀態(tài)，其持續(xù)時(shí)間在模型中無法事先確定，取決于有關(guān)活動(dòng)的發(fā)生時(shí)刻和忙期。3.3.2活動(dòng)周期圖建模2023/7/2952《系統(tǒng)建模與仿真》3.3.2活動(dòng)周期圖建?；顒?dòng)周期圖法建模過程（1）辨識(shí)組成系統(tǒng)的實(shí)體及屬性辨識(shí)永久實(shí)體及臨時(shí)實(shí)體，隊(duì)列不作為實(shí)體考慮（2）分別畫出個(gè)實(shí)體的活動(dòng)周期圖以實(shí)際過程為依據(jù)，隊(duì)列作為排隊(duì)等待狀態(tài)來處理①交替原則：靜寂狀態(tài)和激活狀態(tài)必須交替出現(xiàn)②閉合原則：臨時(shí)實(shí)體的ACD表示一個(gè)或單位實(shí)體從產(chǎn)生到消失的循環(huán)過程；永久實(shí)體的ACD表示一個(gè)或幾個(gè)實(shí)體被占用和釋放的循環(huán)往復(fù)過程2023/7/2953《系統(tǒng)建模與仿真》3.3.2活動(dòng)周期圖建模加工空閑安裝就緒等待D=10D=3機(jī)器工人2023/7/2954《系統(tǒng)建模與仿真》3.3.2活動(dòng)周期圖建模（3）將各實(shí)體的ACD連接成系統(tǒng)ACD以各實(shí)體之間的協(xié)同活動(dòng)為紐帶進(jìn)行連接（4）增添必要的虛擬實(shí)體ACD中，當(dāng)一個(gè)活動(dòng)的所有前置靜寂狀態(tài)均取非零值時(shí)，該活動(dòng)才有可能發(fā)生，可以增添某些必要的虛擬實(shí)體，并假定它們與另外的實(shí)體協(xié)同完成某項(xiàng)活動(dòng)為實(shí)體活動(dòng)的發(fā)生加上某種附加條件，從而實(shí)現(xiàn)“隔時(shí)發(fā)生”的建模效果2023/7/2955《系統(tǒng)建模與仿真》3.3.2活動(dòng)周期圖建模（5）標(biāo)明活動(dòng)發(fā)生的約束條件和占用資源的數(shù)量①活動(dòng)是否可以發(fā)生的判斷條件②永久實(shí)體在參加一次協(xié)同活動(dòng)時(shí)被占用和活動(dòng)完成時(shí)釋放的數(shù)量（6）給出模型參數(shù)的取值、參變量的計(jì)算方法及屬性描述變量的取值方法，并給出排隊(duì)規(guī)則和服務(wù)規(guī)則2023/7/2956《系統(tǒng)建模與仿真》3.3.2活動(dòng)周期圖法建模舉例例3：機(jī)床加工系統(tǒng)的活動(dòng)周期圖法建模——操作工有休息飲茶的權(quán)利考慮一個(gè)簡(jiǎn)單的加工車間。車間內(nèi)有數(shù)臺(tái)自動(dòng)機(jī)床，由一名工人負(fù)責(zé)看管。工人的任務(wù)是：①如果機(jī)床的刀具完好，則為機(jī)床安裝工件，然后按下運(yùn)行按鈕；②如果機(jī)床的刀具損壞，則先要重裝刀具，然后執(zhí)行任務(wù)①。只有當(dāng)機(jī)床完成一次自動(dòng)加工工序，并停止運(yùn)行后，工人才能執(zhí)行上述兩項(xiàng)任務(wù)。假定每臺(tái)機(jī)床均可加工各種工件，并且不會(huì)發(fā)生工件短缺的現(xiàn)象。建模的目的是為了研究工人的忙閑率。2023/7/2957《系統(tǒng)建模與仿真》3.3.2活動(dòng)周期圖法建模舉例建模考慮的兩類實(shí)體：機(jī)床、工人（1）工人活動(dòng)：安裝工件(RESET)，安裝刀具(RETOOL)，其他活動(dòng)(AWAY)三種活動(dòng)均為激活狀態(tài)否則，處于靜寂狀態(tài)“等待”，該狀態(tài)取決于激活狀態(tài)2023/7/29《系統(tǒng)建模與仿真》583.3.2活動(dòng)周期圖法建模舉例（2）機(jī)床三種激活狀態(tài)：安裝刀具，安裝工件，加工(RUWNING)引入“預(yù)備”、“停機(jī)”兩種靜寂狀態(tài)：滿足交替原則的要求2023/7/29《系統(tǒng)建模與仿真》593.3.2活動(dòng)周期圖法建模舉例工人只要不從事“安裝刀具”和“安裝工件”的工作，就可從事“其他活動(dòng)”。即，“等待”是“其他活動(dòng)”的唯一前置條件。問題：限定工人每隔2h才能休息10min，如何在活動(dòng)周期圖中表示？辦法：引入虛擬實(shí)體——工人休息的權(quán)力2023/7/29《系統(tǒng)建模與仿真》603.3.2活動(dòng)周期圖法建模舉例權(quán)力實(shí)體協(xié)同工人實(shí)體完成“飲茶”活動(dòng)，其生命周期中要完成“計(jì)時(shí)”（RECORD）這一活動(dòng)。為了滿足交替原則，增添“有權(quán)”(YES)和“無權(quán)”(NO)兩種狀態(tài)。權(quán)力實(shí)體的引入滿足了每隔一段時(shí)間方可進(jìn)入某一活動(dòng)的建模需要2023/7/29《系統(tǒng)建模與仿真》613.3.2活動(dòng)周期圖法建模舉例2023/7/29《系統(tǒng)建模與仿真》623.3.2活動(dòng)周期圖法建模舉例模型參數(shù)：“機(jī)床數(shù)量”模型參變量：“累計(jì)加工的工件數(shù)”判斷當(dāng)機(jī)床處于“停機(jī)”狀態(tài)且工人處于“等待”狀態(tài)時(shí)，機(jī)床是否需要重?fù)Q刀具，從而決定是進(jìn)入“安裝刀具”還是“安裝工件”屬性變量：“加工時(shí)間”、“安裝刀具時(shí)間”和“安裝工件時(shí)間”、“飲茶時(shí)間”和“輪休時(shí)間”2023/7/29《系統(tǒng)建模與仿真》633.3.2活動(dòng)周期圖法建模舉例服務(wù)規(guī)則當(dāng)工人處于“等待”狀態(tài)時(shí)，是先飲茶休息，還是先工作（假定機(jī)床處于“停機(jī)”狀態(tài)且權(quán)力處于“有權(quán)”狀態(tài)），其選擇取決于模型參數(shù)的值活動(dòng)周期圖中允許進(jìn)行分支處理，這時(shí)分支狀態(tài)需要有一個(gè)判斷變量，根據(jù)判斷變量的取值情況，可以確定實(shí)體的走向。2023/7/29《系統(tǒng)建模與仿真》643.3.2活動(dòng)周期圖法建模舉例例4：貨物運(yùn)轉(zhuǎn)系統(tǒng)大型貨車從工廠拉貨到轉(zhuǎn)運(yùn)站，將貨卸在固定的倉(cāng)位。運(yùn)來的貨物經(jīng)分揀后放在另外的專用倉(cāng)位，由小貨車運(yùn)往客戶。運(yùn)轉(zhuǎn)站內(nèi)有兩個(gè)卸貨倉(cāng)位，4個(gè)裝貨倉(cāng)位，每個(gè)倉(cāng)位前均只能停放一輛貨車。貨物由10名工人負(fù)責(zé)裝卸，裝卸一車貨物需要2名工人。運(yùn)送貨物的大小貨車首先從公路上拐進(jìn)運(yùn)轉(zhuǎn)站門口的一個(gè)停車場(chǎng)，然后經(jīng)過一條通道駛往各自的倉(cāng)位。為了便于辦理手續(xù)，通道被分為兩半，左邊出車，右邊進(jìn)車，而且進(jìn)出通道只能容兩輛小貨車同時(shí)行進(jìn)。大車的優(yōu)先級(jí)高于小車，出車的優(yōu)先級(jí)高于進(jìn)車。倉(cāng)位有空閑時(shí)才放貨車進(jìn)入通道。2023/7/29《系統(tǒng)建模與仿真》65停車場(chǎng)通道3.3.2活動(dòng)周期圖法建模舉例建模目的是研究在一定的貨物吞吐量下設(shè)幾個(gè)卸貨倉(cāng)位比較合適。不考慮貨物數(shù)量的影響。實(shí)體：大貨車、小貨車、卸貨倉(cāng)位、裝貨倉(cāng)位、工人、進(jìn)站通道和出站通道7個(gè)實(shí)體：2個(gè)臨時(shí)實(shí)體和5個(gè)永久實(shí)體2023/7/29《系統(tǒng)建模與仿真》663.3.2活動(dòng)周期圖法建模舉例（1）大貨車由系統(tǒng)“外部”逐個(gè)“到達(dá)”，經(jīng)停車場(chǎng)“排隊(duì)”后，“駛?cè)搿毙敦泜}(cāng)位“等候”工人“卸貨”，“卸空”后“駛離”轉(zhuǎn)運(yùn)站。激活狀態(tài)：“到達(dá)”、“駛?cè)搿?、“卸貨”和“駛離”協(xié)同活動(dòng)：“外部”、“等候”、“排隊(duì)”和“卸空”“駛?cè)搿被顒?dòng)發(fā)生的條件之一：至少有一個(gè)卸貨倉(cāng)位空閑（空閑卸倉(cāng)個(gè)數(shù)UNBAY>0）（2）小貨車與大貨車類似2023/7/29《系統(tǒng)建模與仿真》67leaveemptyunloadoutsidewaitarrivequeuemove大貨車exitfullloadelsewheredockedcomeparkenter小貨車2023/7/2968《系統(tǒng)建模與仿真》2023/7/29《系統(tǒng)建模與仿真》693.3.2活動(dòng)周期圖法建模舉例（3）裝、卸倉(cāng)位（4）裝、卸工人（5）進(jìn)、出通道unloadunbay卸貨倉(cāng)位loadbay裝貨倉(cāng)位unloadloadlabour裝卸工leaveroadoutmoveexit出口通道leaveroadinmoveenter進(jìn)口通道2023/7/2970《系統(tǒng)建模與仿真》unloadunbayloadbayunloadloadlabourleaveemptyunloadoutsidewaitarrivequeuemoveleaveroadoutmoveexitexitfullloadelewheredockedcomeparkenterleaveroadinmoveenter2023/7/2971《系統(tǒng)建模與仿真》2023/7/29《系統(tǒng)建模與仿真》723.3.2活動(dòng)周期圖法建模舉例模型參數(shù)：裝卸工人的數(shù)量，裝卸倉(cāng)位的數(shù)量參變量：當(dāng)前卸貨倉(cāng)位的數(shù)量UNBAY，裝貨倉(cāng)位的數(shù)量BAY，工人的可用數(shù)量LABOUR，進(jìn)、出通道數(shù)ROADIN和ROADOUT屬性變量：各個(gè)活動(dòng)的忙期，隨機(jī)變量排隊(duì)規(guī)則：FIFO服務(wù)規(guī)則：大小貨車各排一隊(duì)，裝卸工、進(jìn)出通道優(yōu)先為大貨車服務(wù)，優(yōu)先安排貨車離開貨場(chǎng)2023/7/29《系統(tǒng)建模與仿真》733.3.3模型的人工運(yùn)行首先確定系統(tǒng)的初始狀態(tài)按下列原則運(yùn)行模型：規(guī)則1——活動(dòng)的發(fā)生與執(zhí)行（1）活動(dòng)的所有前置狀態(tài)中均有實(shí)體停留，且各類永久實(shí)體的數(shù)量超過或等于相應(yīng)資源占用量；（2）活動(dòng)發(fā)生的約束條件已經(jīng)滿足。依次檢查每一活動(dòng)，以判斷此活動(dòng)是否可以開始，即此活動(dòng)所要求的足夠的實(shí)體集合是否已經(jīng)存在于所有有關(guān)的前置隊(duì)列中。如果含有，則將這個(gè)實(shí)體集合的標(biāo)志移入此活動(dòng)的矩形內(nèi)，且計(jì)算出此活動(dòng)的終止時(shí)間，并將此時(shí)間寫在該活動(dòng)的矩形內(nèi)。當(dāng)所有活動(dòng)都檢查完后，轉(zhuǎn)向規(guī)則2。2023/7/29《系統(tǒng)建模與仿真》743.3.3模型的人工運(yùn)行規(guī)則2——確定當(dāng)前時(shí)間檢查所有活動(dòng)的終止時(shí)間，選其最小值，并設(shè)置時(shí)鐘值為此選擇值，然后轉(zhuǎn)向規(guī)則3。規(guī)則3——活動(dòng)的完成從所有已發(fā)生的活動(dòng)中，檢出終止時(shí)間等于當(dāng)前時(shí)間的臨時(shí)實(shí)體，刪掉為其標(biāo)注的終止時(shí)間；然后將相應(yīng)臨時(shí)實(shí)體的標(biāo)記移至其相關(guān)的后續(xù)狀態(tài)中。參與活動(dòng)的各永久實(shí)體的資源量相應(yīng)增加，將參與活動(dòng)的永久實(shí)體的后續(xù)狀態(tài)作標(biāo)記，轉(zhuǎn)規(guī)則12023/7/29《系統(tǒng)建模與仿真》753.4實(shí)體流圖和活動(dòng)周期圖的比較第一：EFC以臨時(shí)實(shí)體在系統(tǒng)中的流動(dòng)過程為主線，永久實(shí)體濃縮于表示狀態(tài)和事件的圖示符合中，隊(duì)列作為一種特殊實(shí)體。ACD基于各類臨時(shí)和永久實(shí)體的行為模式，有獨(dú)特的圖示標(biāo)識(shí)，隊(duì)列成為實(shí)體生命周期的一種狀態(tài)。第二：EFC是帶有小循環(huán)的樹形流程圖ACD中，各類實(shí)體是環(huán)形的循環(huán)圖，整個(gè)系統(tǒng)由多個(gè)環(huán)套在一起2023/7/29《系統(tǒng)建模與仿真》763.4實(shí)體流圖和活動(dòng)周期圖的比較第三：EFC中，事件有顯式的表達(dá)ACD中，事件蘊(yùn)含在活動(dòng)中，沒有顯式表達(dá)第四：EFC中，狀態(tài)判斷框的作用非常重要ACD中，將需作判斷的狀態(tài)用“空閑”、“等待”等靜寂狀態(tài)表示，對(duì)實(shí)體是否處于該狀態(tài)的判斷也無需標(biāo)注在圖中，而是作為模型運(yùn)行時(shí)的一般規(guī)則3.5Petri網(wǎng)建模方法改變活動(dòng)周期圖建模方法：取消臨時(shí)實(shí)體ACD中的“源”狀態(tài)，即不再考慮臨時(shí)實(shí)體的生命周期循環(huán)將活動(dòng)看作是“開始事件+狀態(tài)+結(jié)束事件”，則，建模元素就變成“事件”和“狀態(tài)”，后者包括ACD中的激活狀態(tài)和靜寂狀態(tài)不強(qiáng)調(diào)實(shí)體模型之間的獨(dú)立性用集合論的語(yǔ)言描述后，可以建立規(guī)范的Petri網(wǎng)方法2023/7/29《系統(tǒng)建模與仿真》773.5.1Petri網(wǎng)的基本概念Petri網(wǎng)是由節(jié)點(diǎn)和有向弧組成的一種有向圖它有兩類節(jié)點(diǎn)：庫(kù)所，即狀態(tài)元素，它表示一個(gè)場(chǎng)所，而且在該場(chǎng)所存放了一定的資源，用“○”表示；變遷，它指資源的消耗、使用以及對(duì)應(yīng)狀態(tài)元素的變化，用“∣”表示。另外，資源指的是與系統(tǒng)狀態(tài)發(fā)生變化有關(guān)的因素。2023/7/29《系統(tǒng)建模與仿真》783.5.1Petri網(wǎng)的基本概念2023/7/29《系統(tǒng)建模與仿真》79Petri網(wǎng)定義：三元組N=(S,T;F)稱為Petri網(wǎng)的充要條件是：3.5.1Petri網(wǎng)的基本概念S：庫(kù)所集；T：變遷集F：由一個(gè)S元素和一個(gè)T元素組成的有序偶的集合，稱為N的流關(guān)系dom（F）：F所含序偶的第一個(gè)元素的集合cod（F）：第二個(gè)元素的集合N不能有孤立元素，即S,T,F均不能為空集3.5.2網(wǎng)系統(tǒng)網(wǎng)是系統(tǒng)靜態(tài)結(jié)構(gòu)的基本描述容量、標(biāo)識(shí)和權(quán)重3.5.2網(wǎng)系統(tǒng)例5：有一條工業(yè)生產(chǎn)線，它要完成兩項(xiàng)工業(yè)操作，這兩項(xiàng)操作用t1和t2表示。第一個(gè)變遷t1將傳入生產(chǎn)線的半成品s1和部件s2用兩個(gè)螺絲釘s3固定在一起，變成半成品s4。第二個(gè)變遷t2再將s4和部件s5用3個(gè)螺絲釘s3固定在一起，得到新的半成品s6。完成操作t1和t2時(shí)都要用到工具s7。假定由于存放空間的限制，部件s2和部件s5最多不能超過100件，停放在生產(chǎn)線上的半成品s4最多不能超過5件，螺絲釘s3存放最多不能超過1000件。3.5.2網(wǎng)系統(tǒng)S1S2S3K=1000K=5S4S7S5S6K=100K=100t2t13.5.2網(wǎng)系統(tǒng)（1）容量K(s)標(biāo)識(shí)庫(kù)所s中允許存放令牌的最大數(shù)量，其值標(biāo)在表示庫(kù)所的圓圈旁，不標(biāo)明時(shí)容量為∞（2）權(quán)W(x,y)表示變遷發(fā)生時(shí)消耗和產(chǎn)出的令牌數(shù)量，其值標(biāo)在?。▁，y）上；不標(biāo)明時(shí)表示權(quán)為1（3）令牌表示原料、部件、產(chǎn)品、人員、工具、設(shè)備、數(shù)據(jù)和信息等組成系統(tǒng)的“資源”，標(biāo)識(shí)M(s)的值用令牌數(shù)表示3.5.2網(wǎng)系統(tǒng)2023/7/29《系統(tǒng)建模與仿真》853.5.3Petri網(wǎng)的變遷原則當(dāng)變遷不斷發(fā)生時(shí)，網(wǎng)系統(tǒng)的狀態(tài)也不斷發(fā)生變化，這一過程稱網(wǎng)系統(tǒng)的執(zhí)行。2023/7/29《系統(tǒng)建模與仿真》863.5.3Petri網(wǎng)的變遷原則1）一個(gè)變遷被授權(quán)發(fā)生，當(dāng)且僅當(dāng)該變遷的每一個(gè)輸入庫(kù)所中的令牌數(shù)大于或等于輸入弧的權(quán)值，并且該變遷的輸出庫(kù)所中已有的令牌數(shù)與輸出孤權(quán)值之和小于輸出庫(kù)所的容量；簡(jiǎn)單地說就是“前面夠用，后面夠放”。2）變遷發(fā)生(點(diǎn)火)的充要條件是該變遷是授權(quán)的。3）變遷發(fā)生時(shí)，從該變遷的輸入庫(kù)所中移出與輸入弧權(quán)值相等的令牌數(shù)，輸出庫(kù)所中產(chǎn)生與輸出弧權(quán)值相等的令牌數(shù)。2023/7/29《系統(tǒng)建模與仿真》87

p1

p2

t1

t2

p4

p5

p3

t3

t4

p6

p7

t6

t5

（a）初始

p2

p1

t1

t2

p4

p5

p3

t3

t4

t5

t6

（b）引發(fā)t1

p6

p7

3.5.3Petri網(wǎng)的變遷原則

p1

p2

t1

t2

p4

p5

p3

t5

t6

p6

p7

(c)

引發(fā)t2

t3

t4

p2

p1

t1

t2

p4

p5

p3

t5

t6

p6

p7

（d）引發(fā)t1和t2

t3

t4

3.5.3Petri網(wǎng)的變遷原則3.5.4Petri網(wǎng)的行為性質(zhì)Petri網(wǎng)的模型只給出系統(tǒng)的靜態(tài)結(jié)構(gòu)及特征，系統(tǒng)的動(dòng)態(tài)行為是在Petri網(wǎng)的運(yùn)行過程中體現(xiàn)出來的，主要由它的一些性質(zhì)來描述。狀態(tài)標(biāo)識(shí)為一個(gè)向量，代表網(wǎng)中相應(yīng)序號(hào)庫(kù)所中所含令牌的數(shù)量，它反映了令牌在網(wǎng)中的分布情況。定義(可達(dá)性)

對(duì)于Petri網(wǎng)N,若存在t∈T使得M[t>M’，則稱M’是從M直接可達(dá)的。若存在變遷序列Ρ=t1，t2，…，tk和標(biāo)識(shí)序列σ=M1，M2，…，Mk

使得M[t1>M1[t2>M2…Mk-1[tk>Mk,則稱Mk是從M可達(dá)的，記作Mo[σ>M

。所有由M可達(dá)的標(biāo)識(shí)集合記為R(N,M)?？蛇_(dá)性用于驗(yàn)證系統(tǒng)能否達(dá)到某種狀態(tài)。3.5.4Petri網(wǎng)的行為性質(zhì)給定一個(gè)Petri網(wǎng)(N，M0)，一定可以建立起表達(dá)其可達(dá)集R(N，M0)的一個(gè)樹狀結(jié)構(gòu)的圖形，稱之為Petri網(wǎng)(N，M0)，的可達(dá)樹?？蛇_(dá)樹具有如下一些屬性：

（1）可達(dá)樹在圖形結(jié)構(gòu)上呈倒立狀樹形；（2）從樹根出發(fā)，按照由樹根節(jié)點(diǎn)激發(fā)出的“使能變遷節(jié)點(diǎn)”個(gè)數(shù)來生長(zhǎng)出相同個(gè)數(shù)的支線，并將使能變遷標(biāo)注在對(duì)應(yīng)的支線旁，各個(gè)支線末端為相應(yīng)使能變遷發(fā)生后達(dá)到的新狀態(tài)標(biāo)識(shí)即新令牌分布，由此形成一批新的分支點(diǎn)，以這些分支點(diǎn)為起點(diǎn)，按相同原則，依次伸展；3.5.4Petri網(wǎng)的行為性質(zhì)（3）有限可達(dá)集對(duì)應(yīng)于有限可達(dá)樹，而無限可達(dá)集用有限可達(dá)樹來表示。具體引入以下附加規(guī)定：

a、分支的終止支點(diǎn)。伸展出的一個(gè)新節(jié)點(diǎn)在先前的支點(diǎn)或其它分支點(diǎn)出現(xiàn)過，該分支點(diǎn)終止延伸；

b、引入無限參量ω?？蛇_(dá)樹構(gòu)造過程中，如果某個(gè)支點(diǎn)M比由樹根M0到M的一條分支上的一個(gè)“中途”支點(diǎn)M*要大，即支點(diǎn)M和M*的每個(gè)位置節(jié)點(diǎn)的令牌數(shù)均有M(pj)≥M*(pj),則對(duì)支點(diǎn)M中滿足“>”關(guān)系的位置節(jié)點(diǎn)采用無限參量來替代令牌數(shù)。3.5.4Petri網(wǎng)的行為性質(zhì)

s3s1s2t3t2t1(1,0,0)(0,0,1)(0,1,1)(1,ω,0)(1,ω,0)(0,ω,1)(0,ω,1)t1t1t2t2t3t33.5.4Petri網(wǎng)的行為性質(zhì)定義(有界性)如果對(duì)于s∈S及任意M∈R(N，M0),都有M(S)≤K,則稱網(wǎng)是K—有界的,特別地，當(dāng)K=1時(shí)稱此網(wǎng)是安全的。

有界性保證了系統(tǒng)的緩沖區(qū)不會(huì)溢出,工件在某個(gè)操作階段不會(huì)堆積。有界性判別：一個(gè)Petri網(wǎng)(N，M0)為有界的,即其可達(dá)集R(N，M0)為有限，當(dāng)且僅當(dāng)Petri網(wǎng)的可達(dá)樹中不出現(xiàn)無限參量ω。安全性判別：一個(gè)Petri網(wǎng)(N，M0)是安全的,當(dāng)且僅當(dāng)Petri網(wǎng)的可達(dá)樹的所有支點(diǎn)的位置標(biāo)識(shí)中，只包含0和1兩類元。3.5.4Petri網(wǎng)的行為性質(zhì)3.5.4Petri網(wǎng)的行為性質(zhì)定義(死鎖)

對(duì)給定初始標(biāo)識(shí)即初始令牌分布M0的一個(gè)Petri網(wǎng)R(N，M0)，稱其一個(gè)變遷節(jié)點(diǎn)t為死鎖，如果對(duì)由初始令牌分布M0可達(dá)的任一令牌分布M∈R(N，M0)下，此節(jié)點(diǎn)變遷t都是不使能即不具發(fā)射權(quán)的。在工程系統(tǒng)如柔性生產(chǎn)系統(tǒng)等的設(shè)計(jì)中，務(wù)必要從結(jié)構(gòu)上盡可能避免死鎖的存在，以保證系統(tǒng)的信息和物料的運(yùn)行過程不致癱瘓。s4s3s1s2t3t2t1t43.5.4Petri網(wǎng)的行為性質(zhì)定義(活性)

對(duì)t∈T和M∈R(N，M0)，如果存在M’∈R(N,M),使得M’[t>,則稱

t是活的。所有的t∈T都是活的,則稱網(wǎng)N是活的。

活性保證了系統(tǒng)不會(huì)出現(xiàn)死鎖,生產(chǎn)可以正常連續(xù)進(jìn)行。在活性Petri網(wǎng)中,無論怎樣選取點(diǎn)火序列,都保證不會(huì)出現(xiàn)死鎖。死鎖的判別：一個(gè)Petri網(wǎng)(N，M0)的一個(gè)變遷t是死鎖的，當(dāng)且僅當(dāng)此變遷節(jié)點(diǎn)t不出現(xiàn)在Petri網(wǎng)的可達(dá)樹的任一分支上。3.5.4Petri網(wǎng)的行為性質(zhì)

s8s9s7s6s5s10s4s3s1s2t8t4t3t7t6t2t1t5M0=(1,1,1,0,0,0,0,0,0,0)t1

、t2

沖突，讓t1發(fā)生

s8s9s7s6s5s10s4s3s1s2t8t4t3t7t6t2t1t5M0=(1,0,0,1