第9章排队论 排队论是我们每个人都很熟悉的现象。因为人或物或是信息为了得到某种服 务必须排队。有一类排队是有形的,例如在售票处等待买票的排队,加油站前汽 车等待加油的排队等:还有一类排队是无形的,例如电话交换机接到的电话呼叫 信号的排队,等待计算机中心处理机处理的信息的排队等。为了叙述的方便,排 队者无论是人、物、或信息,以后统称为“顾客”。服务者无论是人,或事物, 例如一台电子计算机也可以是排队系统中的服务者,我们以后统称为“服务员”。 排队现象是我们不希望出现的现象,因为人的排队意味着至少是浪费时间 物的排队则说明了物资的积压。但是排队现象却无法完全消失,这是一种随即现 象。由于顾客到达间隔时间的随机性和为顾客服务时间的随机性是排队现象产生 的原因。如果上述的两个时间是固定的,我们就可以通过妥善安排来完全消除排 队现象 排队论是研究排队系统在不同的条件下(最主要的是顾客到达的随机规律和 服务时间的随机规律)产生的排队现象的随机规律性。也就是要建立反映这种随 机性的数学模型。研究的最终目的是为了运用这些规律,对实际的排队系统的设 计与运行做出最优的决策 排队论中的数学模型是根据概率和随机过程的理论建立起来的,我们先来讨 论泊松过程和生灭过程,然后,再此基础上研究排队系统的结构及其主要的数学 模型,最后研究排队系统的优化问题。 9.1泊松过程和生灭过程 911泊松过程 如果用N(1)表示在[0,n时间内顾客到达的总数,则对于每个给定的时刻 N()都是一个随机变量。随即变量族{NO)∈[O,T}称作是一个随机过程 若对1<t2<…tn<tn+,有 P(N(tn+)=i+|N(t)=i,N(t)=12…,N(t)=1n P(N(n+)=in+N(m)=im) 1 则称随即过程{N()∈,T)为马尔柯夫过程。公式(91)所标示的性质称 为“无后效性”。它的实际意义是说:如果用tn表示现在时刻,tn+表示未来时 刻,t1n2…,tn1表示过去的一系列时刻,则顾客到来的过程在tn以前所处的状态第 9 章 排队论 排队论是我们每个人都很熟悉的现象。因为人或物或是信息为了得到某种服 务必须排队。有一类排队是有形的，例如在售票处等待买票的排队，加油站前汽 车等待加油的排队等；还有一类排队是无形的，例如电话交换机接到的电话呼叫 信号的排队，等待计算机中心处理机处理的信息的排队等。为了叙述的方便，排 队者无论是人、物、或信息，以后统称为“顾客”。服务者无论是人，或事物， 例如一台电子计算机也可以是排队系统中的服务者，我们以后统称为“服务员”。 排队现象是我们不希望出现的现象，因为人的排队意味着至少是浪费时间； 物的排队则说明了物资的积压。但是排队现象却无法完全消失，这是一种随即现 象。由于顾客到达间隔时间的随机性和为顾客服务时间的随机性是排队现象产生 的原因。如果上述的两个时间是固定的，我们就可以通过妥善安排来完全消除排 队现象。 排队论是研究排队系统在不同的条件下（最主要的是顾客到达的随机规律和 服务时间的随机规律）产生的排队现象的随机规律性。也就是要建立反映这种随 机性的数学模型。研究的最终目的是为了运用这些规律，对实际的排队系统的设 计与运行做出最优的决策。 排队论中的数学模型是根据概率和随机过程的理论建立起来的，我们先来讨 论泊松过程和生灭过程，然后,再此基础上研究排队系统的结构及其主要的数学 模型，最后研究排队系统的优化问题。 9.1 泊松过程和生灭过程 9.1.1 泊松过程 如果用 表示在[0 时间内顾客到达的总数，则对于每个给定的时刻 ， 都是一个随机变量。随即变量族 N t( ) ,t] t N t( ) { ( N t) t ∈[0,T]}称作是一个随机过程。 若对 t t 1 2 < <"t n <t n+1，有 1 111 2 2 ( ( ) ( ) , ( ) , , ( ) P N t i n n + + = = N t i N t = i " N t n = in 1 1 ( ( ) ( ) ) = = P N t i n n + + N t n = in (9-1) 则称随即过程{ ( 为马尔柯夫过程。公式（9-1）所标示的性质称 为“无后效性”。它的实际意义是说：如果用t 表示现在时刻，t 表示未来时 刻，t t 表示过去的一系列时刻，则顾客到来的过程在t 以前所处的状态 N t) t ∈[0,T)} n n+1 1 2 1 , , , " t n− n