【科研相关知识】运筹学——排队论模型

• 排队论——排队系统模型
  • 1. 基本概念
    • (1) 输入过程
    • (2) 排队规则
    • (3) 服务机构
    • (4) 排队系统模型表示
    • (5) 排队系统指标
  • 2. 马尔科夫排队模型

排队论——排队系统模型

运筹学是一门研究如何在有限资源条件下做出最优决策的学科。它结合了数学、统计学和计算机科学等多个领域的理论和方法，以解决各种实际问题，如生产调度、物流优化、资源分配、项目管理等。运筹学的目标是通过建立数学模型和运用优化算法，使得在面对复杂的决策问题时能够找到最佳的解决方案。

1. 基本概念

排队的一般过程如下图所示：

排队系统基本组成部分：

1. 输入过程(顾客按照怎样的规律到达)
2. 排队规则(顾客按照一定规则排队等待服务)
3. 服务机构(服务机构的设置、服务台的数量、服务的方式、服务时间分布等)

(1) 输入过程

1. 顾客源
   即顾客的总体，可以是无限的，也可以是有限的(N)。

2. 顾客到达方式
   顾客或单个到达，或成批到达。主要研究单个到达。

3. 顾客到达时间间隔分布
   即顾客相继到达的时间间隔的分布，常见的概率分布：负指数分布、k阶爱尔朗分布等。

定理：在排队系统中，如果单位时间内顾客到达数服从以λ为参数的泊松分布，则顾客相继到达的时间间隔服从以λ为参数的负指数分布

(2) 排队规则

1. 排队系统类型
   顾客到达时，如果所有服务台都被占用，排队等候的称为等待制，随即离去的称为损失制。

2. 排队队列
   队列可以是单列，也可以是多列，正如路由器微体系结构中的VC虚拟通道。

3. 接受服务的顺序

• 先来先服务(FCFS)
• 后到先服务(LCFS)
• 随机服务(SIRO)
• 优先服务(PR)

(3) 服务机构

服务台数量有单服务台，也有多服务台，其构成形式主要有以下五种：

• 单队列-单服务台
  

• 单队列-多服务台并联式
  

• 多队列-多服务台并联式
  

• 单队列-多服务台串联式
  

• 单队列-多服务台串并联混合式
  

(4) 排队系统模型表示

排队系统模型可以表示为：A/B/C/D/E/F
分别表示顾客到达时间间隔分布/服务时间分布/服务台数目/系统中顾客容量限制/顾客源数目/服务规则。

1. 顾客到达时间间隔分布：M——负指数分布
2. 服务时间分布：M——负指数分布
3. 服务台数目：1——一个服务台，C——多个服务台，即M/M/1代表一个服务台，M/M/C代表多个服务台
4. 系统中顾客容量限制：∞——系统中顾客容量无限制，N——系统中最多容纳N个顾客
5. 顾客源数量：∞——顾客源数量无限多，N——顾客源数量有N个
6. 服务规则：如FCFS——先来先服务

(5) 排队系统指标

1. 状态概率分布Pn：系统中有n个顾客的概率
2. 队长L：系统中的平均顾客数，包括正在服务和正在排队等待的顾客
3. 排队长Lq：系统中排队等待的平均顾客数
4. 顾客平均停留时间：W
5. 顾客平均等待时间：Wq

Little公式：

2. 马尔科夫排队模型

• 生灭过程
  一群细菌，每个细菌在时段$\Delta t$内分裂成两个的概率为$\lambda \Delta t+o(\Delta t)$，死亡的概率为$\mu \Delta t+o(\Delta t)$，既不分裂也不死亡保持不变的概率为$1-(\lambda +\mu )\Delta t+o(\Delta t)$。各个细菌在任何时间段的分裂和灭亡都是独立的。若将其都看作一个事件的话，任意时刻$t$的细菌总数$X(t)$为多少？

• 马尔科夫排队模型(生灭过程排队系统)
  将一个新顾客到来看作为生，将一个顾客服务完离开看作死，设置$N(t)$为任意时刻$t$排队系统的状态。满足下列生灭过程特征的排队模型称为马尔科夫排队模型：

  • 给定$N(t)=n$，到下一个顾客到达的间隔时间服从参数为${\lambda }_n(n=0,1,2,...)$的负指数分布；
  • 给定$N(t)=n$，到下一个顾客离开的间隔时间服从参数为${\mu }_n(n=0,1,2,...)$的负指数分布；
  • 同一时刻只有一个顾客达到或离去。

• 状态平衡方程
  

则P0+P1+…+Pn = 1，即可以算出P0，并可以依次算出所有Pi。