排队仿真——等待线系统的建模与分析
- 提出者
- Agner Krarup Erlang
- 年份
- 1909
- 类型
- Stochastic simulation / analytical modeling
- 类别
- Simulation / optimization
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
排队仿真结合了经典的排队论和离散事件仿真,用于对实体到达、等待服务和离开的系统进行建模。它预测平均等待时间、队列长度和服务器利用率等性能指标,从而能够对服务、制造、医疗保健和网络系统进行容量规划和瓶颈识别。
方法背后的直觉
每当顾客排队等待时——无论是在银行、医院急诊室,还是在计算机网络中——都会形成一个队列。系统的行为取决于实体的到达速度、服务所需时间以及服务器的数量。排队仿真通过多次重放随机的到达和服务过程来捕捉这些动态,并测量平均等待时间和拥塞情况。与纯粹的公式不同,仿真可以处理复杂的调度、多种队列类型以及闭式方程无法解决的非标准分布。
历史学
排队论由丹麦工程师Agner Krarup Erlang于1909年在研究哥本哈根电话公司电话交换拥塞时创立。他的Erlang-B和Erlang-C公式至今仍在使用。Kendall(1953)通过其符号体系,以及Kleinrock(1975)在计算机网络领域的贡献,使该领域得以形式化。随着计算机在20世纪60-70年代使大规模随机建模成为可能,基于仿真的排队分析应运而生。
何时使用
当系统涉及实体等待共享资源且需要定量性能预测时,使用排队仿真——呼叫中心、急诊科、制造生产线、计算机网络、物流枢纽。当分布为非马尔可夫、服务过程与状态相关或多个交互队列使得闭式解难以处理时,优先选择仿真而非分析排队模型。当系统没有拥塞动态、确定性调度足够或到达和服务时间的样本数据稀疏到无法可靠拟合输入分布时,请勿使用。
局限与注意事项
- 需要足够的经验数据来拟合到达和服务分布;输入模型不佳会导致误导性输出。
- 稳态估计需要仔细的预热期删除和复制规划,这并不简单。
- 对于复杂网络或罕见事件估计,仿真运行时间可能很长。
- 结果是具有置信区间的随机估计值,而不是精确值——需要统计解释。
- 模型验证至关重要但困难;如果假设错误,一个看似合理的模型可能会产生系统性偏差结果。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 处理闭式排队公式无法解决的复杂、非马尔可夫到达和服务分布。
- 在统一框架内对具有路由、优先级和有限缓冲的多服务器、多队列网络进行建模。
- Little法则提供了独立于分布假设的内部一致性检查。
- 通过改变系统参数而无需物理实验,支持“假设”分析和容量规划。
- 输出置信区间为决策提供统计上严格的不确定性量化。
- 在不同领域得到广泛验证:电信、医疗保健、制造和交通。
应用
- 医院急诊科容量规划和分诊优先级优化。
- 呼叫中心人员配置和服务水平协议合规性分析。
- 电信网络路由器缓冲区大小调整和数据包延迟估计。
- 制造生产线吞吐量分析和瓶颈识别。
- 机场值机和安检通道配置以管理乘客流量。
- 云计算资源分配和可变工作负载下的作业调度。
使用方式
使用方式
定义系统边界:确定实体类型(顾客、作业、数据包)、服务器(资源)、队列规则(先进先出、优先级、轮转)和容量限制。指定网络拓扑——单队列、串联队列或具有节点间路由概率的通用排队网络。
将到达和服务时间分布拟合到观测数据。常见的选择是泊松到达(速率λ)和指数服务时间(速率μ),构成M/M/c族。对于实际系统,使用爱尔兰分布、伽马分布或通过拟合优度检验拟合的经验分布。在运行仿真之前验证输入模型。
公式
\lambda \sim \text{Poisson}(\lambda),\quad S \sim \text{Exp}(\mu)选择Kendall符号模型(A/B/c/K/N/D):到达分布/服务分布/服务器/容量/总体/规则。验证稳定性条件ρ = λ / (c * μ) < 1;否则队列将无限增长。对于可解析处理的情况,计算闭式稳态指标作为基准。
公式
\rho = \lambda / (c \cdot \mu) < 1
运行离散事件仿真:事件日历按到达事件、服务开始事件和离开事件推进。对于每次复制,实体从拟合的分布中生成,通过系统路由,并收集统计数据。运行足够的复制(或删除预热期的长单次运行)以获得稳态估计。
估计关键性能度量:系统中平均数量L,队列中平均数量Lq,系统中平均时间W,以及平均等待时间Wq。Little法则(L = λ * W)将这些量联系起来,并作为一致性检查。计算服务器利用率ρ以及等待或被阻塞的概率。
公式
L = \lambda W,\quad W_q = L_q / \lambda
使用批次均值或独立复制为每个性能指标构建置信区间。通过改变到达率、服务率或服务器数量进行敏感性分析,以识别瓶颈。使用排序和选择或公共随机数方差缩减技术比较设计方案(例如,增加服务器、改变规则)。
常见陷阱
- 忽略预热(瞬态)期会导致稳态估计偏差,混合了初始空系统行为和真实性能。
- 在未检验数据的情况下假设泊松到达;过度分散或突发性到达(例如,在网络中)需要更重尾的分布。
- 将单次仿真运行报告为确定性结果,而没有置信区间或复制。
- 将不稳定的队列(ρ ≥ 1)视为已达到稳态——模型只会显示不断增长的队列。
- 混淆吞吐量与利用率:服务器可以被利用90%,但吞吐量仍然受上游瓶颈的限制。
常见问题
何时应使用仿真而非M/M/c公式?
当服务或到达分布与指数分布显著偏离(例如,确定性服务、高方差)、多个队列通过路由相互作用、服务器发生故障或有调度安排,或者需要瞬态(时变)性能而非稳态平均值时,应使用仿真。
需要多少次复制?
没有通用答案。初步研究5-10次复制可以估计方差;然后使用公式n = (z * s / ε)^2 在置信水平z下找到达到期望半宽度ε所需的次数。通常20-50次复制足以达到中等精度,但罕见事件问题可能需要数千次。
什么是Little法则及其重要性?
Little法则指出L = λ * W:系统中平均数量等于到达率乘以在系统中花费的平均时间。它适用于几乎任何稳定的队列,无论其分布如何,并可作为仿真输出的合理性检查。
如何知道我的队列是否稳定?
对于单服务器队列,交通强度ρ = λ / μ必须严格小于1。对于c个服务器,ρ = λ / (c * μ) < 1。如果ρ ≥ 1,则队列不稳定并无限增长;不存在稳态分布,仿真结果将显示等待时间不断增加。
排队仿真能处理优先级队列和抢占吗?
是的。离散事件仿真自然地适应了多优先级类别、可抢占和不可抢占调度以及动态优先级规则。只有在泊松到达的M/M/c/PR(抢占恢复优先级)情况下才存在解析结果;对于其他优先级结构,仿真是一种标准方法。
相关方法
参考文献
Kleinrock, L. (1975). Queueing Systems, Volume 1: Theory. Wiley-Interscience, New York.
ISBN:978-0471491101已复制。Law, A. M. (2015). Simulation Modeling and Analysis (5th ed.). McGraw-Hill Education, New York.
ISBN:978-0073401324已复制。