論文閱讀：Eliminating Event Cancellation

發表於 2025-10-07 更新於 2025-10-21 分類於學習筆記 Disqus：

在simulation modeling的領域，有時會使用event cancellation的技巧──取消已經排程好的事件──來建立simulation model。本篇論文提出一個消除event cancellation的一般化方法，並且以兩個simulation model：preemptive priority queue 和 queue with a state dependent service rate，作為示範。

論文資訊

E. L. Savage and L. W. Schruben, “Eliminating Event Cancellation In Discrete Event Simulation,” in Proceedings of the 1995 Winter Simulation Conference, 1995.

論文內容

Event cancellation是建立模擬模型時相當好用的一個技巧，但是這會使得 infinitesimal pertubation analysis和structural model equivalence兩種模擬系統的分析方法變得無效。這兩種分析方法建立在Generalized Semi-Markov Process的模型表示，而這個模型通常不允許使用event cancellation。

這篇論文用event graph來說明：一個event發生時，會根據條件來排程另一個event。一個event graph model (EGM)由edges和vertices表示，$G = \{E, V\}$，以及對應的狀態空間 $S$(state space)。$v$ 表示某個事件，$e = (v_o, v_d)$ 表示某條edge，據此可以定義以下的集合：

$F = \{f_v: \forall v \in V\}$，和事件相關的state change。
$P = \{p_e: \forall e \in E\}$，execution priority expressions，用來打破time-ties的困境。
$T = \{t_e: \forall e \in E\}$，inter-event delay。
$C = \{c_e: S \rightarrow {\cal{R}},\ \forall e \in E\}$，排程條件，0表示false。

排程條件不為0的edges稱作active edges。具體的模擬模型則是以indices來建立。和FSM、Petri nets等模型不同，EGM的vertices不是用來表示狀態的值，而是用來指示狀態的改變，作者認為這和微分方程構成的系統模型相當相似。

作者提及有些人會在EGM增加其他特性：可以取消事件的edge、在edge增加屬性以儲存事件清單(event list)的值或是vertices的參數。不過，作者說圖靈機的模型已經證明這些功能並非必要，因此接著探討取消事件(event cancellation)這個動作，因為event cancellation在本質上和其他附加的特性不太一樣。接下來用兩個例子來說明如何消除event cancellation。

EX1. Preemptive priority queue 搶先優先佇列

在這個例子裡，有一個server，兩種顧客，type 1的顧客擁有優先權：如果type 2的顧客正在接受服務，而來了type 1的顧客，則server會中斷type 2顧客的服務、優先服務type 1的顧客，直到queue裡沒有任何type 1顧客時，才會繼續完成type 2顧客的服務。圖A為使用到cancelling edge的EGM。

圖A，改自論文的Figure 1。

各個edge上的排程條件如下，其中 $S = 1$ 表示server idle，$S = 0$ 表示server busy(紅字為發生preemption的條件，黃字表示經過修改)：

條件(i)，$S = 1$。
條件(ii)，$S = 0$ 且 $\text{PR} = 0$。
條件(iii)，$Q(1) > 0$ 且 $\text{RTIME} = 0$ (刪除 $S = 1$ 因為必然符合)。
條件(iv)，$Q(1) = 0$ 且 $Q(2) > 0$ 且 $\text{RTIME} = 0$ (刪除 $S = 1$ 因為必然符合)。
條件(v)，$Q(1) > 0$ 且 $\text{RTIME} \neq 0$。

先前也說過，每一個vertex/event意味著狀態變化，所以也把state change條列如下，黃字表示經過修改(其中 $x = 1\ \text{or}\ 2$，表示顧客的type；$\text{PR} = 0$ 表示目前服務的顧客無優先權，$\text{PR} = 1$ 表示目前服務的顧客有優先權)：

$\text{Enter}(x) \rightarrow Q(x) = Q(x) + 1$
$\text{Start}(x) \rightarrow Q(x) = Q(x) - 1,\ S = 0,\ \text{PR} = 2 - x,\ \text{FTIME} = \text{CLK} + t_s(x)$
$\text{Leave}(x) \rightarrow S = 1,\ \text{PR} = 0,\ \textcolor{yellow}{\text{RTIME} = 0\ \text{if }x = 2}$
$\text{Preemp} \rightarrow Q(1) = Q(1) - 1,\ S = 0,\ \text{PR} = 1,\ \textcolor{yellow}{\text{RTIME} = \text{RTIME} + \text{FTIME} - \text{CLK} + t_s(1),\ \text{FTIME} = \text{CLK} + t_s(1)}$

當中 $\text{RTIME}$ 為服務到一半的type 2顧客被type 1顧客搶先後，等待結束服務的時間(註1)。$\text{FTIME}$ 為目前顧客結束服務的時間點(註2)。圖A裡紅色的edge表示搶先(preemption)，發生在條件(ii)和條件(v)；發生preemption時，原本已經排程(e.g. 放到event list)的Leave2會被取消，即圖A中的藍色虛線。

圖B為不使用cancelling edge的EGM。作法為：排程Leave2之前，先檢查有沒有preemption的情形($\text{RTIME} \neq 0$)，有的話(條件(vi))就排程下一次檢查；沒有preemption的話(條件(vii))，就可以結束對type 2顧客的服務。新增的條件如下：

條件(vi)，$\text{RTIME} \neq 0$。
條件(vii)，$\text{RTIME} = 0$。

新增與修改的state change如下：

$\text{Start}(x) \rightarrow Q(x) = Q(x) - 1,\ S = 0,\ \text{PR} = 2 - x,\ \text{FTIME} = \text{CLK} + t_s(x),\ \textcolor{yellow}{t_{sl}(1) = t_s(1)\ \text{if }x = 1}$
$\text{Leave}(x) \rightarrow S = 1,\ \text{PR} = 0,\ \textcolor{yellow}{t_{sl}(1) = 0\ \text{if }x = 1}$
$\text{Preemp} \rightarrow Q(1) = Q(1) - 1,\ S = 0,\ \text{PR} = 1,\ \text{FTIME} = \text{CLK} + t_s(1),\ \textcolor{yellow}{t_{sl}(1) = t_s(1)}$
$\text{Check} \rightarrow \text{RTIME} = t_{sl}(1)$

注意 $\text{RTIME}$ 其實就是 $t_{sl}(1)$ (參考圖C)，即目前接受服務的type 1顧客的service time，是我自己新增的state variable。

圖B，改自論文的Figure 2。

圖C，說明 $\text{RTIME}$ 與 $t_{sl}(1)$ 的關係。

方法

這裡說明更一般的方法。

建立一個dummy event CheckV，然後把所有排程V都改成排程CheckV；把cancelling的動作改成讓變數VCancel加一，而每次事件CheckV發生，就讓VCancel減一，當Vcancel為零，CheckV就會排程事件V。

上述的方法假設cancelling edge的延遲為零(符合條件就馬上取消)。這個方法除了用在preemption(例如EX. 1)的情況，也適用於某事件V被多次排程，先排程的事件發生時間點早於後排程的事件發生時間點的情況。請見圖D。

圖D，如果先排程的事件發生時間點晚於後排程的事件發生時間點，
兩種做法就會有不同的結果。

要解決圖D的問題，可以給每次事件V的排程加上編號，來表示排程的先後順序。比如說用index $i$ 作為排程編號，$\text{VSTime}(i)$ (陣列)表示第 $i$ 個排程排定的事件發生時間點，$\text{VCancel}(i)$ (陣列)記錄第 $i$ 個排程是否取消，$\text{VOrder}$ (陣列)將排程編號依據 $\text{VSTime}(i)$ 從小排到大。使用這些陣列，就可以按照正確的順序取消排程。

EX.2 Single server queue with state-dependent service rate

論文提出第二個例子。在這個例子裡，有一個server，它的service rate是queue length $Q$ 的函數，service rate = $r(Q)$，並且 $r(0) = 1$。這裡定義service units $\text{SU}$ 為服務的基本單位，和service rate $r(Q)$ 的關係如下：

$$
\frac{\text{SU}}{r(Q)} = t_s
$$

每一個顧客接受服務時，都會隨機生成service time $t_s$，再根據當下的service rate，決定 $\text{SU}$。當顧客服務到一半，有新的顧客排隊、queue length改變時，原本排程好的Leave就要取消，並重新排程，因為service rate改變、剩餘的service time也改變了。請見圖E，圖中的藍色虛線為cancelling edge。

條件條列如下，$S = 0$ 表示server busy，$S = 1$ 表示server idle：

條件(i)，$S = 0$。
條件(ii)，$S = 1$。
條件(iii)，$Q > 0$。

與事件相關的state change則條列如下，其中 $\text{TF}$ 為time left to finish，即目前顧客服務剩餘時間，初始值即為 $t_s$：

$\text{Run} \rightarrow S = 1$
$\text{Enter} \rightarrow Q = Q + 1,\ \text{TF} = (\text{FTIME} - \text{CLK})*\frac{r(Q - 1)}{r(Q)},\ \text{FTIME} = \text{CLK} + \text{TF}$
$\text{Start} \rightarrow S = 0,\ Q = Q - 1,\ \text{TF} = \text{SU}/r(Q),\ \text{FTIME} = \text{CLK} + \text{TF}$
$\text{Leave} \rightarrow S = 1$

圖E，改自論文的Figure 3。

接著要把cancelling edge刪除。如果先排程的事件發生時間點都早於後排程的事件發生時間點，就不會發生圖D的情況，可以加上一個Check的vertex來取代cancelling edge。可是在這個例子裡，如果 $r(Q)$ 為遞增函數(排隊的人愈多，service rate愈快)，當原本的Leave取消後重新排程，新的Leave發生時間點一定比原本(被取消)的發生時間點還要早，因為service rate增加了。如果是這樣，就一定會發生圖D的狀況。

那麼該如何消除cancelling edge？當然可以用上一節提到的一般化方法(圖D下方段落)。這裡用另一種方法，思路是這樣的：如果可以在下一個顧客抵達前結束服務，就可以排程Leave；如果做不到，不要排程Leave。因此定義新的state variable $\text{TNA}$ 為下一個顧客抵達的時間點。新增的條件如下：

條件(iv)，$S = 0$ 且 $\text{TF} \leq \text{TA}$。
條件(v)，$\text{TF} \leq \text{TNA} - \text{CLK}$。

修改過的state change如下(沒有新增事件)：

$\text{Enter} \rightarrow Q = Q + 1,\ \text{TF} = (\text{FTIME} - \text{CLK})*\frac{r(Q - 1)}{r(Q)},\ \text{FTIME} = \text{CLK} + \text{TF},\ \text{TA} = t_a,\ \text{TNA} = \text{CLK} + \text{TA}$

圖F即為不使用cancelling edge的EGM。

圖F，改自論文的Figure 4。

結尾評論

論文最後提及，這個消除cancelling edge的一般化方法沒有將隨機生成的time delay/time interval(如 $\text{TF}$)作為state variable，但是論文提出的兩個例子，使用的方法都有這麼做。作者不確定這會對系統分析造成什麼影響。

讀後想法

本身不是研究這個領域的，但是作為課堂報告還是要仔細讀完。老師說這篇論文的EGM有許多地方要修正，確實如此。那這篇論文到底是怎麼通過審核的？

論文提出了一個一般化的方法來避免使用cancelling edge，一言以蔽之就是預防勝於治療。嗯，就這樣。畢竟我也不清楚為什麼要這麼做(沒時間研究附錄的內容)，對我來說只能算是一個modeling的技巧。

註

原本論文裡Preemp的狀態變化，$\text{RTIME}$ 的部分是這樣寫的：$\text{RTIME} = \text{FTIME} - \text{CLK}$。這裡改寫 $\text{RTIME}$ 的算法。點擊以返回論文。
原本論文裡 $\text{FTIME}$ 是這樣寫的：$\text{FTIME} = \text{FTIME} + t_s(1)$。這裡修改了 $\text{FTIME}$ 的定義，所以算法也改寫。點擊以返回論文。

附錄

參考資料

無。