排队论基础 第5版

本书介绍了如何分析排队模型的概率性质，以及分析过程中所涉及的统计原理。作者并没有局限于某个特定的应用领域，而是基于计算机科学、工程学、商业和运筹学等多个领域的实践阐述了相关的排队论理论。本书特别介绍了一种数值方法，可以帮助读者理解排队论并对相关数据进行估算，并全面地介绍了简单的和高级的排队模型。 本书扩展了对排队论的定性（非数学）描述，包括对日常生活中排队场景的描述，扩展了对随机过程的介绍，包括泊松过程及马尔可夫链。在介绍理论知识的同时，本书还提供了实际应用的例子，所有习题都已经过国外本科及研究生高等课程的课堂测试，可以帮助读者掌握解决实际排队问题的技巧。各章所介绍的关键概念和公式都是相对独立的，读者可以单独阅读感兴趣的内容。 本书可作为高等院校应用数学、统计学等专业师生的参考书，也可为应用数学、运筹学、工程学和工业工程领域的从业者提供有益参考。

约翰·F.肖特尔（John F. Shortle）博士 美国乔治?梅森大学系统工程与运筹学系教授。他撰写了30多篇关于仿真和排队论在电信和航空领域应用的文章。 詹姆斯?M.汤普森（James M. Thompson） 美国房地美公司架构师。他目前的研究领域包括计算机系统性能建模、系统容量研究和基准测试、信息架构和计算金融。 唐纳德?格罗斯（Donald Gross）博士 美国乔治?梅森大学运筹学与工程学杰出的研究教授，乔治?华盛顿大学运筹学名誉教授。格罗斯博士在学术界和咨询果拥有40多年的经验，他在可修复件库存控制、空中交通管制和网络拥塞等排队论的应用领域发表了大量的文章。 卡尔?M.哈里斯（Carl M. Harris）博士 （1940—2000） 美国乔治?梅森大学系统工程与运筹学系创始主席。由于哈里斯博士在应用概率统计、排队论、仿真和公共系统分析等领域的研究贡献，美国运筹学与管理科学研究协会（Institute for Operations Research and the Management Sciences, INFORMS）于1999年授予他乔治? E.金博尔（George E. Kimball）奖章。

第 1章 基础知识. . 1 1.1 系统的效益指标. . . 2 1.2 排队系统的特征. . . 3 1.2.1 顾客的到达过程. . . 4 1.2.2 服务员的服务过程. 4 1.2.3 服务员的数量和服务通道的数量. . 5 1.2.4 排队规则. 5 1.2.5 系统容量. 6 1.2.6 服务阶段的数量. . . 6 1.2.7 表示法. . . 7 1.2.8 模型选择. 8 1.3 等待的体验8 1.4 利特尔法则. . . 10 1.4.1 利特尔法则的几何式图解. . .14 1.4.2 H = λG. 16 1.4.3 利特尔法则的分布形式18 1.5 一般结果. 20 1.6 队列的简单记录. . 23 1.7 软件介绍. 26 习题. . . 27 第 2章 随机过程回顾33 2.1 指数分布. 33 2.2 泊松过程. 37 2.3 离散时间马尔可夫链. .47 2.3.1 马尔可夫链的性质50 2.3.2 长期行为51 2.3.3 遍历性. . 58 2.4 连续时间马尔可夫链. .61 2.4.1 嵌入离散时间马尔可夫链. . .64 2.4.2 C-K 方程65 2.4.3 长期行为68 习题. . . 69 第3章 简单马尔可夫排队模型. . . 72 3.1 生灭过程. 72 3.2 单服务员排队模型（M/M/1） . . . 77 3.2.1 用迭代法求解{pn} . . . 78 3.2.2 用母函数求解{pn} . . . 79 3.2.3 用线性算子求解{pn}. .81 3.2.4 效益指标83 3.2.5 等待时间的分布. . 88 3.3 多服务员排队模型（M/M/c） . . . 91 3.4 服务员数. 98 3.5 截尾的排队模型（M/M/c/K） . 102 3.6 埃尔朗损失公式（M/M/c/c） . . 107 3.7 无穷服务员排队模型（M/M/∞） . . 110 3.8 有限源排队模型. 111 3.9 状态相依服务. . . 118 3.10 有不耐烦顾客的排队模型. . . 123 3.10.1 M/M/1 止步.123 3.10.2 M/M/1 中途退出. 124 3.11 瞬态行为. . . 125 3.11.1 M/M/1/1 排队模型的瞬态行为. 125 3.11.2 M/M/1/∞ 排队模型的瞬态行为127 3.11.3 M/M/∞ 排队模型的瞬态行为. . 130 3.12 忙期分析. . . 130 习题. .132 第4章 高级马尔可夫排队模型. . 148 4.1 批量到达排队模型（M[X]/M/1） . . . 148 4.2 批量服务排队模型（M/M[Y ]/1） . . . 154 4.2.1 部分批量服务排队模型. . . 155 4.2.2 完全批量服务排队模型. . . 156 4.3 埃尔朗排队模型. 159 4.3.1 埃尔朗分布. 160 4.3.2 阶段型分布. 162 4.3.3 埃尔朗服务排队模型（M/Ek/1） . . 166 4.3.4 埃尔朗到达排队模型（Ek/M/1） . . 170 4.3.5 Ej /Ek/1 排队模型. . .173 4.4 具有优先级的排队模型. . 175 4.4.1 具有两个优先级的非抢占排队模型. .177 4.4.2 具有多个优先级的非抢占排队模型. .184 4.4.3 具有优先级的抢占排队模型. . . 192 4.4.4 排队的公平性. . . 193 4.5 重试排队模型. . . 197 4.5.1 M/M/1 重试排队模型. . . 198 4.5.2 有不耐烦顾客的M/M/1 重试排队模型. 202 4.5.3 M/M/c 重试排队模型的近似求解方法. .208 习题. .211 第5章 排队网络：串联网络和循环网络. 218 5.1 串联网络219 5.1.1 节点输出. . . 220 5.1.2 有阻塞的串联网络. . . 224 5.2 杰克逊开网络. . . 226 5.3 杰克逊闭网络. . . 235 5.4 循环网络251 5.5 杰克逊网络的扩展. . . 252 5.6 非杰克逊网络. . . 255 习题. .256 第6章 一般到达时间间隔分布和一般服务时间分布. .263 6.1 一般服务时间分布、单服务员（M/G/1） . . . 263 6.1.1 效益指标：PK 公式. .263 6.1.2 离开时刻系统大小概率. . . 269 6.1.3 证明πn = pn . . . 276 6.1.4 遍历理论. . . 277 6.1.5 等待时间. . . 280 6.1.6 忙期分析. . . 284 6.1.7 系统容量有限的排队模型（M/G/1/K） 286 6.1.8 一些补充结果. . . 288 6.1.9 批量到达排队模型（M[X]/G/1） . . 289 6.1.10 离开时刻状态相依、分解及服务员休假. 292 6.1.11 水平穿越法296 6.2 一般服务时间分布、多服务员（M/G/c/· 及M/G/∞） . 300 6.2.1 M/G/c/∞ 排队模型. 301 6.2.2 M/G/∞ 和M/G/c/c 排队模型. . . 302 6.3 一般到达时间间隔分布（G/M/1 及G/M/c） . . . 305 6.3.1 G/M/1 排队模型. . . .306 6.3.2 G/M/c 排队模型311 习题. .317 第7章 一般排队模型与理论研究323 7.1 G/Ek/1、G[k]/M/1 及G/PHk/1 排队模型. 323 7.1.1 矩阵几何解. 326 7.1.2 拟生灭过程. 329 7.2 G/G/1 排队模型330 7.2.1 GEj/GEk/1 排队模型. . . 337 7.2.2 G/G/1 离散时间排队模型341 7.3 M/D/c 排队模型. . . 342 7.4 半马尔可夫过程与马尔可夫更新过程.344 7.5 其他排队规则. . . 349 7.6 排队系统的设计与控制. . 355 7.6.1 设计问题. . . 357 7.6.2 控制问题. . . 362 7.7 统计推断366 习题. .375 第8章 界与近似解. 378 8.1 界. . .378 8.1.1 单服务员排队模型的基本关系. 378 8.1.2 单服务员排队模型的界. . . 381 8.1.3 多服务员排队模型的界. . . 391 8.2 近似393 8.2.1 用界来近似. 394 8.2.2 系统近似. . . 396 8.2.3 过程近似. . . 397 8.3 确定性流体排队模型408 8.3.1 一般关系. . . 410 8.3.2 基本模型. . . 411 8.3.3 重新审视道路模型. . . 414 8.3.4 串联队列. . . 416 8.4 网络近似417 8.4.1 基本假设和表示符号. 418 8.4.2 参数分解. . . 419 8.4.3 多服务员. . . 427 习题. .428 第9章 数值方法与仿真方法433 9.1 数值方法433 9.1.1 稳态解. 433 9.1.2 瞬态解. 442 9.2 数值逆变换. .450 9.2.1 傅里叶级数方法. 452 9.2.2 误差分析. . . 456 9.2.3 示例. . . 458 9.2.4 其他数值求逆方法. . . 462 9.3 离散事件随机仿真. . . 464 9.3.1 仿真模型的组成. 465 9.3.2 输入建模与随机数生成. . . 467 9.3.3 记录. . . 481 9.3.4 输出分析. . . 482 9.3.5 模型验证. . . 487 习题. .488 附录A 符号及缩写. .492 附录B 模型与分布. . 499 附录C 变换和母函数. . . 504 C.1 拉普拉斯变换. . . 504 C.2 母函数. .510 附录D 微分方程和差分方程515 D.1 常微分方程. 515 D.1.1 分类. . 515 D.1.2 求解. . 516 D.1.3 分离变量法517 D.1.4 一阶线性微分方程. . 519 D.1.5 常系数线性微分方程520 D.1.6 待定系数法524 D.1.7 微分算子法525 D.1.8 降低阶数. . 527 D.1.9 线性微分方程组529 D.1.10 总结. 532 D.2 差分方程. . . 532 D.2.1 常系数线性差分方程533 D.2.2 线性差分方程组535 附录E QtsPlus 软件. . . 537 参考文献. .540