第九章 排隊模型
介紹排隊模型
排隊理論(Queuing theory)是關於等候線或排隊(queues)的研究。
排隊分析的目的是設計一些系統使組織能根據某些標準來最佳化地執行。
排隊過程的要素
排隊系統的要素
1.到達(Arrivals)：顧客依某種到達模式到達某個系統
2.在等候線中等待(waiting in a Queue)：到達的顧客可
能必須在一或多個隊伍中等待接受服務
3.服務(Service)：顧客接受服務並離開系統
圖
三個服務人員(server)的排隊系統
排隊過程的要素
到達過程(The Arrival Process)
在某些情況下，顧客會依據一個設定好的時程到達，可以利用決定性到達過程(deterministic arrival process)來為此系統建立模型。
排隊過程的要素
卜瓦松分配(The Poisson Distribution)
卜瓦松到達過程的狀況
1.有順序的─在任何時點，最多一個顧客到達服務設施
2.不變的─在某一特定時間框架內，顧客在某一時間幅度
內到達機率與所有相同的時間區段相等
3.獨立的─顧客到達彼此間為獨立
排隊過程的要素
卜瓦松到達分配
在時間t內有k個到達的機率為：
P(X＝k)＝(λt)ke-λt/k!
λ＝單位時間內平均到達率
t＝時間區段的長度
e＝（自然對數基底）
k!＝k(k－1)(k－2)(k－3)...(3)(2)(1)
在此式中，λ及t必須以相同時間單位表示，如果λ以每小時顧客數表示，則t必須以小時表示。
排隊過程的要素
等候線(The Waiting Line)
等候線型式(Line Configuration)
一條長等候線或許多較短的等候線
圖 常用的排隊系統等候線型式
排隊過程的要素
變換隊伍(Jockeying)
當顧客發現另一條隊伍移動較快而轉換隊伍時，會發生變換隊伍(Jockeying)的情形。
如果顧客懂得變換隊伍，則任一種等候線型式將導致相同的績效評量。
排隊過程的要素
中止(Balking)
顧客認知到等候線過長可能會離開(balk) 且決定到其他地方處理業務。
如果過多顧客離開，公司的長期獲利率將受到影響。
排隊過程的要素
優先順序法則(Priority Rules)
最常被用來作為選擇下一顧客的優先順序法則(Priority Rule)為先進先出(FCFS)，這是指在等候線的第一人將會是下一個接受服務者。
排隊過程的要素
前後排隊(Tandem Queues)
顧客通常僅需要由一名服務人員來服務，但在某些系統，必須接受多個服務人員服務，這種系統叫前後排隊等候系統(Tandem Queues)。
排隊過程的要素
同質性(Homogeneity)
儘管許多等候模型假設到達顧客為同質性(homogeneity)群體，而且每人需要同一種服務，但某些等候模型會依顧客不同的到達模式或服務需求來分類 。
排隊過程的要素
服務過程(The Service Process)
指數機率分配常被用於把顧客服務時間模型化。
指數服務時間分配
f(t)＝e－t
＝單位時間內平均接受服務之顧客人數
排隊過程的要素
對指數分配而言，顧客平均服務時間及顧客服務時間標準差皆為1/。
在時間t內完成服務的機率
P(X≦t)＝1－e－t
排隊過程的要素
指數分配的無記憶性
指數分配是無記憶性分配，也就是說觀察已執行過的服務時間，不會讓現在的機率分配獲得更多的資訊
排隊過程的要素
卜瓦松分配與指數分配之間的關係
若顧客的到達符合到達率為λ的卜瓦松分配，則到達間隔時間符合平均到達時間為1/λ的指數分配。
卜瓦松與指數分配之間的關係能得到當顧客到達為卜瓦松分配而服務時間為指數分配的排隊績效衡量。
排隊過程的要素
耳蘭分配
若指數分配不適合將服務時間模型化(由於不符合無記憶性特性)；另一個選擇為耳蘭分配。
排隊系統的績效衡量
短暫和穩定狀態期間
到達穩定狀態的要求
系統(system) 要求(requirement)
單一服務者 λ＜
k個服務者，各個服務率可能不同 λ＜1＋2＋...＋k
k個具相同服務率的服務者 λ＜k
排隊系統的績效衡量
穩定狀態系統的績效衡量
P0＝沒有顧客在系統中的機率
Pn＝有n個顧客在系統中的機率
L＝系統內平均顧客數
Lq＝排隊隊伍中的平均顧客數
W＝一名顧客在系統中平均花費時間
Wq＝一名顧客平均花費在等候的時間
Pw＝所有服務者都在忙碌的機率
ρ＝每個服務者的使用率
排隊系統的績效衡量
里陶公式
里陶公式(Little‘s Formulas)說明系統內平均顧客數L與系統內顧客平均花費時間W之間，及等候服務之平均顧客數Lq與顧客花在等候服務的平均時間Wq之間存在重要的關係。
排隊系統的績效衡量
里陶公式
L＝λW
Lq＝λWq
對於可能有無限母體之穩定狀態模式，若所有服務者以相同的服務率服務，則λ/表示被服務的平均顧客數，所以L＝Lq＋λ/
排隊系統的績效衡量
排隊系統記號法
不同的到達及服務過程及不同服務者數目導致不同的排隊系統之結構配置。
排隊的分類
到達過程/服務過程/服務者個數
M/M/1排隊系統
M/M/1排隊的績效衡量
P0＝1－(λ/)
Pn＝(1－(λ/))(λ/)n
L＝λ/(－λ)
Lq＝λ2/( (－λ))
W＝1/(－λ)
Wq＝λ/( (－λ))
Pw＝λ/
ρ＝λ/
M/M/1排隊系統
系統時間分配
M/M/1─系統時間
系統平均時間＝1/(－λ)
P（系統時間＜t）＝1－e－(－λ)t
M/M/1排隊系統
系統與排隊績效衡量的關係
在系統內的平均等候時間
＝在隊伍中的平均等候時間＋平均服務時間
W＝Wq＋1/
系統內的平均顧客數
＝隊伍中的平均顧客數＋平均正被服務的顧客數
L＝Lq＋λ/
M/M/K排隊系統
M/M/K排隊系統(M/M/K queuing system)假設
1.顧客以卜瓦松過程，平均率為λ到達
2.服務時間符合指數分配
個服務者皆以平均率 (K＞λ)進行服務
M/M/K排隊系統
M/M/K排隊系統的績效衡量
P0＝
Pn＝
P0 for n≦k
Pn＝
P0 for n＞k
M/M/K排隊系統
L＝
P0＋
W＝
P0＋
Lq＝
P0
M/M/K排隊系統
Wq＝
P0
Pw＝
P0
ρ＝
M/G/1排隊系統
普氏─卡氏公式
L＝
λ為平均到達率
1/為平均服務時間
σ為用與服務時間相同單位表示的服務時間標準差
M/G/1排隊系統
M/D/1系統
在M/D/1系統(M/D/1 system)中，顧客以固定的(確定的)速率被服務。
M/G/1排隊系統
M/En/1系統
當顧客的服務是由許多獨立任務所組成時，服務時間常可被模型化為耳蘭分配(Erlangian distribution)，耳蘭隨機變數是由n個獨立指數分佈的隨機變數總合所組成，每個的平均值都等於1/n。
M/M/k/F排隊系統
(有限排隊長度)
M/M/k/F的模型(M/M/k/F model)假設平均率為λ的卜瓦松到達過程，k個服務者，服務時間為平均率為的指數分配，及系統在同一時間內最多能容納F個顧客。
M/M/k/F排隊系統
(有限排隊長度)
只有λ中一部分的顧客能進入系統，這個有效到達率(effective arrival rate)設為λe。
有限排隊的有效到達率
λe＝λ(1－PF)
M/M/1//m排隊系統
(有限顧客母體)
在M/M/1//m系統中，假設有單一服務者，每個顧客的服務率遵循平均值為1/的指數分配，且有m個潛在顧客，若m中已有n個顧客在系統，則下一個顧客的到達間隔時間遵循平均值為1/(m－n)λ的指數分配。
排隊系統的經濟分析
用排隊模型來決定最佳用人水準
-薪資
-電話費用
-商譽成本
-每小時總平均成本
排隊系統的經濟分析
考慮一個不同的排隊系統，並決定最佳服務者數目
-目前狀況分析
-刪減一個產房的分析
-增加一個產房的分析
前後排隊系統
顧客在完成全部服務前必須接受許多服務者服務，這種系統便叫前後排隊系統(tandem queuing systems)。
顧客到達第i個站時符合每小時平均率為λi的卜瓦松過程，在λi＜ki時，離開第i個站的過程也將為平均率為λi的卜瓦松分配。
