杰克逊网络

杰克逊网络（Jackson network）是一类具有乘积形式稳态分布的排队网络。顾客从外部进入，在多个服务节点之间按固定概率转移，最终离开。节点之间明明有流量联系，稳态下各节点人数却能具有独立的几何分布；这一结论依赖明确的到达、服务与路由假设，不能套用于任意“多条队伍”。

考虑两个服务台。外部以每分钟一人进入节点一、每分钟半人进入节点二；二者是独立泊松流。节点一完成服务后以二分之一概率转去节点二，否则离开；节点二完成后以四分之一概率返回节点一，否则离开。单个顾客可能访问同一节点多次。

开放网络的模型

本篇采用有限个节点、每节点一台先到先服务服务器、无限等候空间的开放模型。外部到达为相互独立的泊松过程；节点 $i$ 的服务时长独立同分布，服从参数 ${\mu }_i>0$ 的指数分布，与到达、路由及其他服务相互独立。服务完成后的下一去向按固定概率 $p_{ij}$ 选择，与当前队长、历史和其他顾客独立；以 $p_{i0}=1-\sum _j{p}_{ij}$ 离开网络。

设 $P=(p_{ij})$ 为内部路由矩阵，要求路由是开放的，即每个内部节点最终离开的概率为一；有限状态下可表为 $\rho (P)<1$。外部到达率列向量为 $\gamma$，每个节点的总访问流率 $\lambda$ 满足流量方程 $$\lambda =\gamma +P^T\lambda ,\lambda =(I-P^T{)}^{-1}\gamma .$$ 这里 ${\lambda }_i$ 计的是访问次数流率，不是外来顾客中“第一次到这里”的人数。另要求每个利用率 $r_i={\lambda }_i/{\mu }_i<1$，才能使用下文可归一化的稳态分布；这与路由开放性是两个不同条件。

两节点流量与负荷

主例的服务率为 ${\mu }_1=3$、${\mu }_2=2$ 人/分钟。流量方程为 $$\begin{array}{cc}{\lambda }_1& =1+\frac{1}{4}{\lambda }_2,\\ {\lambda }_2& =\frac{1}{2}+\frac{1}{2}{\lambda }_1.\end{array}$$ 代入第一式得 $(7/8){\lambda }_1=9/8$，所以 ${\lambda }_1=9/7$、${\lambda }_2=8/7$。相应利用率为 $r_1=3/7$、$r_2=4/7$，均小于一。若只把外部流率一与半代入各自的单队公式，会漏算内部转移与返回带来的负荷。

箭头旁的外部数字是人每分钟，内部及离开箭头旁的数字是概率；图中明确区分两种量纲。返回路径使节点访问率高于各自外部到达率。

乘积形式及平衡证明

记 $N_i$ 为节点 $i$ 内人数，包括正在服务的人。在上述假设及稳定条件下，稳态概率为 $$\pi (n_1,\dots ,n_k)=\prod _{i=1}^k(1-r_i)r_i^{n_i},n_i=0,1,\dots .$$ 下面对无直接自回路 $p_{ii}=0$ 的情形验证全局平衡；主例属于此类。一般自回路可在状态转移中另行消去不改变人数的事件，不能把它误算成队长变化。

固定人数状态 $n$。其流出率为外部总率 $\sum _j{\gamma }_j$，加上每个非空节点的服务率 $\sum _{j:n_j>0}{\mu }_j$。候选乘积概率给出 $$\begin{array}{cc}\frac{\pi (n-e_j)}{\pi (n)}& =\frac{1}{r_j}(n_j>0),\\ \frac{\pi (n+e_i-e_j)}{\pi (n)}& =\frac{r_i}{r_j}(i\ne j,n_j>0).\end{array}$$ 先假设各节点有效流率为正，以免出现零比值。来自外部到达节点 $j$ 的流入，加上其他节点服务完成后转往 $j$ 的流入，除以 $\pi (n)$ 后，对每个非空 $j$ 合计为 $$\frac{{\gamma }_j+\sum _i{\lambda }_i{p}_{ij}}{r_j}=\frac{{\lambda }_j}{r_j}={\mu }_j.$$ 另外，从状态 $n+e_i$ 服务完成并离开网络，也会流入 $n$，相对率合计为 $\sum _i{\mu }_i{r}_i{p}_{i0}=\sum _i{\lambda }_i{p}_{i0}$。将流量方程对节点求和可得 $$\sum _i{\lambda }_i{p}_{i0}=\sum _j{\gamma }_j.$$ 故总流入恰好等于总流出。每个几何级数因 $r_i<1$ 收敛到一，乘积概率已归一化；有限节点与有限到达/服务率还保证这条连续时间链不在有限时间内发生无限次跳变。于是该概率给出稳态分布。流率为零、无法接收任何流量的节点在相关稳态中为空，可删除后应用上述证明。

这个推导验证了固定时刻队内人数的乘积形式，没有假定所有内部到达过程都是独立泊松流。尤其有反馈时，不能从最后的独立几何分布反推各条内部事件过程相互独立。

平均人数、每次停留与全程停留

主例全部节点同时为空的概率为 $$\pi (0,0)=(1-3/7)(1-4/7)=12/49.$$ 几何分布均值给出节点平均人数 $L_1=3/4$、$L_2=4/3$，总人数 $L=25/12$。全网络的外部到达率是 $1+1/2=3/2$ 人/分钟；按顾客从入网到离网计一次，Little定律给出 $$W=\frac{25/12}{3/2}=25/18\text{分钟}.$$ 不能把各节点平均停留时间直接相加，因为顾客的路径与访问次数并不相同。每次访问节点的平均停留为 $$W_1=\frac{L_1}{{\lambda }_1}=\frac{7}{12},W_2=\frac{L_2}{{\lambda }_2}=\frac{7}{6}\text{分钟}.$$ 每个外来顾客平均分别访问两个节点 ${\lambda }_1/(3/2)=6/7$ 次与 ${\lambda }_2/(3/2)=16/21$ 次，故 $$\frac{6}{7}\frac{7}{12}+\frac{16}{21}\frac{7}{6}=\frac{25}{18}\text{分钟},$$ 与全系统计算一致。平均访问次数可以小于一，因为并非每位外来顾客都访问每个节点；存在反馈时，平均访问次数也可能超过一。

两节点精确计算程序

代码求解本例相同结构的两节点开放网络；无自回路，参数依次为外部到达率、服务率、两个交叉路由概率。输入支持有理数，返回流率、利用率、全空概率、总人数及全程时间。所有外部率为零时，稳态为空，但没有外来顾客可定义平均停留时间，代码返回 None。

Python 3

from fractions import Fraction

def jackson_two(external, service, p12, p21):
    gamma, mu = tuple(map(Fraction,external)), tuple(map(Fraction,service))
    p, q = Fraction(p12), Fraction(p21)
    if len(gamma) != 2 or len(mu) != 2:
        raise ValueError("exactly two nodes required")
    if any(x < 0 for x in gamma) or any(x <= 0 for x in mu):
        raise ValueError("nonnegative arrivals and positive services required")
    if not (0 <= p <= 1 and 0 <= q <= 1) or p*q >= 1:
        raise ValueError("open Markov routing required")
    lam1 = (gamma[0]+q*gamma[1])/(1-p*q)
    lam2 = gamma[1]+p*lam1
    rates = (lam1,lam2)
    rho = tuple(v/m for v,m in zip(rates,mu))
    if any(r >= 1 for r in rho):
        raise ValueError("each utilization must be below one")
    p_empty = (1-rho[0])*(1-rho[1])
    number = sum((r/(1-r) for r in rho), Fraction(0))
    arrival = sum(gamma)
    time = number/arrival if arrival else None
    return rates, rho, p_empty, number, time

print(jackson_two([1,Fraction(1,2)],[3,2],Fraction(1,2),Fraction(1,4)))
# ((Fraction(9, 7), Fraction(8, 7)),
#  (Fraction(3, 7), Fraction(4, 7)), Fraction(12, 49),
#  Fraction(25, 12), Fraction(25, 18))

两个线性方程的消元直接给出流率，之后各式均已在上文推导；此固定两节点版本需要常数次有理数运算与常数额外空间，有理数的位复杂度另计。稳定性检查不可删去，否则几何级数不收敛，却可能算出负的“平均队长”。

变式。 将节点二的返回概率改为零，其余参数不变，得 ${\lambda }_1={\lambda }_2=1$，利用率为 $1/3,1/2$，总平均人数为 $1/2+1=3/2$，全程时间为一分钟。取消返回确实降低平均停留，但节点二仍会接收来自节点一的转移。

服务时间明显非指数、容量有限且阻塞、顾客按实时队长改道、批量到达或外部流量强相关时，上述证明的转移率结构改变，不能原样保留乘积形式。实际建模应先检查这些假设，而非只把测得的平均到达率代入公式。