離散事件模擬(1)：Single Server Queue Monitoring (SSQ)
以C# Winform實作佇列模擬系統
本文介紹簡單的單一server的離散事件系統，以C# Winform實作模擬系統，透過Piece wise Constant (Step Lines)展示系統中job數量的變化，並呈現有意義的相關統計量，輔助使用者認識離散事件系統運作。
專有名詞
首先，讓我們先了解一下該模擬系統的專有名詞。
關於系統
- Service system：服務系統。包含server和queue節點的系統。
- Server：泛指提供服務者。可以是加工機台、櫃台人員、運輸載具等，視場景而定。
- Job：泛指服務對象。可以是在製品、客人等，視場景而定。
- Queue：隊列。當server無法即時處理該job，則該job會進入到queue節點中。
關於時間
- Arrival time：job抵達時間。
- Delay time：job服務延遲時間。Job從抵達到開始接受服務的這段時間。
- Service time：job接受服務所需時間
- Completion time：job服務結束時間。
- Wait time：job等候時間。job在系統內的總時間Delay time+Service time。注意，不是指在隊列的時間！
系統時間示意圖
系統假設
這個應用程式在模擬只有一個server的服務系統，它基於以下幾點假設：
- 先進先出原則(FIFO)。每個job依照抵達時間先後處理，並且job抵達的順序和完成服務的順序一致。
- 系統容量無限制(capacity is infinite)。
- 服務是conservative，只要有job在服務系統內，server就是處於服務狀態，不會有閒置的情形發生。
- Not conservative。或稱約診式。與conservative相反的就是Not conservative。當job抵達服務系統，server即使目前沒有在忙碌中，也有可能不提供服務給新抵達的job，使其新抵達的job待在Queue中。白話說，就是server可能有閒置狀態，即便手中無事也不會立刻處理在Queue內的job。
輸出統計量
系統模擬的目的是得到洞見(insight)，藉由查看有意義的統計量來獲取服務系統的表現，實際採取何種統計量會取決於模擬的目的。舉例來說，對於一個job(消費者)來說，最重要的指標莫過於平均延遲時間(average delay)，或是第95百分位數的延遲時間；站在管理者的立場，倘若server價格昂貴，自然更在乎server的利用率(utilization)，有沒有發揮它應有的價值，此時server的忙碌比例就是一項更重要的指標。
通常統計量會從兩個面向來探討一個是Job-Averaged Statistics、另一個是Time-Averaged Statistics。
Job-Averaged Statistics
該面向的指標探究的是每一個job平均耗費的時間，單位是時間。
- 平均抵達間隔時間(average interarrival time) r_bar、平均服務時間(average service time) s_bar。
如果service rate小於arrival rate，則server服務job的效率有點低落。
- 平均延遲時間(average delay) d_bar、平均等候時間(average wait)w_bar
平均等候時間指得是平均待在服務系統的時間，因此會是延遲時間加上服務時間。
Time-Averaged Statistics
該面向的指標探究的是該面向的指標探究的是每單位的時間平均有幾個job，單位是job數量，使用積分的技巧計算。
- 節點中的時間平均數量(time-averaged number in the node)l_bar
節點就是指整個服務系統，看平均每個時間單位系統內有多少個job。計算公式就是類似積分的作法，累加每個時間單位的job的數量，最後再除以整個時間長度。
積分看起來嚇死人，但其實它就是單位面積累加的概念而已，範例如下，在t1~t2有2個job，在t2~t3有1個job，將單位時間內的面積累積至最後一個時段就等於總面積，之後再除以總時間t3-t1。
- 隊列的時間平均數量(time-averaged number in the queue) q_bar、 服務的時間平均數量( time-averaged number in service) x_bar
q_bar表示平均的job隊列數量(或稱隊列長度)，這是客戶所在乎的。 x_bar則是sever平均服務的job數量，這是服務提供者所關切的。因為這是基於單一server的系統， x_bar同時為server的利用率(utilization)，意味server在任何時間點忙碌的機率，x_bar的值會落在[0,1]。
用常理來思考 x_bar會與q_bar成正比，試想如果server總是忙得不可開交，job平均等待數量是不是會越多呢？
因為節點的數量等於隊列中的數量加上服務中的數量，因此以下成立
洞見(insight)
使用者可以從Sample資料夾內，打開我們隨機產生的一份如下的數據集Example122.dat，這是一份共有10個job的加工時間表格，關於這些時間名詞代表的意涵可以再對照本文關於時間的章節，這裡不再贅述，我們試著以這份toy dataset挖掘出一些有趣的資訊。
以下是透過程式模擬資料集的結果。
Step Lines展示的是不同時間點job數量變化，紅色代表的是在系統的總job數量，藍色是在server的job數量，綠色則是在Queue中的job數量。從圖表可以判斷該系統的運作邏輯合不合乎基本假設。
- 藍色線條在0和1兩者之間擺盪，合乎假設。因為系統只有一個server，且server同一時間只能處理一個job數量。
- 紅色線條的值會是藍色線條加上綠色線條，合乎假設。根據定義，所謂的在系統的總job數量，就是在server的job數量加上在Queue中的job數量。
從圖表來檢視大致合乎基本假設，接下來我們可以檢視介面上半部分的數據，諸如Average Interarrival Time或Average Service Time等等，皆為剛才列舉的相關統計量，完全可以由加工時間推導而得，這部分可以細看主程式碼。
Arrival Rate和Service Rate都是0.03左右，處於較為『供需均衡』的狀態，q_bar=0.71，表示平均只有0.71個job在等待；x_bar=0.92，表示平均有0.92個job正在進行加工，server利用率已經逼近最大值。客戶不常等待且server的利用率又高，這種雙贏局面是相當理想的系統！
下面右圖同樣是Example122.dat資料集所繪製的Step Lines，差別在於Service Time Factor設定為1.5，意味著將所有Service Time乘上1.5倍，這是在模擬服務時間較長的系統，例如招聘新進的員工或是使用老舊的機台等等，x_bar (server的平均加工job數量) 已到了0.97，q_bar (平均在Queue等待的數量) 則到了1.97，下方表格是更清楚的數據比較。
雖然站在提供服務者的角度，server的利用率往上提升了0.05，但是平均等待隊列人數卻從0.71飆升到1.97，所以該如何在這兩個指標進行取捨，需要基於不同情境來做討論。
程式的第二個分頁是在模擬不同的Service Time Factor，對 x_bar (server的平均加工job數量) 和q_bar (平均在Queue等待的數量)分別的影響，以此來幫助使用者做決策。
從圖表檢視基本上兩者指標呈現正相關，但X軸的x_bar到達1之後就無法在增加了，表示這唯一的Server已經全天候在運轉，此時再增加服務時間只會讓q_bar以更快速度增長，這時就必須考慮要不要多增加server數量來支援了。
