CodeHighlight

2013年5月6日 星期一

[Queueing theory]Birth-Death process(出生-死亡過程)

        這世界上可以分析的系統非常多,從乘客搭車、商店排隊、銀行辦事、工廠產出、流量分析...等等,但是可用的數學模型是有限的,因此在模擬時,為了使複雜度調整到可以處理的程度,因此會針對系統做些簡化。因此,逐漸產生了一些固定的模型供使用,其中Birth-Death process是一個相當著名的例子:

在這個Process中,State的轉換是符合連續時間下的馬可夫鍊(CTMC),且已知:
  • Arrival Rate: Poisson Distribution(l)
    • l(k) = 在狀態K時,轉換到狀態k+1的機率
  • Departure Rate: Poisson Distribution(m)
    • m(k) = 在狀態K時,轉換到狀態K-1的機率
  • 極短時機內,最多一人到達
  • 每個客人到達時間互相獨立
根據以上,可以畫成以下狀態圖:
State diagram of a birth-death process

在這個系統中,由於沒有限定顧客的來源,因此在任意State下,其Arrival Rate皆相同:
l(k) = l
同理,由於沒有限定系統內的Buffer大小,因此每個客人都會被接受,其Departure Rate為:
m(k) = m

那在這個系統中的穩定態,基於「Flow in = Flow out」:
(Hint:P(0) = 在狀態0的機率)

  • 狀態0:mP(1) = lP(0)
  • 狀態1:lP(2) + mP(0) lP(1) + mP(1)
  • 狀態2:lP(3) + mP(1) = lP(2) + mP(2)
  • ......
  • 狀態nlP(n-1) + mP(n+1) = lP(n) + mP(n)

上述關係式簡化後,會變成:
 P(n) = (l/m)^n * P(0)
P(0) = 1 - (l/m)

2013年5月4日 星期六

[Queueing theory]系統描述與一般性穩定態計算(General Equilibrium Solution)

是說最近在上Queueing Theory,除了概念要多想多模擬才能理解外,
最困擾的是基礎數學功力不夠呀!
果然出來混總是要還的

----------------------------碎碎念結束---------------------------

在一個系統中,不同狀態的轉換都是根據機率決定是否發生,
不過,要將一個系統轉換成數學可以處理的模式,
則需要我們「定義」這個系統,以便符合我們可用的數學模型

以火車站為例:一個車站內會有很多人來搭火車,
乘客的目的是希望可以搭到車,就以「到車站 -> 等車 -> 上車」這個流程來看。
根據Kendall notation,我們可以定義:

  • State(系統狀態):車站內的人數
  • Transition rate(狀態往前的機率):乘客到車站的機率
  • Departure rate(狀態往後的機率):乘客上車的機率
  • Queue Size/Buffer Size(系統內的上限);車站可以容納等車人數的多寡
  • Number of parallel server(同時有多少Server提供服務):一次會有多少車來
  • Queueing discipline(提供服務的順序):大家上車的順序
當然,上述是簡化後的例子,實際情況會比描述得更為複雜,
不過這邊做一定程度的簡化,使其可以利用數學工具做一定程度的評估。


在上面的例子中,每個State代表車站內的人數,對於要關注這個系統的人來說,
我們感興趣的部分可能會有:
  • 這個車站平均有多少人?
  • 平均每個乘客要等多久?
  • 車站大多數時候會有多少人在等車?
  • 要如何調整發車才可以減少等候時間?
  • ......
為了要計算這些,我們可以從「在某狀態下的機率」作為起點,
假設在一個穩定的系統中,單一狀態的機率在觀察時間夠長的話,
其機率會固定在一個特定的值,我們稱之為pk

以上述式子來說,代表「狀態k機率的穩定態,其機率等於在無窮遠的時間下,得到之狀態k的機率」。

而我們假設,進入這個系統的機率是λ;離開這個系統的機率是µ
以上面的例子(Birth-Death系統)為例,會有以下特性:
  • 車站內的人數最小為0,不會有負數
  • 所有狀態的機率和為1(表示所有狀況都考慮在內)
而一個系統在穩定態時,系統的Flow in = Flow out,代表該系統進出的機率會是相同的,
這樣系統內的人數才會維持一定。也就是說:

Flow in = Flow out

→ 進入該狀態的機率 = 離開該狀態的機率

前個狀態下的進入率+下個狀態的離開率 = 現在狀態下的進入與離開率和

→ 


根據以上特性,我們可以推出在狀態K的機率為:

狀態0的機率是:


利用這兩個關係式,就可以針對我們定義的系統,計算在不同情境下,在穩定態的機率。
根據這些機率,配合上Little's Law,就可以方便的算出相關的系統表現了!



參考資料:

2013年5月2日 星期四

[Queueing theory]Kendall notation - Queueing系統的描述方式

針對一個Queueing的系統,其中有許多的參數和特性,為了要有個簡單且明確的表示方法。這邊使用由Kendall提出的表示法:「Kendall notation」

這表示法是由一連串的「/」區分不同的特性,表示法如下:

A/B/X/Y/Z
其中個別代表的意思是:

  • A:Arrival Pattern,Request到達系統的分布特性
  • B:Service Pattern,Request離開系統的分布特性
  • X:Number of parallel server,單一系統同時有幾個Server進行服務
  • Y:System Capacity,系統內Buffer的大小
  • Z:Queueing discipline,系統處理Request的方式
其中A和B可以有下列幾個類型:
  • Exponential Distribution (M)
  • Deterministic (D)
  • General Distribution (G)
  • Erlang type k (k=1,2,...) (Ek)
  • Mixture of k expoenetials (Hk)
  • Phase type (PH)
而X和Y則是給予數字,代表該系統的Buffer大小和可處理之Service數,
Z的部分則有:
  • FCFS:first come, first served,先到先處理
  • LCFS:last come, first served,後到先處理
  • RSS:random selection for service,隨機取Buffer內的處理
  • PR:priority,依優先權處理
  • GD:general discipline
一般來說,系統大多是取前面的A/B/X做描述,這時候後面的Y和Z各自代表「系統內的Buffer Size無限大」和「採用FCFS處理」。

參考資料:
Queue的標記法notation