离散事件仿真 (DES)
- 提出者
- Banks, Carson, Nelson & Nicol (textbook lineage); foundational work by Tocher & Conway (1960s)
- 年份
- 1960s (formalized); modern computational form from 1970s onward
- 类型
- Stochastic process simulation
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
离散事件仿真 (DES) 是一种计算建模范式,其中系统的状态仅在可数的时间点序列——即事件——发生变化。在事件之间,状态不发生变化,因此仿真时钟直接从一个事件跳转到下一个事件。DES 通过 Banks、Carson、Nelson 和 Nicol 以及 Law 在 20 世纪 60 年代至 21 世纪初的奠基性教科书得以形式化,已成为分析排队系统、医疗患者流、制造生产线和物流网络(其中实体随时间在资源之间移动)的标准工具。
方法背后的直觉
想象一个医院急诊科:患者到达、等待护士、接受治疗、然后离开。现实生活不是每毫秒都在更新——它只在发生某事时才改变:患者到达、护士空闲、或患者出院。DES 精确地捕捉了这种逻辑。仿真维护一个未来事件的排序列表,并逐一处理它们,将虚拟时钟推进到每个事件时间,而不是逐毫秒地进行计算。这使得它即使对于复杂系统也能快速运行,并且让分析师能够询问“如果我们增加一名护士会怎样?”或“周一的到达人数翻倍会怎样?”而无需干预真实系统。
历史学
DES 的基础由 K.D. Tocher 和 R.W. Conway 等研究人员在 20 世纪 50 年代末和 60 年代初奠定,他们开发了第一个通用仿真语言(GSP、GPSS)。事件调度范式——维护一个按时间排序的未来事件列表——在 20 世纪 70 年代成为标准。Banks、Carson、Nelson 和 Nicol 的教科书(第一版 1984 年,现为第五版,2010 年)以及 Law 的配套书籍(第一版 1982 年,现为第五版,2015 年)巩固了定义现代实践的方法论、输出分析程序和输入建模技术。DES 在运筹学、工业工程和医疗管理领域迅速普及,如今已在开源库(SimPy、simmer)和商业平台中实现。
何时使用
只要系统可以被描述为离散实体在随机到达和服务时间支配的资源中移动,DES 就适用。它适用于排队系统、急诊科和医院病房流程、制造和供应链吞吐量分析、呼叫中心人员配置以及物流路由——无论何时分析师需要评估容量、瓶颈或“假设”场景而无需在真实系统上进行实验。不需要正态性假设。重复试验次数必须足够(通常至少 30 次,或对于窄置信区间需要 ≥1000 次)——重复试验次数太少会导致 DES 结果不可靠,此时分析性排队模型可能更优。分布输入(到达和服务时间分布)必须根据历史数据进行估计;当没有数据时,需要专家访谈或试点运行。
局限与注意事项
- 输入不确定性:结果的可靠性仅取决于拟合的到达和服务分布。
- 预热偏差:忽略预热期会夸大或缩小稳态估计值。
- 重复试验:重复试验次数太少(少于约 30 次)会导致置信区间过宽,使得场景比较不可靠。
- 计算成本:具有许多实体和资源的复杂模型可能需要大量运行时间才能获得窄置信区间。
- 模型验证需要历史数据进行校核;映射不当的流程会导致误导性输出。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 处理分析性排队模型无法表示的复杂、非线性过程——资源争用、可变路由、优先级队列。
- 通过独立重复试验产生真实的置信区间,使不确定性明确化。
- 支持“假设”实验和场景比较,而不会中断真实系统。
- 对输出没有分布假设;可以适应任何输入分布。
- 适用于广泛的领域——医疗保健、制造、物流、服务运营——而无需更改核心范式。
应用
- 急诊科患者流:评估人员配置水平、分诊策略和床位容量以减少等待时间。
- 制造吞吐量:识别瓶颈工作站、确定缓冲区大小和规划班次表。
- 供应链和物流:在随机需求下模拟仓库运营、配送路线和库存补充。
- 呼叫中心人员配置:确定座席数量和路由规则以满足服务水平协议。
- 机场和港口运营:模拟登机口分配、地面服务和货物吞吐量。
使用方式
使用方式
分析师映射真实流程:实体(患者、作业、车辆)、资源(护士、机器、卡车)、队列和路由逻辑。这个概念模型是后续一切的基础——模糊的流程图会产生不可靠的仿真。
到达间隔时间和服务持续时间根据历史数据和拟合优度检验,被拟合到概率分布——通常是指数分布、爱尔兰分布、对数正态分布或经验分布。分布输入是 DES 中不确定性的主要来源;如果数据稀缺,跨越合理分布族的敏感性分析至关重要。
初始化事件日历(未来事件列表)。每种事件类型(到达、服务开始、服务结束、离开)都用其引起的状态转换进行编码。随机数流驱动每个随机元素,并为到达和服务过程分配单独的流,以便稍后应用诸如公共随机数之类的方差缩减技术。
在收集统计数据之前,仿真会运行一个预热期。在时间零点,系统通常是空的——一种人为的初始条件,会使稳态估计产生偏差。预热期(通过 Welch 方法或类似方法估计)允许系统在测量开始前达到统计平衡。
运行多个独立的重复试验,每次使用不同的随机种子。统计分析的单位是重复试验,而不是单次运行中的观测值。建议至少进行 30 次重复试验以获得可靠的置信区间估计;所需次数可以通过序贯试点程序确定。
计算跨重复试验的汇总统计数据——平均等待时间、吞吐量、资源利用率——并报告 95% 的置信区间。如果置信区间过宽,则应用更多的重复试验或方差缩减技术。场景比较使用相同的随机种子(公共随机数)来减少场景间的噪声。
常见陷阱
- 在需要窄置信区间时运行少于 1000 次重复试验——使用序贯试点程序确定所需的最小次数。
- 省略或低估预热期——从时间零点的空系统收集的稳态指标,对于利用率会向下偏差,对于等待时间会向上偏差。
- 使用一次长运行代替多次独立重复试验——运行内的观测值是自相关的,不能作为置信区间估计的独立数据点。
- 将错误的分布族拟合到到达或服务时间——在接受拟合分布之前,务必进行正式的拟合优度检验,并将拟合分布与经验数据进行比较。
- 混淆 DES 与连续仿真——DES 适用于状态变化由事件驱动的系统;对于连续演变的存量和流量,系统动力学是正确的范式。
常见问题
我需要多少次重复试验?
对于初步分析,通常从至少 30 次独立的重复试验开始,但用于决策的窄置信区间通常需要 100-1000 次或更多。使用序贯试点程序:运行初始批次的 10-30 次重复试验,估计方差,然后计算达到目标半宽度所需的额外重复试验次数。
我如何确定预热期?
Welch 图形法是最常用的方法:绘制性能指标随时间的移动平均线,并确定其稳定的点。或者,使用 Mecklenburg-White 检验,或简单地运行模型足够长的时间,使预热期占总运行长度的不到 10%。省略预热期会使稳态估计产生偏差。
我何时应该使用 DES 而不是分析性排队模型?
分析性排队模型(M/M/c 及其变体)为简单、理想化的系统提供精确或近似的闭式结果。当流程具有复杂路由、多个竞争资源类型、非指数服务时间、批量到达或时变到达率时,应使用 DES——这些情况分析性解决方案不可用或需要不切实际的简化假设。
如果我没有用于拟合分布的历史数据怎么办?
专家访谈(例如,最小、最可能、最大估计值以拟合三角形分布)是初步模型的可接受的备选方案。进行跨越合理分布族的敏感性分析,以了解输入不确定性如何传播到输出不确定性。随着模型的成熟收集真实数据。
相关方法
参考文献
Banks, J., Carson, J.S., Nelson, B.L. & Nicol, D.M. (2010). Discrete-Event System Simulation (5th ed.). Pearson.
ISBN:978-0136062127已复制。Law, A.M. (2015). Simulation Modeling and Analysis (5th ed.). McGraw-Hill.
ISBN:978-0073401324已复制。