[發明專利]一種具兩異質服務類型排隊線的穩態機率矩陣計算方法

有效

• 申請號: 201910207266.6
• 申請日: 2019-03-19
• 公開（公告）號: CN109902262B
• 公開（公告）日: 2022-06-21
• 發明（設計）人: 王嘉宏;吳曉晶
• 申請（專利權）人: 福建工程學院
• 主分類號: G06F17/16
• 分類號: G06F17/16;G07C11/00
• 代理公司: 福州元創專利商標代理有限公司 35100
• 代理人: 蔡學俊

1.一種具兩異質服務類型排隊線的穩態機率矩陣計算方法，其特征在于，首先，假設準備進入具兩異質服務類型系統的顧客總數目為一有限整數值N，在給定服務類型閾值δ后，顧客被指派到第一種服務類型排隊線的比例為p₁(δ)，配置的第一種類型服務的服務器數量為c₁，平均服務率為μ₁；而顧客被指派到第二種服務類型排隊線的比例為1-p₁(δ)，配置的第二種類型服務的服務器數量為c₂，平均服務率為μ₂；而后，定義具兩異質服務類型排隊線的排隊系統穩態機率向量π，構造狀態轉移機率矩陣Q，穩態機率向量π，進而計算排隊系統表現指標，即平均隊列長度L(δ,c₁,c₂)和平均等待時間W(δ,c₁,c₂)；該方法具體實現如下：

定義具兩異質服務類型排隊線的排隊系統狀態空間{(q₂(t),q₁(t)),t＞0}，表示顧客在第二種服務類型排隊線和第一種服務類型排隊線的所有可能排隊狀態組合，其中，q₁(t)表示在第一種服務類型排隊線的顧客數目，而q₂(t)表示在第二種服務類型排隊線的顧客數目；考慮隨機過程{(q₂(t),q₁(t)),t＞0}為連續時間的馬可夫鏈過程，并且顧客總數N為有限整數值，故而第一種服務類型排隊線的顧客狀態數q₁(t)和第二種服務類型排隊線的顧客狀態數q₂(t)皆為有取值范圍上限的整數值，并且滿足以下不等式：

q₁(t)+q₂(t)≤{N+c₁+c₂}

因此，二維馬可夫鏈系統的狀態空間集合Ω表示為

Ω＝{(q₂(t),q₁(t))|q₂(t)＝0,1,...,N+c₂；q₁(t)＝0,1,...,N+c₁}

同時，用集合概念建構二維馬可夫鏈系統的狀態空間集合Ω如下

其中，子集合

表示當第二種服務類型排隊線的顧客狀態數為q₂(t)時，此二維馬可夫鏈系統所有狀態的子集合，用表示第二種服務類型排隊線的顧客狀態數為q₂(t)且第一種服務類型排隊線的顧客狀態數為q₁(t)時的系統狀態子集合，即隨機過程{(q₂(t),q₁(t)),t＞0}為階段相依的擬生死過程；

定義具兩異質服務類型排隊線的排隊系統穩態機率向量

其中，向量π_i＝(π_i⁽²⁾,π_i⁽¹⁾),i＝0,1,…,N+c₂，穩態機率π_i⁽²⁾表示恰好有i個顧客在第二種服務類型排隊線的機率向量；π_i⁽¹⁾表示第一種服務類型排隊線在給定i個顧客在第二種服務類型排隊線時的所有可能狀態數的機率向量；

建構擬生死過程的狀態轉移機率矩陣Q

Q表示系統狀態從轉移至下一時間點的系統狀態在Q里面有(N+c₂+1)²個子矩陣A_i,j，A_i,j表示狀態q₂＝i轉移至q₂＝j的狀態轉移矩陣，其矩陣大小為(K+1+c₁-max{0,i-c₂})×(K+1+c₁-max{0,j-c₂})，其中，i,j∈{0,1,…,K+c₂}；

構造狀態轉移機率矩陣Q中子矩陣A_i,j：

首先，定義：

ψ_i＝K+c₁-max{0,i-c₂}，θ_i＝K+c₁-max{0,j-c₂}，λ₁＝p₁(δ)·λ，λ₂＝(1-p₁(δ))·λ，T₁＝c₁·μ₁和T₂＝c₂·μ₂；

①當下標賦值i＝j＝0,1,...,K+c₂時，狀態轉移機率矩陣Q中對角線子矩陣A_i,i，如下所示：

②當下標賦值i＝j+1時，對于j∈{0,1,…,K+c₂-1}，狀態轉移機率矩陣Q中的子矩陣A_i,j，如下所示：

③當下標賦值i＝j-1時，對于j∈{0,1,…,K+c₂}，狀態轉移機率矩陣Q中的子矩陣A_i,j，如下所示：

④當下標賦值2≤i-j≤K+c₂時，對于i,j∈{0,1,…,K+c₂}，狀態轉移機率矩陣Q中的子矩陣A_i,j，如下所示：

⑤當下標賦值2≤i-j≤K+c₂時，對于i,j∈{0,1,…,K+c₂}，狀態轉移機率矩陣Q中的子矩陣A_i,j，如下所示：

在計算得到狀態轉移機率矩陣Q后，滿足穩定性條件下求得穩態機率向量其中，當0≤i≤c₂時，穩態機率向量π_i是維度N+c₂的向量；而當c₂＜i≤N+c₂時，穩態機率向量π_i的維度N+2c₂-i向量；在滿足穩定性條件下，透過求解以下聯立方程組計算得到穩態機率向量π：

其中，向量為所有元素皆取值為1的向量；

由此使用穩態機率向量π計算在穩定狀態下的平均等待時間，即期望通關時間W(δ,c₁,c₂)；顧客在第二種服務類型排隊線的長期平均數目L₂(δ,c₁,c₂)，由下式計算得到：

表示顧客在第二種服務類型排隊線的系統狀態數乘以對應的穩態機率再對所有可能的系統狀態進行加總運算；

而顧客在第一種服務類型排隊線的長期平均數目L₁(δ,c₁,c₂)，由計算在第一種服務類型排隊線的系統狀態數乘以對應的穩態機率再對所有可能的系統狀態進行加總運算得到，如下式所示：

其中，表示第j個元素為1，其它元素皆為0的單位向量，其向量維度與對應相乘的穩態機率向量π_i相同；

具兩異質服務類型排隊線的排隊系統平均隊列長度L(δ,c₁,c₂)計算如下：

其中，p₁(δ)＝p_r(0≤a≤δ)為所有到達系統的顧客會被指派至第一種服務類型排隊線的比例，1-p₁(δ)＝p_r(δ≤a≤1)為所有到達系統的顧客會被指派至第二種服務類型排隊線的比例，是服務類型閾值δ的函數；

運用排隊論中的Little's Law，推導出顧客在第二種服務類型排隊線的平均等待時間：

計算顧客在第一種服務類型排隊線的平均等待時間：

由此得排隊模型的平均等待時間W(δ,c₁,c₂)由下式計算得到：