查看“杰克逊排队网络”的源代码

在[[排队论]]中（[[运筹学]]的一支），'''杰克逊排队网络'''（{{Lang-en|Jackson network}}，亦作{{Lang|en|Jacksonian network}}<ref>{{Cite journal|title=Sojourn Times and the Overtaking Condition in Jacksonian Networks|first1=J.|last2=Varaiya|first2=P.|journal=Advances in Applied Probability|issue=4|doi=10.2307/1426753|year=1980|volume=12|pages=1000–1018|jstor=1426753|pmc=|pmid=|last1=Walrand|authorlink1=Jean Walrand}}</ref>）是一类排队网络模型，其均衡分布计算形式简单且网络具有积形式解。该模型已被推广，其定理的思想也被运用于寻找其他网络中类似的积形式解。<ref>{{cite journal|title=Networks of Queues|last=Kelly|first=F. P.|authorlink=F. P. Kelly|date=June 1976|journal=Advances in Applied Probability|issue=2|doi=10.2307/1425912|volume=8|pages=416–432|jstor=1425912}}</ref>[[互联网]]发展中的一些思想亦源于该排队网络。<ref>{{cite journal|title=Comments on "Jobshop-Like Queueing Systems": The Background|first=James R.|last=Jackson|journal=[[Management Science: A Journal of the Institute for Operations Research and the Management Sciences|Management Science]]|volume=50|date=December 2004|pages=1796–1802|jstor=30046150|issue=12|doi=10.1287/mnsc.1040.0268}}</ref>这一网络模型首先由{{Tsl|en|James R. Jackson|4=詹姆斯·R·杰克逊}}提出。<ref name="jackson">{{cite journal|title=Jobshop-like Queueing Systems|last=Jackson|first=James R.|date=Oct 1963|journal=[[Management Science: A Journal of the Institute for Operations Research and the Management Sciences|Management Science]]|issue=1|doi=10.1287/mnsc.1040.0268|volume=10|pages=131–142|jstor=2627213}} A version from January 1963 is available at http://www.dtic.mil/dtic/tr/fulltext/u2/296776.pdf</ref><ref>{{Cite journal|title=Networks of Waiting Lines|first1=J. R.|authorlink=James R. Jackson|journal=Operations Research|issue=4|doi=10.1287/opre.5.4.518|year=1957|volume=5|pages=518–521|jstor=167249|pmc=|pmid=|last1=Jackson}}</ref>2004年，杰克逊的文章重载于《{{Tsl|en|Management Science (journal)|管理科学 (期刊)|管理科学}}》，该刊将其誉为“[[管理科学]]头50年中最具影响力的十篇论文”之一。<ref>{{cite journal|title=Jobshop-Like Queueing Systems|first=James R.|last=Jackson|journal=[[Management Science: A Journal of the Institute for Operations Research and the Management Sciences|Management Science]]|volume=50|date=December 2004|pages=1796–1802|jstor=30046149|issue=12|doi=10.1287/mnsc.1040.0268}}</ref>

杰克逊受到了{{Translink|en|Burke's theorem|柏克定理|柏克}}和赖克（{{Lang|en|Reich}}）工作的启发。<ref>{{cite journal|title=Waiting Times When Queues are in Tandem|journal=[[Annals of Mathematical Statistics]]|volume=28|date=September 1957|first=Edgar|last=Reich|doi=10.1214/aoms/1177706889|jstor=2237237|issue=3|pages=768}}</ref>但吉恩·华尔兰德（{{Lang|en|Jean Walrand}}）指出“积形式解的结果……从柏克定理推过去不是很直接，并没有杰克逊本人在他那篇奠基性文章中所认为的那么直接”。<ref>{{cite journal|title=A Probabilistic Look at Networks of Quasi-Reversible Queues|journal=[[IEEE Transactions on Information Theory]]|volume=29|date=November 1983|first=Jean|last=Walrand|doi=10.1109/TIT.1983.1056762|issue=6|pages=825}}</ref>

在串联排队（有限数量的队列，顾客按先后顺序去每个队列等候）和环形排队网络（串联成环的若干队列，顾客按先后顺序去每个队列等候）中，{{Lang|en|R.R.P. Jackson}}更早就发现了一个积形式解。<ref>{{cite journal|title=Book review: Queueing networks and product forms: a systems approach|first=R. R. P.|last=Jackson|doi=10.1093/imaman/6.4.382|year=1995|volume=6|pages=382–384|journal=IMA Journal of Management Mathematics|issue=4}}</ref>

杰克逊网络包括一定数量的节点，每个节点表示一个队列，队列的服务率既可以是状态无关的（不同的节点有不同的服务率），也可以是状态相关的（服务率的变化与队长相关）。任务（{{Lang|en|jobs}}）按照一个固定的路由矩阵（{{Lang|en|routing matrix}}）在节点间转移。每个节点处的任务都属于单一的“类”（{{Lang|en|class}}），任务都服从相同都服务时间分布和路由机制。因此，并没有引入任务服务的优先级：每个节点处的所有工作都以先到先得（{{Lang|en|FIFS, First In First Severed}}）方式进行。

有限任务、闭合网络的杰克逊网络也有积形式解，该结论由Gordon–Newell定理阐明。<ref>{{Cite journal|title=Closed Queuing Systems with Exponential Servers|first1=W. J.|last2=Newell|first2=G. F.|authorlink2=Gordon F. Newell|journal=[[Operations Research (journal)|Operations Research]]|issue=2|doi=10.1287/opre.15.2.254|year=1967|volume=15|pages=254|jstor=168557|pmc=|pmid=|last1=Gordon}}</ref>

== 杰克逊排队网络的必要条件 ==
<math>m</math>个相连队列组成的网络被称作杰克逊网络，若它满足下述条件：<ref>{{Cite journal|title=The Non-Ergodic Jackson Network|last=Goodman|first=Jonathan B.|last2=Massey|first2=William A.|date=December 1984|journal=Journal of Applied Probability|issue=4|doi=10.2307/3213702|volume=21|pages=860-869}}</ref><ref>{{Cite journal|title=Sojourn Times and the Overtaking Condition in Jacksonian Networks|last=Walrand|first=J.|last2=Varaiya|first2=P.|date=December 1980|journal=Advances in Applied Probability|issue=4|doi=10.2307/1426753|volume=12|pages=1000-1018}}</ref> 

# 若网络是开放的，任意往节点<math>i</math>的外部到达都是一个[[泊松过程]]，
# 服务时间呈指数分布，排队规则为先到先得（{{lang|en|First come first served}}），
# 队列<math>i</math>处的顾客服务结束后，以概率<math>P_{ij}</math>转移到新的队列<math>j</math>或以概率<math>1-\sum_{j=1}^{m}P_{ij}</math>离开队列；对于开放网络来说，离开概率对所有队列的某个子集是非零的，
# 所有队列的利用率都小于1。

== 定理 ==

<math>m</math>为[[M/M/1|M/M/1模型]]的开放杰克逊网络，其中利用率（{{lang|en|utilization}}）<math>\rho_i</math>对每个队列都小于1，平衡状态概率分布存在，且对状态<math>\scriptstyle{(k_1,k_2,\ldots,k_m)}</math>，平衡状态（{{Lang|en|equilibrium state}}）概率分布由每个队列的平衡分布之积给出：

:<math>\pi (k_1,k_2,\ldots,k_m) = \prod_{i=1}^{m} \pi_i(k_i) = \prod_{i=1}^{m} [\rho_i^{k_i} (1-\rho_i)].</math>

结果<math>\pi (k_1,k_2,\ldots,k_m) = \prod_{i=1}^{m} \pi_i(k_i)</math>对[[M/M/c]]服务站（{{Lang|en|stations}}）也成立，其中第<math>i</math>个节点的服务台（{{Lang|en|servers}}）数为<math>c_i</math>，利用率满足<math>\rho_i < c_i</math>。

== 定义 ==
在一个开放网络中，顾客自系统外部以泊松流方式到达，到达率为<math>\alpha>0</math>。每个往节点''j''的到达是相互独立的，有概率 <math>p_{0j}\ge0</math>且满足<math>\sum_{j=1}^J p_{0j}=1</math>。当节点<math>i</math>处的服务完成时，顾客会以概率<math>p_{ij}</math>进入另一节点或者以<math>p_{i0}=1-\sum_{j=1}^J p_{ij}</math>的概率离开网络。

因此，节点<math>i</math>的总到达率<math>\lambda_i</math>是外部到达和内部转移的总和：<math /><math /><math display="block">\lambda_i =\alpha p_{0i} + \sum_{j=1}^J \lambda_j p_{ji}, i=1,\ldots,J.\qquad (1)</math>（因为每个节点的利用率均小于1，且我们观察的是均衡分布，即长时间运行的平均行为，任务从<math>j</math>转移到<math>i</math>速率的界不超过<math>j</math>到达率的一部分，我们由此忽略上式中的服务率<math>\mu_j</math>。）<math />

定义 <math>a=(\alpha p_{0i})_{i=1}^J</math>，我们就可以解出<math>\lambda=(I-P^T)^{-1}a</math>。

所有任务在后续泊松过程中会离开其节点，节点<math>i</math>处有<math> x_i </math>个任务，定义其服务率为<math>\mu_i(x_i)</math>。

令<math>X_i(t)</math>表示节点<math>i</math>在时间<math>t</math>的任务数，<math>\mathbf{X}=(X_i)_{i=1}^J</math>。<math>\mathbf{X}</math>的[[均衡分布]]，<math>\pi(\mathbf{x})=P(\mathbf{X}=\mathbf{x})</math>由如下系统平衡方程给出：

:<math>
\begin{align}
& \pi(\mathbf{x}) \sum_{i=1}^J [\alpha p_{0i} +\mu_i (x_i) (1-p_{ii})] \\ = {} & \sum_{i=1}^J[\pi(\mathbf{x}-\mathbf{e}_i) \alpha p_{0i}+\pi(\mathbf{x}+\mathbf{e}_i)\mu_i(x_i+1)p_{i0}]+\sum_{i=1}^J\sum_{j\ne i}\pi(\mathbf{x}+\mathbf{e}_i-\mathbf{e}_j)\mu_i(x_i+1)p_{ij}.\qquad (2)
\end{align}
</math>

其中<math>\mathbf{e}_i</math>表示第<math>i</math>个[[单位向量]].。

=== 定理 ===
设独立随机向量<math> (Y_1,\ldots,Y_J)</math>，每个<math> Y_i</math>都有[[概率质量函数]]：

:<math> P(Y_i=n)=p(Y_i=0)\cdot \frac{\lambda_i^n}{M_i(n)}, \quad (3)</math>

其中<math> M_i(n)=\prod_{j=1}^n \mu_i(j) </math>。当<math> \sum_{n=1}^\infty \frac{\lambda_i^n}{M_i(n)} < \infty </math>即<math>P(Y_i=0)=\left(1+\sum_{n=1}^\infty \frac{\lambda_i^n}{M_i(n)}\right)^{-1}</math>是良定义的，开放杰克逊网络的平衡分布有如下的积形式：

:<math> \pi(\mathbf{x})=\prod _{i=1}^J P(Y_i=x_i).</math>

对所有的<math>\mathbf{x}\in \mathcal{Z}_{+}^J </math>。

=== 例 ===
[[File:Open_jackson_network_(final).png|缩略图|三节点的开放杰克逊网络]]
设图中有一三节点的杰克逊网络，系数分别是：

:<math>\alpha=5, \quad
p_{01}=p_{02}=0.5, \quad p_{03}=0,\quad </math>

:<math>
P=\begin{bmatrix}
0 & 0.5 & 0.5\\
0 & 0 & 0 \\
0 & 0 & 0\end{bmatrix}, 
\quad 
\mu=\begin{bmatrix}
\mu_1(x_1)\\
\mu_2(x_2)\\
\mu_3(x_3)\end{bmatrix}
=\begin{bmatrix}
15\\
12\\
10\end{bmatrix} 
\text{ for all }x_i>0</math>

通过定理，可以计算：

: <math>\lambda=(I-P^T)^{-1}a=\begin{bmatrix}
1 & 0 & 0\\
-0.5 & 1 & 0 \\
-0.5 & 0 & 1\end{bmatrix}^{-1}\begin{bmatrix}
0.5\times5\\
0.5\times5\\
0
\end{bmatrix}=\begin{bmatrix}
1&0&0\\
0.5&1&0\\
0.5&0&1\end{bmatrix}\begin{bmatrix}
2.5\\
2.5\\
0\end{bmatrix}=\begin{bmatrix}
2.5\\
3.75\\
1.25\end{bmatrix}
</math>

根据<math>\mathbf{Y}</math>的定义，有：

:<math> P(Y_1=0)=\left(\sum_{n=0}^\infty \left(\frac{2.5}{15}\right)^n\right)^{-1}=\frac{5}{6} </math>
:<math> P(Y_2=0)=\left(\sum_{n=0}^\infty \left(\frac{3.75}{12}\right)^n\right)^{-1}=\frac{11}{16} </math>
:<math> P(Y_3=0)=\left(\sum_{n=0}^\infty \left(\frac{1.25}{10}\right)^n\right)^{-1}=\frac{7}{8} </math>

因此，每个节点处有一个服务的概率是：

:<math> \pi(1,1,1)=\frac{5}{6}\cdot\frac{2.5}{15}\cdot\frac{11}{16}\cdot\frac{3.75}{12}\cdot\frac{7}{8}\cdot\frac{1.25}{10}\approx 0.00326</math>

由于这里的服务率是状态无关的，<math> Y_i</math>各项服从简单的[[幾何分佈|几何分布]]。

== 杰克逊网络的推广 ==
'''推广的杰克逊网络'''允许{{tsl|en|Renewal theory|更新到达过程}}不一定是一个泊松过程，也允许服务时间是独立且同种的非指数分布。一般地，网络不一定要有{{tsl|en|Product-form solution|积形式稳定解}}，因此需要找近似解
<ref>{{Cite book|title=Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization|last=Chen|first=Hong|last2=Yao|first2=David D.|publisher=Springer|year=2001|isbn=0-387-95166-0}}</ref>

=== 布朗近似 ===
在一些平和的条件下，开放的推广杰克逊网络的队长过程<math />Q(t)<math />可以用{{tsl|en|reflected Brownian motion|反射布朗运动}}近似，定义为<math>RBM_{Q(0)}(\theta,\Gamma;R)</math>，其中<math>\theta</math>是过程的漂移（{{lang|en|drift}}），<math>\Gamma</math>是协方差矩阵，<math>R</math>是反射矩阵。这一二阶近似是从均质流体（{{lang|en|homogeneous fluid network}}）的推广杰克逊网络和反射布朗运动间的关系得到的。

反射布朗过程的参数如下所述：

:<math> \theta= \alpha -(I-P^T)\mu </math>
:<math> \Gamma=(\Gamma_{kl}) </math>有<math> \Gamma_{kl}=\sum_{j=1}^J (\lambda_j \wedge \mu_j)[p_{jk}(\delta_{kl}-p_{jl})+c_j^2(p_{jk}-\delta_{jk})(p_{jl}-\delta_{jl})]+\alpha_k c_{0,k}^2 \delta_{kl} </math>
:<math> R=I-P^T </math>

其中符号的定义：
{| class="wikitable" style="margin-bottom: 10px;"
|+近似公式中符号的定义
! 符号 
!  含义
|-
| <math> \alpha=(\alpha_j)_{j=1}^J </math>
|J维向量，每个节点的到达率
|-
| <math> \mu=(\mu)_{j=1}^J </math> 
|J维向量，每个节点的服务率
|-
| <math> P </math> 
|转移矩阵
|-
| <math> \lambda_j </math>
|第j个节点的有效到达
|-
| <math> c_j </math> 
|第j个节点服务时间的变异系数
|-
| <math> c_{0,j} </math>
|第j个节点服务台间转移到达时间的变异系数
|-
| <math> \delta_{ij} </math> 
| 反映节点间关系的系数{{hidden begin|toggle=left}}
它们是这样定义的：令<math>A(t)</math>为系统的到达过程，则在分布中有<math>A(t)-\alpha t {}\approx \hat{A}(t)</math>，其中<math>\hat{A}(t)</math>是一个无漂移（{{lang|en|driftless}}）的布朗过程，其协方差矩阵为<math>\Gamma^0=(\Gamma^0_{ij})</math>，满足对所有的<math>i,j\in \{1,\dots,J\}</math>都有<math>\Gamma^0_{ij}=\alpha_i c_{0,i}^2 \delta_{ij}</math>。
{{hidden end}}
|}

== 参见 ==

* Gordon–Newell网络
* BCMP网络
* G-网络
* [[利特爾法則|Little法则]]

== 参考文献 ==
{{Reflist}}
[[Category:等候理論]]