離散事件動態系統

人們在生產活動和社會活動中，經常遇到一類複雜的系統，這類系統中有許多事件時而出現，時而消失，時而動作，時而停止，而啓動和停止都發生在一些離散的時刻，並帶有一定的隨機性。例如，港口中船舶的停靠碼頭、生產線上機牀的啓停、電話的接通和斷開、計算機系統中某項作業的進行和退出，凡此種種，都帶有上述特點，這類系統叫做離散事件動態系統(DEDS)。隨着生產和科技的日益發展，以及人類社會交往的日趨頻繁，這類系統的數量和種類也越來越多。 ^[1] 

這類系統的分析研究，需要考慮下面這些特點：

(1)它是由事件驅動發生變化的，帶有不連續性。

(2)但考核它的性能的指標卻帶有連續特點，例如平均吞吐率、等候時間、利用率等。

(3)隨機特點。因為有些驅動系統的事件的到來帶有隨機特點(如顧客的到來、電訊報文的到達)，此外任務的完成、任務間的銜接等也都有一定的隨機性，所以常常需要使用處理概率事件與隨機過程的方法和技術。

(4)層次性特點。由於這類系統一般是人造複雜系統，所以多半是按層次組織的，例如在空間跨度上，有單機、機組、生產線、車間、工廠幾個層次，在時間跨度上，有小時、班(8小時)、日、周、月、年等層次，在組織結構上更是如此。這樣我們不得不對每個層次都建立相應的分析方法，有時需要集成，有時又需要分解，上下還必須協調。

(5)動態性特點。我們必須研究這類系統的動態行為和過渡過程。

(6)計算複雜性。在這類系統中，由於組成單元數目大，事件狀態多，所以常有“組合爆炸”的危險，這給分析計算帶來了很大困難。 ^[1] 

由於DEDS的狀態空間缺乏易操作的數學結構，所以難以用傳統的基於微分或差分方程的方法來刻畫其性質。研究的最基本問題仍是系統的建模，當前公認的理論框架包含以下3種模型：

(1)邏輯層次模型：只涉及物理狀態和事件之間的關係，屬於確定性模型，主要包括形式語言/有限自動機和Petri網，用於定性分析。近年的動向是在確定模型中引入隨機因素和時間因素，其中計時Petri網和隨機Petri網比較重要；

(2)時間層次模型：不僅涉及事件和狀態之間的關係，而且要在物理的時間級上刻畫與分析演化過程，主要方法為雙子代數(dioid)，網絡演算屬於這一層次；

(3)統計性能層次模型：起源於對隨機服務系統的研究，主要方法是排隊論和排隊網絡，理論分析的基礎是過程的馬爾可夫性。

此外還有運行分析法、平均值分析法、近似分析法和攝動(perturbation)分析法等，國內對DEDS系統的研究處於國際前列。 ^[2] 

總體來説，有兩大類方法：一類是解析法，一類是模擬仿真(隨機仿真)方法。

在解析法中，有隨機服務系統理論(或稱排隊論)的方法、利用皮特利網(Petri Nets)的方法、極小極大代數法、攝動分析法等；模擬仿真方法則是利用計算機進行仿真，產生隨機事件，大量進行仿真實驗，再進行統計。過去這類問題因屬運籌學範圍，所以多半在運籌學領域內研究。後來由於涉及動態分析，控制理論範圍內也對它進行了研討。看來僅靠定量分析、利用算法已經不夠，還需要發揮人工智能、知識工程的作用，併發揮計算機科學技術的威力。看來在今後若干年內，針對某幾類系統的分析方法和工具會日益成熟並獲得應用，而關於一般理論的探索，也可能有一個良好的開端。 ^[1] 

人類科學技術的進步產生了為數眾多的人造動態系統，如產品製造系統，計算機通信系統，軍事C³1系統等。這些系統難以用傳統意義下的微分方程或差分方程來描述。對系統進程起決定性作用的是一批離散事件，而不是連續變量。系統行為所遵循的是一些複雜的人為規則，而不是物理學定律或廣義物理學定律。這些動態系統的狀態的變化取決於離散的時間值，而不是時間的連續變量|。美國哈佛大學教授Y．C．Ho在20世紀80年代初將這類系統稱為離散事件動態系統(Discrete Event Dynamic Systems，DEDS)。複雜DEDS系統的建模，最終可能需要同時藉助於運籌學、系統控制理論、人工智能等多學科方法的綜合運用。

由於製造系統領域涵蓋相當多數量和種類的DEDS系統，近10餘年來製造系統的DEDS建模方法和行為特徵的研究成為國際製造工程和控制自動化領域一項十分重要的研究課題。DEDS的研究從三個層次上展開：邏輯層次、時間層次和統計層次。它們分別針對不同的需要，建立相應的系統研究模型。經過多年的積累，DEDS已經建立了多層次、多側面、多種模型的描述、分析體系。隨機現象在DEDS系統中非常普遍，無論是在製造系統，計算機系統，還是在通訊系統中，最後都要涉及隨機品質評估和優化的問題。隨機DEDS研究一直是DEDS領域中最活躍的分支，常常採用的方法主要有排隊網絡(Queuing Network)方法和攝動分析(Perturbation Analysis，PA)方法。 ^[3]