排队系统的常用模型

1.单服务台模型

(1)基本排队模型[M/M/1]:[∞/∞/FCFS]

如前所述,[M/M/1]:[∞/∞/FCFS]模型的特征是输入为Poisson流,服务时间服从负指数分布,一个服务台;队列容量无限,顾客源数量无限,服务规则是先到先服务。这是一类最常见的排队问题。

图3-1　[M/M/1]:[∞/∞/FCFS]排队模型的图示

该模型系统运行指标如下:

①系统中的平均顾客数(即系统中顾客数的期望值)L。

　　L=kP_k=kρ^k(1-ρ)=(1-ρ)kρ^k

=(1-ρ)=

　　②队列中的平均顾客数L_q。

　　L_q=(k-1)P_k=(k-1)ρ^k(1-ρ)=(1-ρ)(k-1)ρ^k

=(1-ρ)=

即　L_q=ρL

③顾客在系统中的平均逗留时间。

　　W=

　　④顾客在队列中的平均等待时间。

　　W_q==ρW

　　(2)Little公式

由上述的四个公式可以得到:

　　虽然以上关系是从[M/M/1]:[∞/∞/FCFS]得到的,但可以证明,在很宽的条件下,以上关系都是成立的。对于后面讨论的系统,我们也可以利用Little公式推导出系统的运行指标。

(3)有限队列模型[M/M/1]:[N/∞/FCFS]

当系统的容量从无限值变为有限值N时,[M/M/1]:[∞/∞/FCFS]就转化成为[M/M/1]:[N/∞/FCFS]。[M/M/1]:[N/∞/FCFS]系统的图示如下:

图3-2　[M/M/1]:[N/∞/FCFS]排队模型的图示

系统的运行指标(推导过程略):

　　可以看出,在[M/M/1]:[N/∞/FCFS]系统中,如果考虑有效到达速率λ_e和有效服务强度ρ_e,[M/M/1]:[N/∞/FCFS]系统和[M/M/1]:[∞/∞/FCFS]系统的运行指标的形式是相同的。

(4)有限顾客源模型[M/M/1]:[∞/m/FCFS]

这是一种所谓的有限顾客源模型。设顾客总数为m,当顾客需要服务时,就进入队列等待;服务完毕后,重新回到顾客源中。如此循环往复。在这类问题中,由于顾客源的数量是有限的,因此队列的长度也是有限的,并且队列的长度必定小于顾客源总数。

有限顾客源模型可以用图3-3示意。

图3-3　[M/M/1]:[∞/m/FCFS]排队模型的图示

求得系统的运行指标如下:

2.多服务台模型[M/M/C]

[M/M/C]模型是研究单队、并列的多服务台排队系统。如同单服务台系统一样,分为以下几种情况进行讨论:(1)标准的[M/M/C]:[∞/∞/FCFS]模型;(2)系统容量有限的[M/M/C]:[N/∞/FCFS]模型;(3)有限顾客源的[M/M/C]:[∞/m/FCFS]模型。

(1)[M/M/C]:[∞/∞/FCFS]模型

这个模型的队列与服务台的关系可用图3-4表示:

图3-4　[M/M/C]:[∞/∞/FCFS]排队模型的图示

即顾客到达后,进入队列尾端;当某一个服务台空闲时,队列中的第一个顾客即到该服务台接受服务,服务完毕后随即离去。各服务台互相独立且服务速率相同,即μ₁=μ₂=…=μ_c。

这个系统的特点是,系统的服务速率与系统中的顾客数有关。当系统中的顾客数k不大于服务台个数,即1≤k≤c时,系统中的顾客全部在服务台中,这时系统的服务速率为k_μ;当系统中的顾客数kkengdiegt;c时,服务台中正在接受服务的顾客数仍为c个,其余顾客在队列中等待服务,这时系统的服务速率为cμ。

用与单服务台系统同样的方法,可以得到[M/M/C]:[∞/∞/FCFS]的运行指标:

　　(2)系统容量有限的[M/M/C]:[N/∞/FCFS]模型

设系统容量为N(N≥c),当系统中的顾客数nkengdielt;N时,到达的顾客就进入系统;当n=N时,到达的顾客就被拒绝。设顾客到达的速率为λ,每个服务台服务的速率为μ,ρ=λ/cμ。由于系统不会无限制地接纳顾客,对ρ不必加以限制。

系统的运行指标:

　　特别要注意的是,当N=c时,系统的队列最大长度为0,即顾客到达时,如果服务台有空闲,则进入服务台接受服务,如果服务台没有空,顾客则当即离去。这样的系统成为“即时制”。许多服务设施,如旅馆、停车场等都具有这样的性质。

图3-5　[M/M/C]:[∞/m/FCFS]排队模型的图示

(3)顾客源有限的[M/M/C]:[∞/m/FCFS]模型

设顾客源为有限数m,服务台个数为c,且mkengdiegt;c。这个模型的典型例子是机器维修问题,机器数量为m台,修理工数量为c人。

相应的运行指标如下:

平均故障机器数:L=nP_n

平均等待修理机器数:L_q=(n-c)P_n