管理學系統(tǒng)建模與仿真第三章

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

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

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

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

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

如：在“顧客到達”與“服務開始”兩個事件之間存在一個“排隊等候”活動；“服務開始”與“服務結束”之間存在“顧客接受服務”活動。

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

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

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

如：在隨機服務系統(tǒng)模型中，“顧客”有“等待服務”和“接受服務”等狀態(tài)，“服務員”有“忙”和“閑”等狀態(tài)?；顒涌偸桥c一個或幾個實體的狀態(tài)相對應，狀態(tài)可作為動態(tài)屬性進行描述。12《系統(tǒng)建模與仿真》2024/1/32024/1/3《系統(tǒng)建模與仿真》133.1.1離散事件系統(tǒng)要素13《系統(tǒng)建模與仿真》2024/1/32024/1/3《系統(tǒng)建模與仿真》143.1.1離散事件系統(tǒng)要素7、仿真時鐘仿真時鐘用于表示仿真時間的變化及作為仿真過程的時序控制，它是系統(tǒng)運行時間在仿真過程中的表示。仿真時鐘推進的方式：固定步長時間推進機制下次事件時間推進機制

仿真時鐘推進的時間間隔稱為仿真步長，離散事件系統(tǒng)仿真時鐘的推進步長是隨機的，取決于系統(tǒng)的當前狀態(tài)和事件發(fā)生的條件。14《系統(tǒng)建模與仿真》2024/1/32024/1/3《系統(tǒng)建模與仿真》153.1.1離散事件系統(tǒng)要素8、系統(tǒng)環(huán)境

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

實體流圖法(EntityFlowChart，EFC)采用與計算機程序流程圖相類似的圖示符號和原理，建立表示臨時實體產生、在系統(tǒng)中流動、接受永久實體“服務”，以及消失等過程的流程圖。

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

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

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

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

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

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

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

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網的變遷原則3.5.4Petri網的行為性質Petri網的模型只給出系統(tǒng)的靜態(tài)結構及特征，系統(tǒng)的動態(tài)行為是在Petri網的運行過程中體現(xiàn)出來的，主要由它的一些性質來描述。狀態(tài)標識為一個向量，代表網中相應序號庫所中所含令牌的數(shù)量，它反映了令牌在網中的分布情況。定義(可達性)

對于Petri網N,若存在t∈T使得M[t>M’，則稱M’是從M直接可達的。若存在變遷序列Ρ=t1，t2，…，tk和標識序列σ=M1，M2，…，Mk

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

。所有由M可達的標識集合記為R(N,M)?？蛇_性用于驗證系統(tǒng)能否達到某種狀態(tài)。3.5.4Petri網的行為性質給定一個Petri網(N，M0)，一定可以建立起表達其可達集R(N，M0)的一個樹狀結構的圖形，稱之為Petri網(N，M0)，的可達樹?？蛇_樹具有如下一些屬性：

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

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

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

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

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

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

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

t是活的。所有的t∈T都是活的,則稱網N是活的。

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

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

、t2

沖突，讓t1發(fā)生

s8s9s7s6s5s10s4s3s1s2t8t4t3t7t6t2t1t5M0=(1,0,0,1,0,0,0,0