2009年1月31日 星期六

淺談Queueing Theory的歷史

每次學一個學科,就不得不將研究發展的經過好好了解一 下,外國書好像都有做到這點,反觀國內中文的書籍,通常不會提及,連最後的index都沒有,令人惋惜啊!

先說一下為何要談一下歷史,除了歌功頌德一番之外,就是要培養自我的人文素養,修身養性...學習新知歸學習新知,重點是要知道背後的精神,這樣學起來才有"深度"與"張力"。(就像電影"The Dark Knight"中的Joker和Batman)

The History of The Queueing Theory
(看看就好,沒經過查證的,這留給歷史學家去研究吧!)

1909
pioneer investigator, Danish mathematician, A. K. Erlang(排隊理論之父)
先驅:丹麥數學家A. K. Erlang(Agner Krarup Erlang)發表"The Theory of Probabilities and Telephone Conversations."
Erlang他觀察到電信系統(telecom)有這樣的特性(兩者之一):
  1. Possion input, exponential holding (service) times, and multiple channels (servers)
  2. Possion input, constant holding times, and a single channel

1927
E. C. Molina(全名Edward Charles Dixon Molina (December 13, 1877 - April 19, 1964))發表"Application of the Theory of Probability to Telephone Trunking Problems"在Bell Labs Technical Journal中的一篇

1928
Fry, T. C. (Thornton Carle Fry)出版一本書"Probability and Its Engineering Uses"

1930s早期
Felix Pollaczek(德國University of Berlin博士畢業)研究Possion input, arbitrary output, single- and multiple-channel問題

1950s加速發展
俄國:
Kolmogorov(就是數學家Andrey Nikolaevich Kolmogorov(Russian: Андрей Николаевич Колмогоров) (April 25, 1903 – October 20, 1987))

Khintchine(數學家Aleksandr Yakovlevich KhinchinAleksandr Yakovlevich Khinchin (Russian: Алекса́ндр Я́ковлевич Хи́нчин, French: Alexandre Khintchine; July 19, 1894 – November 18, 1959))

法國:Crommelin, C. D. 1932
瑞典:Palm, C. 1938
(上面這兩位找不到資料,但是很多文獻都有。傳說人物嗎...)

1980s
出現很多文獻,但都沒有什麼實用價值。一直到二次世界大戰結束才受到關注成為顯學。

Useful Link:http://web2.uwindsor.ca/math/hlynka/qhist.html

Continuous-Time Markov Chain (CTMC)

Continuous-Time Markov Chain簡稱CTMC,這種類型的Markov Process就比較難懂一些,其實也還好啦,只是用微積分來計算,觀念和DTMC是差不多的。

2009年1月30日 星期五

Discrete-Time Markov Chain (DTMC)

Markov Chain=馬可夫鏈

我們先討論Discrete-Time Markov Chain簡稱DTMC,或者習慣上直接稱為Markov chain,這類型的Markov Process可說是"基本款"(入門級),算是比較容易懂的一種,因為數學上比較簡單(加加減減的運算,還用不到微積分,但都用∑)。

DTMC的討論當中,主要會有下列幾個觀念:
  • single-step transition probabilities(transition probabilities)轉移機率、轉態機率、變遷機率
    我們了解一個隨機程序是由一連串的隨機變數所組成,在每個時間點的隨機變數稱為狀態(state),而我們只考慮這個狀態轉移到下一個狀態的機率(因此這是一種conditional probabilities),這樣的機率則稱為single-step transition probabilities
  • homogeneous齊次的、均勻的
    這個字在應該很熟悉,偏微分方程有看過...,這個字中文實在很難懂,只能會意,無法言傳,意思是說:轉移機率和選擇觀察的時間點無關,也就是說不隨時間改變,當stochastic process符合這樣的特性則稱為homogeneous(也有稱time-homogeneous)。
  • transition matrix(chain matrix)
    將每個狀態的transition probabilities依照矩陣方式排列,則構成transition matrix。比方說一個Markov chain有兩個狀態(假設A和B),則可以構成2×2的矩陣,共四個轉移機率:A到A、A到B、B到A、B到B。以此類推。
    這樣的矩陣會是一個stochastic matrix,也就是說每一列的機率之和會是1。
有了上面的概念之後,現在我們討論多個狀態之間的問題,也就是n個step transition的情況,剛剛討論的是single-step情形,當m-step的情形時,也就會有n-step transition probabilities。想當然耳,由transition probabilities構成的transition matrix也會有n-step transition matrix

在single-step和n-step之間有沒有關係呢?當然有。
那就是:

Chapman-Kolmogorov (CK) equation

簡稱C-K方程式,中文是"察普曼-科莫高洛夫方程式"(翻譯自偉大的國立編譯館)

Ergodicity

"Ergodicity"這個字,竟然沒有中文(查yahoo字典)。Ergodicity應該是Ergodic的名詞,而Ergodic意思是(參考Wiktionary):
  1. (mathematics, physics) Of or related to certain systems that, given enough time, will eventually return to previously experienced state.
  2. (statistics, engineering) Of or relating to a process in which every sequence or sample of sufficient size is equally representative of the whole.
但以做學問的角度來看,一定要搞清楚(老師教的),Ergodicity的中文意思是(參考國立編譯館):各態歷經性;遍歷性。(但是這中文還是搞不懂啊!)

國立編譯館的學術名詞資訊網找來的,如果要翻譯一些名詞,可以上去看看喔!以後寫論文的時候,名詞也比較有依據!(為了應付口試委員嗎...)


在stochastic process當中,(還沒看懂,以後再補充。)

2009年1月29日 星期四

Markov Process馬可夫程序

Markov Process指的是一種隨機程序(隨機過程),換句話說,以物件導向的概念來看:stochastic process為父類別,Markov Process為子類別。

怎樣的stochastic process才稱為Markov process呢?
  • 簡單說:當一個stochastic process在時間(n)的值,只跟前一個時間(n-1)有關,則這個隨機程序稱為Markov process。
  • 專業說法:一個stochastic process具有Markov property(至於什麼是馬可夫特性,其實就是上述第一項的意思)
  • 非數學的說法:給定現在(present)的條件,未來(future)和過去(past)的狀態是獨立的(因為只跟現在有關),這樣的過程是無記憶性的(memoryless)。
依照state space和parameter space(index set)來區分Markov process如下表所示:





















State Space
Type of Parameter (Parameter Space或稱為Index Set)
Discrete
Continuous
Discrete
(Discrete-parameter) Markov chain縮寫成DTMC
Continuous-parameter Markov chain縮寫成CTMC
Continuous
Discrete-parameter Markov process
Continuous-parameter Markov process

可以用數學式表示Markov Process,不過在網頁上不好輸入,請參考相關書籍。

另外,Discrete-parameter Markov chain縮寫成DTMC,意思是Discrete-Time Markov Chain,一般說的Markov chain通常指的就是DTMC。而Continuous-parameter Markov chain縮寫成CTMC,意思是Continuous-Time Markov Chain

2009年1月28日 星期三

一些常用的隨機變數Random Variables

將一些常用的隨機變數列在這裡以供參考,但這邊不列方程式(HTML很難表示),詳細請參考Wikipedia

現在發現,學這些random variable最好是可以了解背後所代表的涵義(就像電影駭客任務中的Do not try to bend the spoon; that's impossible. Instead only try to realize the truth: There is no spoon.)

Discrete random variable(離散型的隨機變數):
  • Bernoulli random variable(這是Binomial random variable中的一個特例,只做一次實驗的隨機變數,也就是n=1)
  • Binomial random variable(做n次實驗,每次出現的機率為p,在n次實驗當中只要有一次出現的情形,不管出現的順序)
  • Geometric random variable(做n次實驗,每次出現的機率為p,直到出現為止的情形,有考慮先後順序)
  • Possion random variable(可以近似Binomial random variable的一個情形,當實驗次數n很大,機率p很小)
Continuous random variable(連續型的隨機變數):
  • Normal distribution
  • Exponential distribution(在Continuous random variable唯一具有memoryless特性)
  • Hyperexponential distribution
  • Erlang-k distribution
  • Hypoexponential distribution
  • Gamma distribution
  • Generalized Erlang distribution
  • Cox distribution (Branching Erlang distribution)
  • Weibull distribution
  • Pareto distribution
  • Lognormal distribution
Discrete random variable比較容易懂,所以一般書籍都放在前面講,但是到了Continuous random variable的時候,往往會卡住(我是這樣的啦!),要注意的地方有:
  • 連續型的隨機變數在某一點的機率是,記住是零啊!在某一點探討連續型的隨機變數沒有意義。
  • 連續型的隨機變數的pdf(probability density function)所得到的值,不代表機率,因為你要對區間做積分才是機率,不像離散型的隨機變數,pmf(probability mass function)就是機率。

2009年1月27日 星期二

Random Variables與Stochastic Processes

隨機變數(Random Variables)
A random variables is a function that reflects the result of a random experiment.

隨機變數:將我們所關注的實驗結果,映射(轉換、對應,或用mapping概念)至一個變數,這個方式的函數就是隨機變數。所以,隨機變數根本不應該稱為"變數",隨機變數是函數的概念。用微積分的function來學習隨機變數會比較容易懂啊!

依照隨機變數的值來分類,可以區分為:
  1. Discrete Random Variable離散型的隨機變數
    probability mass function(pmf)來描述這種隨機變數
  2. Continuous Random Variable連續型的隨機變數
    cumulative distribution function(CDF,或簡稱distribution function)來描述這種隨機變數,另外CDF對變數的微分則成為probability density function(pdf)
注意不要把pmfpdf搞混在一起,兩者個觀念是不一樣的。

當我們考慮的是多個隨機變數(multiple random variables),則會用joint probanility mass function(pmf)或是joint cumulative distribution function(CDF)來描述 。

還有Continuous Random Variable在某一點(sample space)的機率值會是零,因為Continuous Random Variable探討的是一段區間當中所發生的機率,而且這個區間包含無窮多個點,因此而發生的機會是零。

隨機程序(Stochastic Processes)
A stochastic process is defined as a family of random variable {Xt:t ∈ T} where each random variable Xt is indexed by parameter t ∈ T, which is usually called the time parameter if T ⊆ R+=[0,∞). The set of all possible values of Xt (for each t ∈ T) is known as the state space S of the stochastic process.

隨機程序:或稱之為隨機過程。簡單的來說,就是一連串的隨機變數,而這些隨機變數是由另一個參數來挑選(索引indexed),通常此參數index是以時間來選取,所以隨機程序才跟時間有關。

此外,這些隨機變數所構成的集合稱為state space,而這"一連串的隨機變數"之間,其中每個隨機變數又會和其他隨機變數有數學關係,因而會有conditional probability。

依照index的不同(所構成的index set或parameter space),可以分為兩種隨機程序:
  • discrete-parameter stochastic process(或是discrete-time)
    其index set(或稱為parameter space)是可以計數的( countable sequence)
  • continuous-parameter stochastic process(或是continuous-time)
    其index set(或稱為parameter space)是一個區間(interval)或著區間的代數組合(algebraic combination of intervals)
依照上述的分類,我們可以把一個隨機程序依照下表所示區分:






















State Space
Type of Parameter
Discrete
Continuous
Discrete
Discrete-parameter chain
Continuous-parameter chain
Continuous
Discrete-parameter stochastic process
Continuous-parameter stochastic process

注意,如果state space是discrete的話,我們稱這樣的隨機程序為chain(鏈),也就是以後會提到的Markov chain(馬可夫鏈)是其中之一。換句話說,此 state space是由discrete random variable所組成的。

Possion Process and the Exponential Distribution

這篇沒有中文標題,因為...就忠於原味吧。
  • Possion Process是一種隨機程序stochastic process,而其數學式為pn(t)=[(λ t)^n]×[e^λt]/n!
  • Exponential Distribution是隨機變數的機率分佈
在大多數queueing system當中,我們會假設:interarrival times和service times是exponential distribution也就是arrival rate和service rate是Possion distribution。

哇...這在說什麼東西啊!

意思是說:在固定的一段時間當中,事件發生的次數是Possion random variable,並且相鄰事件的時間是exponential random variable,這是由數學推導出來的,兩者指的是事情是同一件事。

2009年1月26日 星期一

Little's Equation

Little's Equation在排隊理論中是個很強大的關係式(書上這樣的...the most powerful relationship),那要好好理解一下,"小小"的定律但是超強。

這個關係式是John D. C. Little在1960年早期所提出的(一位稱為Little的教授)。主要將穩態時的system size和穩態平均的waiting time的推論出數學關係,說明如下:
  • Tq=waiting time in the queue
  • T=total time in the system
  • S=service time
這三個都是隨機變數,而且T=Tq+S

可以算出期望值為Wq=E[Tq]、W=E[T]

則Little's formula為

L=λ×W

還有Lq=λ
×Wq

其中的L是system size,也不能說超過就是system capacity,不然會發生balked的情形。

一些常用的結果some general results

這裡先提出一個結果,有關於G/G/1和G/G/c的queue,先讓我們對於queueing theory有點感覺,好接下來以後的討論。

這邊定義定義一個traffic intensity(交通強度),或者稱為queue utilization(利用率)

traffic intensity ρ=λ/cμ
  • λ=平均的進入queueing system的顧客速率(每個單位時間進入λ個,單位:個/秒),即arrival rate
  • c=總共有幾個server在system中(單位:個)
  • μ=每個server之平均的service rate,是用平均的觀念(單位時間中的服務率,單位:1/秒),即service rate
當ρ的值有三種情形,分別表示不同的狀況(都假設系統不會deny customers)
  • ρ>=1,也就是顧客來的數目超出系統能服務的容量,因此queue會越來越大(假設queue沒有限制)。這種情形沒有穩態解(steady-state results)
  • ρ==1,除非arrival和service都是deterministic,不然也是沒有穩態解存在
  • ρ<=1,有穩態解存在。
用數學式來計算的下面兩個結果

假設
N(t)為時間t在系統中的總顧客數,Nq(t)為queue中的顧客數,Ns(t)為service中的顧客數,
即N(t)=Nq(t)+Ns(t)

用隨機程序和隨機變數表示,pn(t)=P(N(t)=n)以及pn=P(N=n)

並假設總共有c個server在system當中。

因此可以算出:(E為計算隨機變數的期望值)
  • 在system中,平均的顧客數為L=E[N]=∑n*pn,由n=0至∞
  • 在queue中,平均的顧客數為Lq=E[Nq]=∑(n-c)*pn,由n=c+1至∞
這樣寫數學式很難看,因為沒有辦法嵌LaTeX語法,另外就是懶啊...請大家看看意思就好了

系統效能的測量measuring system performance

分析queueing system的目的就是:想要知道的我們想要知道的資訊,廢話...
不然是閒著發慌嗎?為了學術而學術嗎,還是為了畢業,為了美好的人生...。不是這樣的。

一般來說:分析之後想要知道的資訊有下列三種:
  1. customer waiting time顧客的等待時間。可以再細分為兩種:(1)在queue中所花的時間,(2)在system中或等待的時間,也就是queue加上service的時間。
  2. customer accumulation顧客的總數、積累。同樣的,也分為兩種:(1)在queue中等待的顧客數目,(2)在整個system中的顧客數目,包含queue和server中的顧客。
  3. idle-service服務閒置的情形。可以是server中的閒置百分比,或是整個系統中沒有顧客的時間。
做這些分析的結果,最終目的有兩個:
  1. 評估系統的有效性(effectiveness)
  2. 設計最佳化系統(optimal),以達到某些criterion(準則、要求)

Queue的標記法notation

為了描述一個queueing process,我們可以使用一個簡單的方法來表示,這個標記方法是由Kendall(1953,全名David George Kendall(15 January 1918 – 23 October 2007))所提出,目前已經成為廣泛使用在queueing theory的文章當中(好像成為標準了!)

Kendall's notation (or sometimes Kendall notation)
Notation是由一系列的符號和斜線"/"(是slash,不是backslash,反斜線"\"),
像是:

A/B/X/Y/Z

其意義如下:
  • A:interarrival-time distribution
  • B:service-time distribution
  • X:the number of parallel service channels
  • Y:system capacity
  • Z:queue discipline
A和B的符號有:
  • M:Exponential,為什麼不是用E表示呢?因為E被Erlang用掉了,而M表示的是Markovian或是memoryless的特性。
  • D:Deterministic
  • Ek:Erlang type k (k=1,2,...)
  • Hk:Mixture of k expoenetials
  • PH:Phase type
  • G:General,意思是general probability distribution,通用的機率分佈,沒有特定的數學是形式。

X和Y的符號由數字組成:1,2,....,∞(無限大,Unicode是& #x221e;(hex十六進位表示)或是& infin;(named名稱表示),關於unicode的查詢,參考http://www.fileformat.info)

Z的符號有:
  • FCFS:first come, first served
  • LCFS:last come, first served
  • RSS:random selection for service
  • PR:priority
  • GD:general discipline
最後說明一下,通常只有前面三個符號我們會使用而已(即A/B/X),如果省略最後兩個的話,則Y為system capacity=無限大,而queue discipline=FCFS。

另外,上述這些符號事實上是不完整的,有些特殊的情形沒有符號表示,像是bulk, state independent等等,這些情形目前沒有符號,算是還在發展當中...(標準化當中嗎!)

2009年1月25日 星期日

服務層級的數量number of service stage

這裡的stage意思是指一個queueing system中包含的queueing service有幾個(queue和server的組合),依照stage的數量可以分為:
  1. single stage
  2. multi stage
所謂的multistage有點像是電路中的cascade(串接),不曉得有沒有cascode(疊接)架構...發想,應該不會有疊接啦!

還有一點,在multi stage中有可能會有feedback回授的情形,跟電路類似。

照這樣來看,queueing system好像可以用電路學的概念來學習囉...(老師,是不是這樣啊)

服務通道的數量number of service channels

一個queueing system中的service部分,其server的數量可以說是number of service channels。

依照channel的數量可以分為:
  1. singlechannel system,只有一個server
  2. multichannel system,一個以上的server。這部分又可以分為兩種:一種是多個queue多個server,另一種是單一queue多個server。
除了這些性質之外,當多個server的時候,其service的行為也有可能受到其他server影響(那會越來越複雜),不過通常我們都考慮互相獨立(independent of each other)

系統容量system capacity

system capacity簡單來說,就是queue的容量加上server的容量。

容量計算:
system容量= queue容量 + server容量

當顧客到達system capacity時,沒有任何的顧客可以進入queueing system(包含queue和server),因為都被塞滿了,沒有空間。

另外一個名詞是system size(系統尺寸大小,一般用L表示,L=E[N],N的期望值),指的是目前在queue和server中的顧客數,換句話說:maximum system size=system capacity

這裡要注意的是:system capacity和system size是不一樣的東西,文章中也許會搞混!

排隊的樣式、原則queueing discipline

queueing discipline的是說明如何從queue中選取customer來服務,常用的方式有下列幾種:

  1. 先到先服務:first come, first served(FCFS),類似計算機中的queue
  2. 後到先服務:last come, first served(LCFS),類似計算機中的stack
  3. 隨機選取服務:random selection for service (RSS),就是隨機選取,選的方式應該(是應該,因為還沒看到說明,這是我猜的)有不同的機率分布。
  4. 優先權服務:priority,沒有縮寫...。顧客會先被標示優先權,優先權高的先服務,或是其他規則。這種方式不管顧客來的時間,前述三者是有考慮時間的先後。
其中的priority方式有兩個不同的情況:
  1. 第一種稱為preemptive(先買的、先發制人的),意思是,如果現在service的顧客其優先權比較低,那麼新進來且優先權高的顧客將會先service,並且暫停優先權低的service。當優先權高的完成service之後,則優先權低的才會繼續service。有點像計算機領域的中斷概念。
  2. 第二個就是nonpreemptive,這個概念是一定要等到server中的顧客已經完成service,新進的顧客才能夠進入service,簡單的說就是不能打斷前一個顧客,即使是優先權較低顧客也不能打斷。

服務樣式service pattern of servers

service pattern和arrival pattern是有相似之處,要注意一點的是:service區塊中的server每次只能服務一個customer。

service pattern討論的有:
  1. 服務時間(service times)的機率分布情形
  2. 服務的方式是single or batch
  3. service可否同時(simultaneously)由一個server服務
  4. 服務時間為stationary或是nonstationary
另外,service process的狀態也許會隨著queue的長度狀態改變,這樣的情形稱為state-dependent,注意queue的行為中沒有這個特性,而且不應該和stationary搞混喔!

顧客的到達樣式arrival pattern of customers

先介紹arrival pattern of customers(翻成中文真是怪怪的)。

一般來說,arrival的情形有兩種:一種是隨機的(stochastic),另一個是決定的(deterministic)。大概也只有兩種,二分法嘛...

先以隨機的arrivals來說,我們需要知道它兩個東西:
  1. 相鄰兩個顧客的時間(也就是interarrival times)機率分布情形
  2. 顧客是否會同時到達(simultaneously)到達,這邊有兩種類型:batch or bulk arrivals(細節以後再說,我還沒看到啊..."批次"&"大塊")
此外,也要知道顧客到達時的行為,有下列這幾種:
  1. 不管佇列(queue)有多長,顧客都會等待被服務為止。
  2. 如果queue太長,顧客不進入queue。這樣的情形稱為balked(balk=阻礙、阻止)
  3. 如果顧客進入queue之後,等待超過顧客的極限,那會選擇離開。這樣的情形稱為reneged(renege=違約、否認)
  4. 如果queue有多條(parallel waiting line),顧客也許會從一條換到另外一條等待。這樣的情形稱為jockey位置(jockey=欺騙、耍手段、駕駛操作)
最後,考慮上述行為對於時間的變化,說明如下:
  1. 如果arrival pattern不隨時間變化(time-independent),則稱之為stationary
  2. 如果arrival pattern會隨時間變化,則稱之為nonstationary

2009年1月24日 星期六

買了貝多芬的交響樂symphony.序曲Overture

這張專輯是Jos van Immerseel擔任指揮的
收錄貝多芬(Ludwig van Beethoven)的交響樂
當時是韋在兄推薦,聽了之後一直沒買,
直到最近,越聽越喜歡,加上有點閒錢,就來擴大內需一下,

我是在大眾唱片買的,花了1588元,這張總共六片CD,每片都很棒,
去買的時候沒有貨,店員還幫我調貨,今天剛好到就去拿了,來好好聽一下"原音"囉...
聽完之後,人生充滿希望,就算沒有也值得了...極力推薦!

唱片是從國外進口的,澳洲製造。







網站:http://www.zigzag-territoires.com/?lang=en

專輯資訊:
BEETHOVEN - 9 Symphonies & Overtures
http://www.zigzag-territoires.com/article.php3?id_article=1711&lang=en

In 1977, the space probes Voyager 1&2 took Beethoven’s music into space as a landmark of our western civilisation... People spend millions for his scores, letters. But there is no greater sign of respect for a composer than to take his music, his researches seriously. How can we handle that matter today : respect and freedom hand to hand : Respect the written text, the use of instruments, number of musicians, tempi and vienneese pitch of Beethoven’s time; true work of research and erudition. Freedom : “it lies in the right to be an individual od today with one’s (invariably personal) culture and sensibility, to blend the available elements as one sees fit, and to communicate all of this to an audience. It is when respect and freedom engage in fruitful dialogue that Beethoven is most likely to appear in his full gravity, drama, wit and humour” Jos van Immerseel

Armed with their experience of period-instrument performances of a varied repertoire - Classical (Mozart, Haydn), Austro-German Romantic (Brahms, Johann Strauss), Russian (Tchaikovsky, Rimsky-Korsakov, Borodin), and finally Ravel - the musicians of Anima Eterna come back to Beethoven with the perspective and mastery acquired as a symphony orchestra.

This complete work is a “tour de force” of Jos van Immerseel musically and intellectually trough a true “manifeste” on his approach and his passion for Beethoven.

Concerts Beethoven

6e Symphonie le 17 avril 2008 - Stuttgart LiederHalle - Allemagne

Intégrale des symphonies - 18 au 24 octobre 2008 - Concertgebouw Bruges - Belgique

9e symphonie 27 octobre 2008 - Salle Pleyel - France

Tournées 2008 : Berlioz - Liszt to prepare next record : la symphonie fantastique, releasing 2009 Belgique, France et Allemagne

10 mai 2008 : Bruges (BE) / Liszt - Grieg - Berlioz 11 mai 2008 : Düsseldorf (DE) / Liszt - Grieg - Berlioz 12 mai 2008 : Regensburg (DE) / Berlioz - Liszt 16 mai 2008 : Le Mans- Epau (FR) / Berlio - Liszt 17 mai 2008 : Cité de la Musique de Paris (FR) / Liszt - Grieg - Berlioz 18 mai 2008 : Valenciennes (FR) / Liszt - Berlioz 18 mai 19 mai 2008 : Bruxelles (BE) / Liszt - Grieg - Berlioz 23 mai 2008 : Hasselt (BE) / Liszt - Grieg - Berlioz 24 mai 2008 : Metz (FR) / Liszt - Berlioz - Grieg 21 juin 2008 : Dresden (DE) / Berlioz - Liszt - Berg

為什麼貼在這裡呢?因為排隊理論實在太難懂了(以我目前的能力),加上機率的數學,以前沒有學好,難上加難。苦悶之際,聽聽貝多芬的交響曲,可以紓解一下!不然遲早會瘋掉。

排隊程序的特性Characteristics of Queueing Processes

排隊理論所要探討的就是排隊系統(queueing system)的行為,而一個queueing system由前端的queue和後端的service所組成,顧客(customer)進入前端的queue等待,然後由service的server服務,完成之後離開queueing system

在大多數情形之下,我們可以用六個特徵可以描述一個queueing system,這六個如下:
  1. 顧客的到達樣式
    arrival pattern of customers
  2. 侍者的服務樣式
    service pattern of servers
  3. 排隊的樣式、原則
    queueing discipline
  4. 系統容量
    system capacity
  5. 服務通道的數量
    number of service channels
  6. 服務層級的數量
    number of service stage
書上是說用這六個就足夠說明一個排隊系統,是這樣嗎?
因為才剛開始學,所以還不知道。會不會有第七個...問上帝吧
等等...先問我老師好了

Queueing Theory參考書籍

目前學習Queueing Theory的書籍,我手上有兩本,
都是老師(ycwang)推薦給我看的,如果有需要研究排隊理論(queueing theory)的話,可以先從這兩本下手喔!

這兩本都是Wiley出版的,太可怕了....什麼時候台灣會出一本啊!(老師,你要不要出一本啊...)

一本是:


買的時候是台幣1360元


Fundamentals of Queueing Theory, 4th Edition (都第四版了,應該是不錯...買啦) presents the analytic modeling of queues using up-to-date examples and detailed coverage of the fundamentals of analytic modeling. A fresh emphasis on telecommunications enlivens the text, and spreadsheet programs for Excel and Quattro on the related Web site will help you understand the sensitivity of waiting-line systems to parameter and environmental changes. New material and discussions on call centers, numerical techniques (such as TAM, TRM, and LC), and simulation have been added. Software programs for additional systems, mathematical details with numerical results, and intuitive arguments are also included.



另一本是:



這本是新台幣1680元

Critically acclaimed text for computer performance analysis--now in its second edition


The Second Edition (目前是第二版,有修改一些內容,也不錯...超厚的)of this now-classic text provides a current and thorough treatment of queueing systems, queueing networks, continuous and discrete-time Markov chains, and simulation. Thoroughly updated with new content, as well as new problems and worked examples, the text offers readers both the theory and practical guidance needed to conduct performance and reliability evaluations of computer, communication, and manufacturing systems.

Starting with basic probability theory, the text sets the foundation for the more complicated topics of queueing networks and Markov chains, using applications and examples to illustrate key points. Designed to engage the reader and build practical performance analysis skills, the text features a wealth of problems that mirror actual industry challenges.

New features of the Second Edition include:
* Chapter examining simulation methods and applications
* Performance analysis applications for wireless, Internet, J2EE, and Kanban systems
* Latest material on non-Markovian and fluid stochastic Petri nets, as well as solution techniques for Markov regenerative processes
* Updated discussions of new and popular performance analysis tools, including ns-2 and OPNET
* New and current real-world examples, including DiffServ routers in the Internet and cellular mobile networks

With the rapidly growing complexity of computer and communication systems, the need for this text, which expertly mixes theory and practice, is tremendous. Graduate and advanced undergraduate students in computer science will find the extensive use of examples and problems to be vital in mastering both the basics and the fine points of the field, while industry professionals will find the text essential for developing systems that comply with industry standards and regulations.

Additionally, a solution manual and an FTP site with links to author-provided data for the book are available for deeper study.

都是在巨擘(ㄅㄛˋ)書局買的
可以去參考看看
地址:台北市中正區懷寧街36號二樓‧服務電話:02-2331-0940