[科普中国]-单渠道随机排队法

排队论

排队论是运筹学的重要分支之一，排队论又称随机服务系统理论或等待线理论，是研究排队拥挤现象的一门学科，即研究在保证服务质量的前提下，使得服务、设施及费用既经济又合理。排队论所要解决的主要问题是如何合理地设计与控制随机服务系统，使得它既能满足顾客需要，又能使机构的花费最小。

在排队论中，称要求服务的对象为顾客，称从事服务的机构或个人为服务台。顾客—服务台，形成排队的结构。顾客为了得到某种服务到达系统，在没有得到服务时容许排队等待，此时加入到等待的队伍中，获得服务后离开系统。在排队系统中，顾客到达时间与服务台为其服务时间是随机的，故随机性是排队系统的基本特征。故排队论又称随机服务系统理论。
20世纪50年代初，堪道尔(D.G.Kendall)对排队论作了系统的研究，他用嵌入马尔柯夫链方法研究排队论，使排队论得到了进一步的发展。是他首先（1951年）用3个字母组成的符号A/B/C表示排队系统。其中A表示顾客到达时间分布，B表示服务时间的分布，C表示服务机构中的服务台的个数。

例如：M/M/1是指顾客到达的时间间隔服从参数为1/λ的泊松分布，服务时间服从参数为1/μ的指数分布，服务台的个数为1的排队模型。此模型顾客的到达与服务时间均相互独立、随机的。M/M/c是指顾客到达的时间间隔服从参数为1/λ的泊松分布，服务时间服从参数为1/μ的指数分布，服务台的个数为c的排队模型。此模型顾客的到达与服务时间均相互独立的、随机的。顾客在系统内排成一列等待服务，排队空间无限。

任何一个随机服务系统的运行过程的三个基本组成部分：顾客输入、排队规则、服务机构。

(1)顾客的输入：顾客到达排队系统的过程称为输入过程。输入过程最基本的特征是顾客到达间隔时间的概率分布。
(2) 排队规则：排队所遵循的规则，从队列中挑选顾客进行服务的规则。根据顾客对等待的态度分为损失制与等待制。常用的排队规则：先到先服务、后到先服务、优先权服务、随机服务。

(3)服务机构：服务台的个数(单通道、多通道)，服务台的排列(并联、串联)，服务时间(确定性、随机型)2。

系统模拟模拟又称仿真，它的基本思想是构造一个试验的模型，这个模型与我们研究的系统的主要性能十分近似。模拟是一种定量过程，先为过程设计一个模型，然后再组织一系列的反复试验，以预测该过程全部时间里所发生的情况。

使用模拟的原因：

1.由于难以观察到实际环境，模拟可能是惟一可以利用的方法；

2.不可能求出一个数学解；

3.实际观察一个系统可能太费钱；

4. 不可能有足够的时间来广泛地操作该系统；

5. 对一个系统的实现运用和观察可能破坏性太大。

模拟的不足：

1.模拟是不精确的；

2.一个良好的模型可能是非常昂贵的；

3.并非所有的方法都可用模拟的方法来估算；

4.模拟能产生一种估算答案的方法，但不能得出答案本身。

系统模拟过程是建立模型并通过模型的运行对模型进行检验和修正，使模型不断趋于完善的过程3。

步骤如下：

1.确定要模拟的问题和系统；

2.将所要用的模型化为公式；

3.测试模型：将其情况与真实问题周围的情况作比较；

4.鉴别和收集所需数据以测试模型；

5.执行该模型；

6. 分析模型结果；

7. 重新执行该项模拟以测试新答案；

8. 使模拟生效4。

排队系统模拟描述1.顾客到达模式：用到达时间间隔来描述，可分为确定性到达及随机性到达。随机性到达采用概率分布来描述，最常采用的泊松到达。
2.服务模式：描述服务台为顾客服务的时间：确定性的，也可能是随机的。
3.排队规则：服务台完成当前的服务后，从队列中选择下一实体的原则。
FCFS——先到先服务； LCFS——后到先服务；PS——根据实体的重要程度选择最优先服务者。
4.服务流程：多个服务台，多个队列，如何从某一个队列中选择某一个实体服务，包括实体可否换队及换队规则等。
5.系统状态：一个事件是引起系统状态瞬时变化情况的集合。在服务台排队系统中两个可能的事件会影响系统的状态：顾客进入系统（到达事件）和顾客离开系统（离开事件）。

6**.**事件：引起系统状态发生变化的行为。事件表：管理事件的表。时钟： 标记事件出现的时间的时钟。
随机数： 事件是随机出现的，为了模仿现实生活中所需的随机性，应用“随机数”来完成。

7.随机数

随机数（number)是在区间（0，1)上独立和均匀分布的；随机数字(digit)是在集合{0，1，2，3，…，9}上均匀分布的随机数字可用来产生随机数；从随机数字表上选取合适的随机数字，在选取的随机数字的左边加上十进制的小数点，可以构成随机数；当用一组过程产生随机数时，他们经常被称为伪随机数2。

仿真实例实例：假设6个顾客，到达时间间隔是随机的，服务时间也是随机的，仿真单服务台排队系统。

基本假设：

1.顾客总体（无限）
顾客进入等候线或进入服务不会改变人的到达率；同时只有一个顾客以随机的方式到达；顾客一旦进入等候线最终将得到服务。
2.服务时间
服从某一概率分布，分布不随时间而变化。
3.系统的容量
无限的（被服务的人数加上等候的人数）。
4.被服务的规则
服务员进行服务的次序（ FCFS ，先来先服务）。
5.到达和服务描述
到达间隔时间分布和服务时间分布描述的整个有效的到达率必须小于最大的服务率1。

仿真过程：

1.到达时间 到达事件间隔和时钟时间由掷6个值骰子五次并记录它们的点数来产生，用来计算排队系统的6个顾客的到达时间。

|| || 表1 到达间隔和时钟时间

2.服务时间

服务时间假设有1，2，3，4个时间单位，假定所有的4个值等可能出现。把4个值预先刻在筹码上，然后，轮回随机抽取筹码，将选到的数据记录下来。排队系统到达间隔时间和服务时间必须匹配。

|| || 表2 服务时间

3.仿真表

仿真表是为单服务台队列设计的。仿真表记录了每个事件出现时的时钟时间。第2列是到达时间的时钟时间；表第5列记录了每个离开事件的时钟时间；两类事件按照时间顺序排列。

|| || 表3 仿真表

4.服务顾客的规则：先进先出
5.按时间次序顺序的事件

|| || 表4 仿真事件

应用范围单渠道随机排队法广泛应用于港口的模拟，港口的等待时间分布问题；机场的模拟，飞机的起飞，着陆的分布问题等2。