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

《系統(tǒng)建模與仿真》第三章離散事件系統(tǒng)建模管理科學與工程學院付赟2024/1/3《系統(tǒng)建模與仿真》23.1離散事件系統(tǒng)離散事件系統(tǒng)的性質(zhì)與連續(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)的內(nèi)部狀態(tài)變化是隨機的，同一個內(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)計規(guī)律。系統(tǒng)的內(nèi)部狀態(tài)只在離散的隨機時間點上發(fā)生變化，且狀態(tài)在一段時間內(nèi)保持不變。因此在建立離散事件系統(tǒng)模型時，只需考慮系統(tǒng)內(nèi)部狀態(tài)發(fā)生變化的時間點以及產(chǎn)生這些狀態(tài)變化的原因，而不用描述系統(tǒng)內(nèi)部狀態(tài)發(fā)生變化的過程。3《系統(tǒng)建模與仿真》2024/1/32024/1/3《系統(tǒng)建模與仿真》41、實體1）定義：實體(Entity)是指一個系統(tǒng)邊界內(nèi)部的客觀對象，離散事件系統(tǒng)是由實體組成的。2）分類：臨時實體

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

經(jīng)常處于系統(tǒng)之內(nèi)，其數(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)的工作過程實質(zhì)上就是臨時實體流動和接受加工、處理的過程。如：排隊的顧客，待加工的工件等永久實體只要系統(tǒng)處于活動狀態(tài)，它就一定存在。如：商店的營業(yè)員，加工設(shè)備等臨時實體按一定規(guī)律不斷到達，在永久實體作用下通過系統(tǒng)，最后離開系統(tǒng)。系統(tǒng)狀態(tài)的變化主要是由實體的狀態(tài)變化而產(chǎn)生的。5《系統(tǒng)建模與仿真》2024/1/32024/1/3《系統(tǒng)建模與仿真》62、事件1）定義

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

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

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

8《系統(tǒng)建模與仿真》2024/1/32024/1/3《系統(tǒng)建模與仿真》93.1.1離散事件系統(tǒng)要素4、進程進程(Process)是由與某類實體相關(guān)的事件和若干活動組成的，它描述了這些事件和活動間的相互邏輯關(guān)系和時序關(guān)系。如：“顧客到達系統(tǒng)—排隊—開始接受服務(wù)—服務(wù)結(jié)束”的過程就構(gòu)成了一個進程。進程是事件與活動的組合，它可以更加完整地描述實體狀態(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ù)變量表示。在仿真建模中，只需要使用與研究目的相關(guān)的一部分就可以了。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é)調(diào)并定義狀態(tài)的屬性時，則認為系統(tǒng)處于特定狀態(tài)。

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

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

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

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

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

——兩類顧客競爭資源電影院雇用一名售票員同時負責電影票的銷售和對電話問詢者的咨詢服務(wù)。窗口服務(wù)比電話服務(wù)優(yōu)先級高。問詢者打來的電話由電話系統(tǒng)存儲后按先來先服務(wù)的規(guī)則一一予以答復(fù)。建模的目的是研究售票員的忙閑率。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個活動，對應(yīng)的是“閑”和“忙”兩種狀態(tài)購票者有“排隊”和“購票”2個活動，對應(yīng)的是“等待”和“購票”兩種狀態(tài)問詢者有“排隊”和“問詢”2個活動，對應(yīng)的是“等待”和“問詢”兩種狀態(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)處于排隊等待中的顧客，如果售票員完成了對前一顧客的服務(wù)，則進入“購票”或“問詢”狀態(tài)；否則，繼續(xù)保持“等待”狀態(tài)37《系統(tǒng)建模與仿真》2024/1/33.2.3實體流圖法的實例分析（4）分析引起狀態(tài)變化的事件“購票者到達”、“問詢者到達”、“購票者結(jié)束排隊”或者“問詢者結(jié)束排隊”導(dǎo)致售票員“服務(wù)”活動的開始“購票者買票后離去”或“問詢者咨詢后離去”導(dǎo)致售票員“服務(wù)”活動結(jié)束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）確定模型參變量購票者到達時間電話問詢者到達時間售票服務(wù)時間電話服務(wù)時間（8）給出排隊規(guī)則排隊規(guī)則：FIFO服務(wù)規(guī)則：購票者和問詢者分別排隊，優(yōu)先進行購票活動41《系統(tǒng)建模與仿真》2024/1/33.2.3實體流圖法的實例分析兩個與服務(wù)規(guī)則有關(guān)的判斷和特殊操作當“電話問詢者”和“窗口購票者”同時到達，且售票員處于“閑”的狀態(tài)，后者接受服務(wù)，前者加入電話隊列當服務(wù)完畢，且購票隊列和電話隊列均不為空時，先進行購票服務(wù)由于本例中有兩類臨時實體同時流動,因此可能出現(xiàn)資源沖突,對此類問題的描述,活動周期圖有其獨到之處.42《系統(tǒng)建模與仿真》2024/1/33.2.4模型的人工運行建立實體流程圖模型后，選取有代表性的例子將流程圖全部走一遍，即所謂人工運行。人工運行模型要求遍歷流程圖的各個分支和實體的各種可能狀態(tài)，在時間逐步變化的動態(tài)條件下，分析事件的發(fā)生及狀態(tài)的變化過程，以檢查模型的組成和邏輯關(guān)系是否正確。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ù)來產(chǎn)生2024/1/344《系統(tǒng)建模與仿真》3.2.4模型的人工運行模型需按照一定的規(guī)則運行，本模型的人工運行規(guī)則如下：規(guī)則1——確定當前時間模型人工運行開始時，取當前時間TIME=t0（初始仿真時刻）人工運行開始后，當前時間逐步向前推移，且遞取下一最早發(fā)生事件的發(fā)生時刻如果當前時間有顧客到達事件發(fā)生，轉(zhuǎn)規(guī)則2若有顧客離去事件發(fā)生，則轉(zhuǎn)規(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模型的人工運行令A(yù)1=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活動周期圖法實體流圖法中，實體的行為模式在有限的幾種情況之間周而復(fù)始地變化，表現(xiàn)出一定的生命周期形式如：理發(fā)員在“忙”和“閑”之間不斷變化；顧客在“到達”、“等待”、“理發(fā)”和“離去”之間變化活動周期圖法（ActivityCycleDiagram，ACD）正是基于這樣的思想而逐步形成的一種離散事件建模方法2024/1/350《系統(tǒng)建模與仿真》3.3.1活動周期圖概述以直觀的方式顯示了實體的狀態(tài)變化歷程和各實體之間的交互作用關(guān)系，便于理解和分析。充分反映各類實體的行為模式，并將系統(tǒng)的狀態(tài)變化以“個體”狀態(tài)變化的集合方式表示出來，因此可以更好地表達眾多實體的并發(fā)活動和實體之間的協(xié)同關(guān)系。但是，它只描述了系統(tǒng)的穩(wěn)態(tài)，而沒有表示系統(tǒng)的瞬態(tài)，即活動的開始和結(jié)束事件。2024/1/351《系統(tǒng)建模與仿真》活動周期圖建模方法將實體的狀態(tài)分為靜寂(Dead)和激活(Active)兩種。(a)靜寂狀態(tài)

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

靜寂狀態(tài)通常表示無活動發(fā)生，是實體等待參加某一活動時的狀態(tài)，其持續(xù)時間在模型中無法事先確定，取決于有關(guān)活動的發(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表示一個或單位實體從產(chǎn)生到消失的循環(huán)過程；永久實體的ACD表示一個或幾個實體被占用和釋放的循環(huán)往復(fù)過程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ī)則和服務(wù)規(guī)則2024/1/356《系統(tǒng)建模與仿真》3.3.2活動周期圖法建模舉例例3：機床加工系統(tǒng)的活動周期圖法建?！僮鞴び行菹嫴璧臋?quán)利考慮一個簡單的加工車間。車間內(nèi)有數(shù)臺自動機床，由一名工人負責看管。工人的任務(wù)是：①如果機床的刀具完好，則為機床安裝工件，然后按下運行按鈕；②如果機床的刀具損壞，則先要重裝刀具，然后執(zhí)行任務(wù)①。只有當機床完成一次自動加工工序，并停止運行后，工人才能執(zhí)行上述兩項任務(wù)。假定每臺機床均可加工各種工件，并且不會發(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)引入“預(yù)備”、“停機”兩種靜寂狀態(tài)：滿足交替原則的要求2024/1/3《系統(tǒng)建模與仿真》593.3.2活動周期圖法建模舉例工人只要不從事“安裝刀具”和“安裝工件”的工作，就可從事“其他活動”。即，“等待”是“其他活動”的唯一前置條件。問題：限定工人每隔2h才能休息10min，如何在活動周期圖中表示？辦法：引入虛擬實體——工人休息的權(quán)力2024/1/3《系統(tǒng)建模與仿真》603.3.2活動周期圖法建模舉例權(quán)力實體協(xié)同工人實體完成“飲茶”活動，其生命周期中要完成“計時”（RECORD）這一活動。為了滿足交替原則，增添“有權(quán)”(YES)和“無權(quán)”(NO)兩種狀態(tài)。權(quán)力實體的引入滿足了每隔一段時間方可進入某一活動的建模需要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活動周期圖法建模舉例服務(wù)規(guī)則當工人處于“等待”狀態(tài)時，是先飲茶休息，還是先工作（假定機床處于“停機”狀態(tài)且權(quán)力處于“有權(quán)”狀態(tài)），其選擇取決于模型參數(shù)的值活動周期圖中允許進行分支處理，這時分支狀態(tài)需要有一個判斷變量，根據(jù)判斷變量的取值情況，可以確定實體的走向。2024/1/3《系統(tǒng)建模與仿真》643.3.2活動周期圖法建模舉例例4：貨物運轉(zhuǎn)系統(tǒng)大型貨車從工廠拉貨到轉(zhuǎn)運站，將貨卸在固定的倉位。運來的貨物經(jīng)分揀后放在另外的專用倉位，由小貨車運往客戶。運轉(zhuǎn)站內(nèi)有兩個卸貨倉位，4個裝貨倉位，每個倉位前均只能停放一輛貨車。貨物由10名工人負責裝卸，裝卸一車貨物需要2名工人。運送貨物的大小貨車首先從公路上拐進運轉(zhuǎn)站門口的一個停車場，然后經(jīng)過一條通道駛往各自的倉位。為了便于辦理手續(xù)，通道被分為兩半，左邊出車，右邊進車，而且進出通道只能容兩輛小貨車同時行進。大車的優(yōu)先級高于小車，出車的優(yōu)先級高于進車。倉位有空閑時才放貨車進入通道。2024/1/3《系統(tǒng)建模與仿真》65停車場通道3.3.2活動周期圖法建模舉例建模目的是研究在一定的貨物吞吐量下設(shè)幾個卸貨倉位比較合適。不考慮貨物數(shù)量的影響。實體：大貨車、小貨車、卸貨倉位、裝貨倉位、工人、進站通道和出站通道7個實體：2個臨時實體和5個永久實體2024/1/3《系統(tǒng)建模與仿真》663.3.2活動周期圖法建模舉例（1）大貨車由系統(tǒng)“外部”逐個“到達”，經(jīng)停車場“排隊”后，“駛?cè)搿毙敦泜}位“等候”工人“卸貨”，“卸空”后“駛離”轉(zhuǎn)運站。激活狀態(tài)：“到達”、“駛?cè)搿?、“卸貨”和“駛離”協(xié)同活動：“外部”、“等候”、“排隊”和“卸空”“駛?cè)搿被顒影l(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服務(wù)規(guī)則：大小貨車各排一隊，裝卸工、進出通道優(yōu)先為大貨車服務(wù)，優(yōu)先安排貨車離開貨場2024/1/3《系統(tǒng)建模與仿真》733.3.3模型的人工運行首先確定系統(tǒng)的初始狀態(tài)按下列原則運行模型：規(guī)則1——活動的發(fā)生與執(zhí)行（1）活動的所有前置狀態(tài)中均有實體停留，且各類永久實體的數(shù)量超過或等于相應(yīng)資源占用量；（2）活動發(fā)生的約束條件已經(jīng)滿足。依次檢查每一活動，以判斷此活動是否可以開始，即此活動所要求的足夠的實體集合是否已經(jīng)存在于所有有關(guān)的前置隊列中。如果含有，則將這個實體集合的標志移入此活動的矩形內(nèi)，且計算出此活動的終止時間，并將此時間寫在該活動的矩形內(nèi)。當所有活動都檢查完后，轉(zhuǎn)向規(guī)則2。2024/1/3《系統(tǒng)建模與仿真》743.3.3模型的人工運行規(guī)則2——確定當前時間檢查所有活動的終止時間，選其最小值，并設(shè)置時鐘值為此選擇值，然后轉(zhuǎn)向規(guī)則3。規(guī)則3——活動的完成從所有已發(fā)生的活動中，檢出終止時間等于當前時間的臨時實體，刪掉為其標注的終止時間；然后將相應(yīng)臨時實體的標記移至其相關(guān)的后續(xù)狀態(tài)中。參與活動的各永久實體的資源量相應(yīng)增加，將參與活動的永久實體的后續(xù)狀態(tài)作標記，轉(zhuǎn)規(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網(wǎng)建模方法改變活動周期圖建模方法：取消臨時實體ACD中的“源”狀態(tài)，即不再考慮臨時實體的生命周期循環(huán)將活動看作是“開始事件+狀態(tài)+結(jié)束事件”，則，建模元素就變成“事件”和“狀態(tài)”，后者包括ACD中的激活狀態(tài)和靜寂狀態(tài)不強調(diào)實體模型之間的獨立性用集合論的語言描述后，可以建立規(guī)范的Petri網(wǎng)方法2024/1/3《系統(tǒng)建模與仿真》773.5.1Petri網(wǎng)的基本概念Petri網(wǎng)是由節(jié)點和有向弧組成的一種有向圖它有兩類節(jié)點：庫所，即狀態(tài)元素，它表示一個場所，而且在該場所存放了一定的資源，用“○”表示；變遷，它指資源的消耗、使用以及對應(yīng)狀態(tài)元素的變化，用“∣”表示。另外，資源指的是與系統(tǒng)狀態(tài)發(fā)生變化有關(guān)的因素。2024/1/3《系統(tǒng)建模與仿真》783.5.1Petri網(wǎng)的基本概念2024/1/3《系統(tǒng)建模與仿真》79Petri網(wǎng)定義：三元組N=(S,T;F)稱為Petri網(wǎng)的充要條件是：3.5.1Petri網(wǎng)的基本概念S：庫所集；T：變遷集F：由一個S元素和一個T元素組成的有序偶的集合，稱為N的流關(guān)系dom（F）：F所含序偶的第一個元素的集合cod（F）：第二個元素的集合N不能有孤立元素，即S,T,F均不能為空集3.5.2網(wǎng)系統(tǒng)網(wǎng)是系統(tǒng)靜態(tài)結(jié)構(gòu)的基本描述容量、標識和權(quán)重3.5.2網(wǎng)系統(tǒng)例5：有一條工業(yè)生產(chǎn)線，它要完成兩項工業(yè)操作，這兩項操作用t1和t2表示。第一個變遷t1將傳入生產(chǎn)線的半成品s1和部件s2用兩個螺絲釘s3固定在一起，變成半成品s4。第二個變遷t2再將s4和部件s5用3個螺絲釘s3固定在一起，得到新的半成品s6。完成操作t1和t2時都要用到工具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)標識庫所s中允許存放令牌的最大數(shù)量，其值標在表示庫所的圓圈旁，不標明時容量為∞（2）權(quán)W(x,y)表示變遷發(fā)生時消耗和產(chǎn)出的令牌數(shù)量，其值標在?。▁，y）上；不標明時表示權(quán)為1（3）令牌表示原料、部件、產(chǎn)品、人員、工具、設(shè)備、數(shù)據(jù)和信息等組成系統(tǒng)的“資源”，標識M(s)的值用令牌數(shù)表示3.5.2網(wǎng)系統(tǒng)2024/1/3《系統(tǒng)建模與仿真》853.5.3Petri網(wǎng)的變遷原則當變遷不斷發(fā)生時，網(wǎng)系統(tǒng)的狀態(tài)也不斷發(fā)生變化，這一過程稱網(wǎng)系統(tǒng)的執(zhí)行。2024/1/3《系統(tǒng)建模與仿真》863.5.3Petri網(wǎng)的變遷原則1）一個變遷被授權(quán)發(fā)生，當且僅當該變遷的每一個輸入庫所中的令牌數(shù)大于或等于輸入弧的權(quán)值，并且該變遷的輸出庫所中已有的令牌數(shù)與輸出孤權(quán)值之和小于輸出庫所的容量；簡單地說就是“前面夠用，后面夠放”。2）變遷發(fā)生(點火)的充要條件是該變遷是授權(quán)的。3）變遷發(fā)生時，從該變遷的輸入庫所中移出與輸入弧權(quán)值相等的令牌數(shù)，輸出庫所中產(chǎn)生與輸出弧權(quán)值相等的令牌數(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網(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)的動態(tài)行為是在Petri網(wǎng)的運行過程中體現(xiàn)出來的，主要由它的一些性質(zhì)來描述。狀態(tài)標識為一個向量，代表網(wǎng)中相應(yīng)序號庫所中所含令牌的數(shù)量，它反映了令牌在網(wǎng)中的分布情況。定義(可達性)

對于Petri網(wǎng)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網(wǎng)的行為性質(zhì)給定一個Petri網(wǎng)(N，M0)，一定可以建立起表達其可達集R(N，M0)的一個樹狀結(jié)構(gòu)的圖形，稱之為Petri網(wǎng)(N，M0)，的可達樹。可達樹具有如下一些屬性：

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

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

b、引入無限參量ω?？蛇_樹構(gòu)造過程中，如果某個支點M比由樹根M0到M的一條分支上的一個“中途”支點M*要大，即支點M和M*的每個位置節(jié)點的令牌數(shù)均有M(pj)≥M*(pj),則對支點M中滿足“>”關(guān)系的位置節(jié)點采用無限參量來替代令牌數(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ì)定義(有界性)如果對于s∈S及任意M∈R(N，M0),都有M(S)≤K,則稱網(wǎng)是K—有界的,特別地，當K=1時稱此網(wǎng)是安全的。

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

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

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

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

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