华为数据通信·基础理论系列
Fundamentals of Queueing Theory （Fifth Edition）
排队论基础
（第5版）
[美]约翰·F.肖特尔（John F. Shortle）
[美]詹姆斯·M.汤普森（James M.Thompson）
[美]唐纳德·格罗斯（Donald Gross）
[美]卡尔·M.哈里斯（Carl M.Harris） 著
闫煦 邓博文 译
人民邮电出版社
北京
图书在版编目（CIP）数据
排队论基础：第5版 / （美）约翰·F.肖特尔（John F. Shortle）等著；闫煦，邓博文译．-- 北京：人民邮电出版社，2022.3
（华为数据通信．基础理论系列）
ISBN 978-7-115-56998-1
Ⅰ．①排… Ⅱ．①约…②闫…③邓… Ⅲ．①排队论—研究 Ⅳ．①O226
中国版本图书馆CIP数据核字（2021）第225709号
版权声明
Fundamentals of Queueing Theory, 5th Edition （9781118943526 / 111894352X） by John F. Shortle, James M. Thompson, Donald Gross and Carl M. Harris
Copyright@2018 John Wiley and Sons, Inc.
All Rights Reserved. Authorized translation from the English language edition published by John Wiley & Sons, Inc. Responsibility for the accuracy of the translation rests solely with Posts &Telecommunication Press Co., Ltd and is not the responsibility of John Wiley & Sons Inc.
No part of this book may be reproduced in any form without the written permission of the original copyright holders, John Wiley & Sons Inc..
本书中文简体字版由John Wiley & Sons Inc公司授权人民邮电出版社有限公司出版，专有版权属于人民邮电出版社有限公司。本书封底贴有Wiley防伪标签，无标签者不得销售。
著 [美]约翰·F.肖特尔（John F. Shortle）
[美]詹姆斯·M.汤普森（James M.Thompson）
[美]唐纳德·格罗斯（Donald Gross）
[美]卡尔·M.哈里斯（Carl M.Harris）
译 闫煦 邓博文
责任编辑 韦毅 杨长青
责任印制 李东 周昇亮
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 https://www.ptpress.com.cn
固安县铭成印刷有限公司印刷
开本：720×1000 1/16
印张：36.5
字数：695千字
2022年3月第1版
2022年3月河北第1次印刷
著作权合同登记号 图字：01-2020-0706号
读者服务热线：（010）81055552 印装质量热线：（010）81055316
反盗版热线：（010）81055315
广告经营许可证：京东市监广登字20170147号
本书介绍了如何分析排队模型的概率性质，以及分析过程中所涉及的统计原理。作者并没有局限于某个特定的应用领域，而是基于计算机科学、工程学、商业和运筹学等多个领域的实践阐述了相关的排队论理论。本书特别介绍了一种数值方法，可以帮助读者理解排队论并对相关数据进行估算，并全面地介绍了简单的和高级的排队模型。
本书扩展了对排队论的定性（非数学）描述，包括对日常生活中排队场景的描述，扩展了对随机过程的介绍，包括泊松过程及马尔可夫链。在介绍理论知识的同时，本书还提供了实际应用的例子，所有习题都已经过国外本科及研究生高等课程的课堂测试，可以帮助读者掌握解决实际排队问题的技巧。各章所介绍的关键概念和公式都是相对独立的，读者可以单独阅读感兴趣的内容。
本书可作为高等院校应用数学、统计学等专业师生的参考书，也可为应用数学、运筹学、工程学和工业工程领域的从业者提供有益参考。
“2020年12月31日，华为CloudEngine数据中心交换机全球销售额突破10亿美元。”
我望向办公室的窗外，一切正沐浴在旭日玫瑰色的红光里。收到这样一则喜讯，倏忽之间我的记忆被拉回到2011年。
那一年，随着数字经济的快速发展，数据中心已经成为人工智能、大数据、云计算和互联网等领域的重要基础设施，数据中心网络不仅成为流量高地，也是技术创新的热点。在带宽、容量、架构、可扩展性、虚拟化等方面，用户对数据中心网络提出了极高的要求。而核心交换机是数据中心网络的中枢，决定了数据中心网络的规模、性能和可扩展性。我们洞察到云计算将成为未来的趋势，云数据中心核心交换机必须具备超大容量、极低时延、可平滑扩容和演进的能力，这些极致的性能指标，远远超出了当时的工程和技术极限，业界也没有先例可循。
作为企业BG的创始CEO，面对市场的压力和技术的挑战，如何平衡总体技术方案的稳定和系统架构的创新，如何保持技术领先又规避不确定性带来的风险，我面临一个极其艰难的抉择：守成还是创新？如果基于成熟产品进行开发，或许可以赢得眼前的几个项目，但我们追求的目标是打造世界顶尖水平的数据中心交换机，做就一定要做到业界最佳，铸就数据中心带宽的“珠峰”。至此，我的内心如拨云见日，豁然开朗。
我们勇于创新，敢于领先，通过系统架构等一系列创新，开始打造业界最领先的旗舰产品。以终为始，秉承着打造全球领先的旗舰产品的决心，我们快速组建研发团队，汇集技术骨干力量进行攻关，数据中心交换机研发项目就此启动。
CloudEngine 12800数据中心交换机的研发过程是极其艰难的。我们突破了芯片架构的限制和背板侧高速串行总线（SerDes）的速率瓶颈，打造了超大容量、超高密度的整机平台；通过风洞试验和仿真等，解决了高密交换机的散热难题；通过热电、热力解耦，突破了复杂的工程瓶颈。
我们首创数据中心交换机正交架构、Cable I/O、先进风道散热等技术，自研超薄碳基导热材料，系统容量、端口密度、单位功耗等多项技术指标均达到国际领先水平，“正交架构+前后风道”成为业界构筑大容量系统架构的主流。我们首创的“超融合以太”技术打破了国外FC（Fiber Channel，光纤通道）存储网络、超算互联IB（InfiniBand）网络的技术封锁；引领业界的AI ECN（Electronic Communication Network，电子通信网络）技术实现了RoCE（RDMA over Converged Ethernet，基于聚合以太网的远程直接存储器访问）网络的实时高性能；PFC（Power Factor Correction，功率因数校正）死锁预防技术更是解决了RoCE大规模组网的可靠性问题。此外，华为在高速连接器、SerDes、高速AD/DA（Analog to Digital/Digital to Analog，模数/数模）转换、大容量转发芯片、400GE光电芯片等多项技术上，全面填补了技术空白，攻克了众多世界级难题。
2012年5月6日，CloudEngine 12800数据中心交换机在北美拉斯维加斯举办的Interop展览会闪亮登场。CloudEngine 12800数据中心交换机闪耀着深海般的蓝色光芒，静谧而又神秘。单框交换容量高达48 Tbit/s，是当时业界最高水平的3倍；单线卡支持8个100GE端口，是当时业界最高水平的4倍。业界同行被这款交换机超高的性能数据所震撼，业界工程师纷纷到华为展台前一探究竟。我第一次感受到设备的LED指示灯闪烁着的优雅节拍，设备运行的声音也变得如清谷幽泉般悦耳。随后在2013年日本东京举办的Interop展览会上，CloudEngine 12800数据中心交换机获得了DCN（Data Center Network，数据中心网络）领域唯一的金奖。
我们并未因为CloudEngine 12800数据中心交换机的成功而停止前进的步伐，我们的数据通信团队继续攻坚克难，不断进步，推出了新一代数据中心交换机——CloudEngine 16800。
华为数据中心交换机获奖无数，设备部署在90多个国家和地区，服务于3800多家客户，2020年发货端口数居全球第一，在金融、能源等领域的大型企业以及科研机构中得到大规模应用，取得了巨大的经济效益和社会效益。
数据中心交换机的成功，仅仅是华为在数据通信领域众多成就的一个缩影。CloudEngine 12800数据中心交换机发布一年多之后，2013年8月8日，华为在北京发布了全球首个以业务和用户体验为中心的敏捷网络架构，以及全球首款S12700敏捷交换机。我们第一次将SDN（Software Defined Network，软件定义网络）理念引入园区网络，提出了业务随行、全网安全协防、IP（InternetProtocol，互联网协议）质量感知以及有线和无线网络深度融合四大创新方案。基于可编程ENP（Ethernet Network Processor，以太网络处理器）灵活的报文处理和流量控制能力，S12700敏捷交换机可以满足企业的定制化业务诉求，助力客户构建弹性可扩展的网络。在面向多媒体及移动化、社交化的时代，传统以技术设备为中心的网络必将改变。
多年来，华为以必胜的信念全身心地投入数据通信技术的研究，业界首款2T路由器平台NetEngine 40E-X8A / X16A、业界首款T级防火墙USG9500、业界首款商用Wi-Fi 6产品AP7060DN……随着这些产品的陆续发布，华为IP产品在勇于创新和追求卓越的道路上昂首前行，持续引领产业发展。
这些成绩的背后，是华为对以客户为中心的核心价值观的深刻践行，是华为在研发创新上的持续投入和厚积薄发，是数据通信产品线几代工程师孜孜不倦的追求，更是整个IP产业迅猛发展的时代缩影。我们清醒地意识到，5G、云计算、人工智能和工业互联网等新基建方兴未艾，这些都对IP网络提出了更高的要求，“尽力而为”的IP网络正面临着“确定性”SLA（Service Level Agreement，服务等级协定）的挑战。这是一次重大的变革，更是一次宝贵的机遇。
我们认为，IP产业的发展需要上下游各个环节的通力合作，开放的生态是IP产业成长的基石。为了让更多人加入到推动IP产业前进的历史进程中来，华为数据通信产品线推出了一系列图书，分享华为在IP产业长期积累的技术、知识、实践经验，以及对未来的思考。我们衷心希望这一系列图书对网络工程师、技术爱好者和企业用户掌握数据通信技术有所帮助。欢迎读者朋友们提出宝贵的意见和建议，与我们一起不断丰富、完善这些图书。
华为公司的愿景与使命是“把数字世界带入每个人、每个家庭、每个组织，构建万物互联的智能世界”。IP网络正是“万物互联”的基础。我们将继续凝聚全人类的智慧和创新能力，以开放包容、协同创新的心态，与各大高校和科研机构紧密合作。希望能有更多的人加入IP产业创新发展活动，让我们种下一份希望、发出一缕光芒、释放一份能量，携手走进万物互联的智能世界。
徐文伟
华为董事、战略研究院院长
2021年12月
20世纪30年代，英国学者李约瑟（Joseph Needham）曾提出这样的疑问：为什么在公元前1世纪到公元15世纪期间，中国文明在获取自然知识并将其应用于人的实际需要方面要比西方文明更有成效？然而，为什么近代科学蓬勃发展没有出现在中国？这就是著名的“李约瑟难题”，也称“李约瑟之问”。对这个“难题”的理解与回答，中外学者见仁见智。有一种观点认为，在人类探索客观世界的漫长历史中，技术发明曾经长期早于科学研究。古代中国的种种技术应用，更多地来自匠人经验知识的工具化，而不是学者科学研究的产物。
近代以来，科学研究的累累硕果带来了技术应用的爆发和社会的进步。力学、热学基础理论的进步，催生了第一次工业革命；电磁学为电力的应用提供了理论依据，开启了电气化时代；香农（Shannon）创立了信息论，为信息与通信产业奠定了理论基础。如今，重视并加强基础研究已经成为一种共识。在攀登信息通信技术高峰的30多年中，华为公司积累了大量成功的工程技术经验。在向顶峰进发的当下，华为深刻认识到自身理论研究的不足，亟待基础理论的突破来指导工程创新，以实现技术持续领先。
“华为数据通信·基础理论系列”正是基于这样的背景策划的。2019年年初，华为公司数据通信领域的专家们从法国驱车前往位于比利时鲁汶的华为欧洲研究院，车窗外下着大雨，专家们在车内热烈讨论数据通信网络的难点问题，不约而同地谈到基础理论突破的困境。由于具有“统计复用”和“网络级方案”的属性，数据通信领域涉及的理论众多，如随机过程与排队论、图论、最优化理论、信息论、控制论等，而与这些理论相关的图书中，适合国内从业者阅读的中文版很少。华为数据通信产品线研发部总裁刘少伟当即表示，我们华为可以牵头，与业界专家一起策划一套丛书，一方面挑选部分经典图书引进翻译，另一方面系统梳理我们自己的研究成果，让从业者及相关专业的高校老师和学生能更系统、更高效地学习理论知识。
在规划丛书选题时，我们考虑到随着通信技术和业务的发展，网络的性能受到了越来越多的关注。在物理层，性能的关键点是提升链路或者Wi-Fi信道的容量，这依赖于摩尔定律和香农定律；网络层主要的功能是选路，通常路径上链路的瓶颈决定了整个业务系统所能实现的最佳性能，所以网络层是用户业务体验的上界，业务性能与系统的瓶颈息息相关；传输层及以上是用户业务体验的下界，通过实时反馈精细调节业务的实际发送，网络性能易受到网络服务质量（如时延、丢包）的影响。因此，从整体网络视角来看，网络性能提升优化是对“业务要求+吞吐率+时延+丢包率”多目标函数求最优解的过程。为此，首期我们策划了《排队论基础》（第5版）（Fundamentals of Queueing Theory, Fifth Edition）、《网络演算：互联网确定性排队系统理论》（Network Calculus: A Theory of Deterministic Queuing Systems for the Internet）和《MIMO-OFDM技术原理》（Technical Principle of MIMO-OFDM）这三本书，前两本介绍与网络服务质量保障相关的理论，后一本介绍与Wi-Fi空口性能研究相关的技术原理。
由美国乔治·华盛顿大学荣誉教授唐纳德·格罗斯（Donald Gross）和美国乔治·梅森大学教授卡尔·M.哈里斯（Carl M. Harris）撰写的《排队论基础》自1974年第1版问世以来，一直是排队论领域的权威指南，被国外多所高校列为排队论、组合优化、运筹管理相关课程的教材，其内容被7000余篇学术论文引用。这本书的作者在将排队论应用于多个现实系统方面有丰富的实践经验，并在40多年中不断丰富和优化图书内容。本次引进翻译的是由美国乔治·梅森大学教授约翰·F.肖特尔（John F. Shortle）、房地美公司架构师詹姆斯·M.汤普森（James M. Thompson）、唐纳德·格罗斯和卡尔·M.哈里斯于2018年更新的第5版。由让-伊夫·勒布代克（Jean-Yves Le Boudec）和帕特里克·蒂兰（Patrick Thiran）撰写的《网络演算：互联网确定性排队系统理论》一书于2002年首次出版，是两位作者在洛桑联邦理工学院从事网络性能分析研究、系统应用时的学术成果。这本书出版多年来，始终作为网络演算研究者的必读书目，也是网络演算学术论文的必引文献。让-伊夫·勒布代克教授的团队在2018年开始进行针对时间敏感网络的时延上界分析，其方法就脱胎于《网络演算：互联网确定性排队系统理论》这本书的代数理论框架。本次引进翻译的是作者于2020年9月更新的最新版本，书中详细的理论介绍和系统分析，对实时调度系统的性能分析和设计具有指导意义。
《MIMO-OFDM技术原理》的作者是华为WLAN LAB以及华为特拉维夫研究中心的专家多伦·埃兹里（Doron Ezri）博士和希米·希洛（Shimi Shilo）。从2007年起，多伦·埃兹里一直在特拉维夫大学教授MIMO-OFDM技术原理的研究生课程，这本书就是基于该课程讲义编写的中文版本。相比其他MIMOOFDM图书，书中除了给出MIMO和OFDM原理的讲解外，作者团队还基于多年的工程研究和实践，精心设计了丰富的例题，并给出了详尽的解答，对实际无线通信系统的设计有较强的指导意义。读者通过对例题的研究，可进一步深入地理解MIMO-OFDM系统的工程约束和解决方案。
数据通信领域以及整个信息通信技术行业的研究最显著的特点之一是实用性强，理论要紧密结合实际场景的真实情况，通过具体问题具体分析，才能做出真正有价值的研究成果。众多学者看到了这一点，走出了象牙塔，将理论用于实践，在实践中丰富理论，并在著书时鲜明地体现了这一特点。本丛书书目的选择也特别注意了这一点。这里我们推荐一些优秀的图书，比如，排队论方面，可以参考美国卡内基·梅隆大学教授莫尔·哈肖尔-巴尔特（Mor Harchol-Balter）的Performance Modeling and Design of Computer Systems: Queueing Theory in Action（中文版《计算机系统的性能建模与设计：排队论实战》已出版）；图论方面，可以参考加拿大滑铁卢大学两位教授约翰·阿德里安·邦迪（John Adrian Bondy）和乌帕鲁里·西瓦·拉马钱德拉·莫蒂（Uppaluri SivaRamachandra Murty）合著的Graph Theory；优化方法理论方面，可以参考美国加州大学圣迭戈分校教授菲利普·E.吉尔（Philip E. Gill）、斯坦福大学教授沃尔特·默里（Walter Murray）和纽约大学教授玛格丽特·H.怀特（MargaretH. Wright）合著的Practical Optimization；网络控制优化方面，推荐波兰华沙理工大学教授米卡尔·皮奥罗（Michal Pioro）和美国密苏里大学堪萨斯分校的德潘卡·梅迪（Deepankar Medhi）合著的Routing, Flow, and Capacity Design in Communication and Computer Networks；数据通信网络设备的算法设计原则和实践方面，则推荐美国加州大学圣迭戈分校教授乔治·瓦尔盖斯（GeorgeVarghese）的Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices；等等。
基础理论研究是一个长期的、难以快速变现的过程，几乎没有哪个基础科学理论的产生是由于我们事先知道了它的重大意义与作用从而努力研究形成的。但是，如果没有基础理论的突破，眼前所有的繁华都将是镜花水月、空中楼阁。在当前的国际形势下，不确定性明显增加，科技对抗持续加剧，为了不受制于人，更为了有助于全面提升我国的科学技术水平，开创未来30年的稳定发展局面，重视基础理论研究迫在眉睫。为此，华为公司将继续加大投入，将每年20%～30%的研发费用用于基础理论研究，以提升通信产业的原始创新能力，真正实现“向下扎到根”。华为公司也愿意与学术界、产业界一起，为实现技术创新和产业创新打好基础。
首期三本书的推出只是“华为数据通信·基础理论系列”的开始，我们也欢迎各位读者不吝赐教，提出宝贵的改进建议，让我们不断完善这套丛书。如有任何建议，请您发送邮件至networkinfo@huawei.com，在此表示衷心的感谢。
随着现代科技的迅猛发展，人们面对的世界充满了极大的复杂性和不确定性。客观世界里有限的资源往往伴随着过多的需求，因而出现了大量由随机因素支配和受其影响的现象。排队论（queueing theory）就是在20世纪初随着电话业务的发展，由丹麦工程师A.K.埃尔朗（A.K. Erlang）在1909年考虑电话线路与人工服务的合理配置问题时创立的。类似的问题在生产线管理、交通运输调度、医疗卫生保健管理、武器装备后勤管理等领域也大量存在，因此排队论也被称为随机服务系统理论，它被公认为研究系统随机聚散现象和随机服务系统工作过程及优化控制的基础理论。
20世纪50年代初，经过第二次世界大战的洗礼，运筹学（operations research）应运而生。在运筹学发展的前20年里，排队论的贡献是深远的。一批著名学者，如英国的肯德尔（Kendall）、林德利（Lindley）、史密斯（Smith）、考克斯（Cox）和洛因斯（Loynes）在排队论领域做出了里程碑式的工作。匈牙利学者塔卡奇（Takacs）的两部著作（1962, 1967）利用变换及组合数学的方法给出了各种排队系统的瞬态和稳态行为的刻画，影响深远。20世纪50年代后期和60年代又有一些重要的排队论专著（Morse, 1958；Syski, 1960；Saaty, 1961；Benes, 1963；Prabhu, 1965；Feller, 1957, 1966；Cohen, 1969）出版，构建了排队论的理论大厦。20世纪70年代后期，随着互联网和计算机网络的快速增长，网络拥塞和数据冲突引起人们的密切关注。克兰罗克（Kleinrock）两卷排队论著作（1975, 1976）介绍了当时极为前沿的计算机网络应用问题研究。诺伊斯（Neuts）在著作（1981, 1989）中引入了矩阵几何解析理论和计算概率方法，适用于计算机大规模计算高维度排队问题，极大地推进了排队论的发展，至今仍方兴未艾。
我国对排队论的研究始于20世纪50年代。在中国科学院数学研究所越民义、吴方、韩继业、徐光煇等先生的努力下，我国对排队系统瞬时性态的研究取得了系列创新成果，得到了国际同行的好评。当时的应用研究聚焦于工业中的纺织与矿山两大领域、国防中的卫星信息处理优化管理等。改革开放后，徐光煇、曹晋华、汪荣鑫、董泽清等先生带头培养了一大批高校与科研院所从事排队论与相关领域工作的学者，他们成为当前国内排队论研究的主力军。
笔者有幸于20多年前在中国科学院应用数学研究所曹晋华先生的指导下进行排队论、可靠性、随机库存理论等随机优化理论方面的研究。当时遍览排队论的教材，恰逢唐纳德·格罗斯和卡尔·M.哈里斯的《排队论基础》（第3版）出版（1998年），如获至宝，日夜揣摩，受益匪浅。当时笔者研究兴趣是重试排队（retrial queues），历经10年，这个研究课题的成果被收入《排队论基础》（第4版，2008年出版），可以说我是和这部教材一起成长的。再经10年，《排队论基础》（第5版）面世（英文版于2018年出版）。十年磨一剑，磨砺日久，终成经典。
读博时奢望国内有类似AT&T、贝尔实验室这样的研究机构提供学以致用的机会，20多年后华为技术有限公司勇于创新，在此领域展开基础研究。在《排队论基础》（第5版）中文译本的问世之际，我受邀作序，荣幸之至。国泰民安，科技发轫，华为技术有限公司组织专家翻译的《排队论基础》（第5版），笔者有幸先睹为快。
《排队论基础》（第5版）对前一版本进行了全面的修订和扩充，反映了该领域的最新发展。它延续了前4版内容翔实、循序渐进、结构严谨等优点，给出了分析排队系统概率性质所必需的基本统计方法，介绍了排队论中重要的基本概念，以及这些概念在计算机科学、工程学、商业和运筹学等不同领域的应用。读者可以使用本书中介绍的数值方法来更好地理解排队系统，并对其相关指标进行估算。此外，书中还新增了关于非平稳型流体排队的章节，介绍了通过流体逼近来处理非平稳型队列的基本方法。附录讨论了数学变换、母函数，以及微分方程和差分方程。这本书囊括了近一个世纪排队理论与实践的主要思想、模型和发展。笔者认为，对于国内学习排队论的各位师生，这本书作为排队论初级教程，当是不二之选。
当今排队论的应用随处可见。学者对于大规模复杂的排队系统，发展出了新的理论，如重话务理论、多类排队网络、流体模型与系统稳定性、哈芬-惠特重排（Halfin-Whitt regime）、有效带宽、大偏差理论、重尾分布尾部概率估计、渐进性分析、基于服务质量的排队控制、基于博弈论的排队经济学等，都是排队论后续的高阶理论，正在各个应用领域发挥着重要的作用，相信本书的读者会走进一个精彩绝伦的排队炫世界。我相信此中文译本的出版一定会使国内相关领域的学生和学者获益匪浅，特此推荐。
是为序。
王金亭
中央财经大学管理科学与工程学院副院长、教授
在我们的生活中，排队是很常见的现象：上下班高峰期拥挤的地铁站，“双十一”堵在路上久久不到的快递包裹，以及总是抢购不到的新上市手机，背后都是排队拥塞。为了缓解排队拥塞，人们也想出了很多种办法，比如地铁站外使用折回围杆疏导，“双十一”各快递公司高薪聘请快递员加快配送等。排队论就是用来揭示我们生活以及自然界中无处不在的排队现象背后数学规律的学科，是数学领域运筹学的分支。
排队论最早是1909年丹麦数学家A.K.埃尔朗为了研究电话网络场景而提出的。在当前的数据通信网络领域中，排队论也发挥着重要作用。比如2020年，面对突如其来的新冠肺炎疫情，远程办公、在线视频、在线教育等网络流量井喷，网络上路由器和交换机在高负载下时延变大、丢包严重，全球在线视频服务质量严重下降，这背后的原理就可用排队论来描述，通过排队论也可以找到更合适的优化方案。再比如，在线游戏玩家都有过这样的经历，当我们在家里用Wi-Fi玩游戏时，如果家里有人同时使用该Wi-Fi观看或下载视频，那么游戏效果会变差，但其实如果能基于排队论理论优化网络设备调度器设计，智能化地合理配置网络资源，就能更好地满足各种不同业务的服务质量（quality of service, QoS）需要。除此之外，在数据通信网络中，对于设备缓存大小选择、设备组网接口带宽大小选择、业务端到端时延优化、芯片和软件中各种任务调度和队列调度优化等问题，排队论都能给予很好的理论和实践指导。
自1974年的第1版问世以来，本书的英文版一直是排队论领域的权威指南，难能可贵的是，作者40多年来基于众多学生及工程师的实践意见持续不断丰富和优化内容，每10年左右迭代一个新版本，分别在1985年、1998年、2008年和2018年更新。任何一部数学理论类图书在能够再版3次以上，就堪称经典教材了。当前呈现在各位读者面前的是2018年第5版的中译本。本书的第1章主要介绍排队论的基础知识，如排队系统的特征和效益指标。第2章对排队中常见的随机过程理论进行了回顾，帮助读者快速了解一些重要概念。第3、4章分别讨论生灭类型和非生灭类型的马尔可夫模型。排队网络，包括串联和循环网络等，是排队论中的重要概念，第5章介绍了相关内容。第6章讨论到达时间间隔或服务时间服从一般分布的模型。第7章讨论更一般的排队模型。以上各章均是通过解析方法对模型进行分析，然而对于许多排队系统，不能直接得到其效益指标的解析解。因此，第8章讨论如何求效益指标的上下界或近似解。除近似方法外，第9章介绍如何使用数值方法和仿真方法来对排队系统进行分析。
本书每一章末尾均有习题，读者可以通过练习巩固本章的知识点。原书作者并没有局限于某个特定的领域，而是基于计算机科学、运筹学、应用数学等多个领域的实践阐述了相关的排队理论；无论是对于高校学生，还是相关领域的从业者，本书均具有极高的参考价值。
翻译本书的缘起，是华为数据通信领域几位技术专家驱车前往华为比利时鲁汶研究所的路上，车窗外下着大雨，车内专家们热烈讨论数据通信网络难点问题，有专家提到，数据通信网络是一个统计复用的系统，拥塞、排队、调度是很自然的问题，需要从排队论、网络演算等基础理论中找到更优化的解决方法，而这些基础理论的经典图书，国内一直没有中译本。数据通信产品线研发总裁刘少伟当即表示，华为数据通信产品线应该牵头翻译几本经典理论图书，让从业者及相关专业的高校老师和学生可以更系统地学习网络基础理论。
于是，“华为数据通信·基础理论系列”第一批图书的筛选和翻译工作顺利展开。希望本书与该系列另外两本基础理论译著——《网络演算：互联网确定性排队系统理论》和《MIMO-OFDM技术原理》能为从业人员的问题研究和实践做一些微小的贡献。我们也希望这只是开始，各行各业能有更多专家加入编写和翻译的队伍，出版更多、更好的基础理论图书。我们欣喜地看到，卡内基·梅隆大学莫尔·哈肖尔-巴尔特教授的《计算机系统的性能建模与设计：排队论实战》也已经由北京工业大学方娟、蔡旻、张佳玥等学者翻译完成并出版上市。
本书从开始翻译到出版，历时一年有余。由于本书的专业性非常强，译者为提高自己的知识储备，在启动翻译前参阅了业界诸多图书及论文。翻译过程中，逐字斟酌，力求忠于原文；遇到晦涩难懂的表达或知识点，译者通过查阅论文或咨询专家等方式，反复推敲，直至能完全理解。对于术语，译者更是逐一予以查证，并选用业界最为常用的说法。翻译工作初步完成后，译者对译稿反复回读修改数遍有余，并交由资深专家进行审校。在翻译和校对的过程中，译者也对原书中存在的错误进行了更正。
本书的翻译和出版是多人共同努力的成果。本书由华为翻译中心闫煦和邓博文负责翻译，由华为数据通信研究部多位技术专家参与技术审校，其中宋健审校了第1、6章，杨文斌审校了第2、7章，郑德高审校了第3、4章，白宇审校了第5章，我们还特邀中央财经大学王金亭教授审校了第8、9章。
在本书的翻译过程中，很多专家提出了中肯的建议和鼓励，特别感谢华为数据通信研究部专家宋健、中央财经大学王金亭教授提供细致、专业的审阅意见；特别感谢华为数据通信数字化信息和内容体验部姚成霞全程协调本书出版的各项工作并指导跟踪本书的翻译；特别感谢教授级高级工程师闫建新阅读全书后给出的宝贵意见。
要感谢的还有华为的各位领导、专家和同事，感谢刘少伟、常悦、钱骁、金闽伟、王焘涛、解明震、孟文君、朱正宏、汪洋、谭金芳、马红霞、张威武、王小忠，感谢你们在本书翻译和出版过程中给予的帮助和支撑。
由于时间仓促，本书的错误在所难免，有不当之处请读者批评指正。有任何建议，请发送邮件至networkinfo@huawei.com，在此表示衷心感谢。
1974年，由唐纳德·格罗斯和卡尔·M.哈里斯合著的《排队论基础》（第1版）成功出版。随后，该著作大约每隔10年便重新修订和发布一版。2005年，受唐纳德·格罗斯的邀请，我们有幸参与该著作新版本的修订。相对于第4版，第5版纳入了广大师生和同事的真知灼见。第5版几乎保留了第4版的全部内容，但对其进行了大量改编和信息重组，同时也添加了部分新章节。希望这些修订如前几版一样，能够帮助丰富该书的内容。
在第5版中，我们将第4版的第1章拆分为独立的两章。新的第1章总体介绍了排队论，新的第2章则大体描述了随机过程。在第1章中，我们将利特尔法则（Little's law）一节进行了扩展，加入了大量例子、几何证明，同时增加了利特尔法则的分布形式以及H=λG公式，从而使内容更加丰富、严谨。除此之外，我们还在第1章加入了关于等待心理学的新的一节。
针对第2章介绍的随机过程的内容，我们在第4版的基础上进行了大量的改写和信息重组。通过这些改写，信息更加清晰，可以让熟悉随机过程的读者轻松决定阅读时是否要跳过这一章。对于不太熟悉随机过程的读者，改写后的内容通篇更加简洁明了、言简意赅。
我们对高级马尔可夫排队模型的相关内容（即现在的第4章）也进行了大量修改，其中增加了关于排队的公平性的一节以及处理器共享的内容。与此同时，我们也针对界和近似解的内容（即现在的第8章）进行了修改，加入了有关流体队列的新内容。全书增加了20多个新例题和60多个新习题。
约翰·F.肖特尔
詹姆斯·M.汤普森
2017年10月于美国弗吉尼亚州费尔法克斯
很荣幸能够参与《排队论基础》这本书第4版和第5版的修订和改写，同时感谢原作者唐纳德·格罗斯和卡尔·M.哈里斯在撰写前3版时所做的大量工作。站在巨人的肩膀上，我们希望这两版的修改能对图书内容的丰富有所助益。
感谢同事和学生给我们提供的帮助，他们的广泛意见和建议对我们后续修订图书有很大的帮助。衷心感谢所有人，特别感谢家人们一如既往的鼓励和支持，感谢约翰威立出版公司（John Wiley & Sons）所有人的倾力支持。
同时感谢美国乔治·梅森大学沃尔格诺工程学院和系统工程与运作管理系的大力支持。
约翰·F.肖特尔
詹姆斯·M.汤普森
我们都经受过不得不排队的烦恼，排队现象在拥挤的、城市化的、高科技的社会中普遍存在。我们在堵车时坐在汽车里等待或在收费站前排队等待；在拨打电话时会等待客服接通我们的电话；在超市、快餐店结账时排队；在银行、邮局里排队等候服务。顾客不喜欢排队，而服务场所的管理者也不希望顾客排队，因为这可能会导致顾客流失，影响他们的生意。既然这样，为什么还会有排队这一现象呢？
答案很简单，这是因为顾客对服务的需求大于服务场所对服务的供给。具体来说，有许多原因，如服务员的数量不足（对企业来说，雇用足够多的服务员来避免排队现象的发生并不经济）、可提供的服务受空间限制等。一般来说，投入更多的资本可以在一定程度上消除这些限制。为了解面对排队现象服务场所应该提供多少服务，我们需要回答一些问题，例如：顾客需要等待多长时间？等待队列中将会有多少顾客？本书所研究的排队论就是通过详细的数学过程来分析并回答这些问题的。值得一提的是，在很多场合下，排队论已成功地解决了相关问题。
排队论最早研究的问题是电话流量拥塞问题。丹麦数学家埃尔朗是这一研究领域的先驱，他在1909年发表了论文《概率论和电话通信理论》。在后来的研究中，他发现电话系统的特征通常为：泊松输入、指数占用时间（服务时间）和多通道（多服务员）；或泊松输入、定长占用时间和单通道。在埃尔朗之后，学者们对排队论在电话通信领域应用的研究一直在持续进行。1927年，莫利纳（E. C. Molina）发表了论文《概率论在电话中继问题中的应用》。一年后，桑顿·弗莱（Thornton Fry）《概率及其工程应用》一书的出版扩展了埃尔朗早期的大部分研究。在20世纪30年代初，费利克斯·波拉切克（Felix Pollaczek）在泊松输入、任意输出以及单通道、多通道问题上做了进一步的开创性研究。此外，苏联的科尔莫戈罗夫（Kolmogorov）和辛钦（Khintchine）、法国的克罗梅林（Crommelin）和瑞典的巴尔姆（Palm）在当时也做了相应的研究。排队论的研究起步比较缓慢，但在20世纪50年代飞速发展，此后这一领域产生了大量的研究成果。
排队论在许多方面的应用都很有价值，包括流量规划（车辆、飞机、通信）、调度（病人就诊、机器作业、计算机程序）和服务设施设计（银行、邮局、游乐场、快餐店）等。大多数实际问题并不完全对应于某个数学模型，所以人们也越来越关注复杂的计算分析、近似解、仿真和敏感度分析等数学方法。
图1.1展示了一个典型的排队系统：顾客到达，排队等待服务，接受服务，离开系统。部分顾客可能会在接受服务前离开，可能是因为排队等待的时间过长导致他们失去耐心（①）；也可能是因为没有足够的等待空间，顾客在一开始就没有进入服务场所（②）。
请注意，本书中会经常提及“顾客”一词，但“顾客”不一定指人。例如，顾客可以是等待抛光的滚珠轴承、等待起飞的飞机或等待运行的计算机程序。
关于排队系统的效益问题，我们需要了解什么？一般来说，我们需要关注3个系统指标：顾客的等待时间；队列或系统中累积的顾客数；服务员的空闲时间。由于大多数排队系统含有随机元素，因此以上3个指标通常是随机变量，我们将研究这些随机变量的概率分布（或期望值）。
等待时间分为两类：顾客在队列中等待的时间（排队时间），以及顾客在系统中等待的总时间（排队时间与接受服务时间之和）。根据所要研究的系统，我们可能会更关注其中一种类型的等待时间。例如，如果研究的是某个游乐场，我们会更关注顾客在队列中等待的时间，因为顾客会由于排队时间过长而感到不愉快。如果我们研究的是某个机器维修系统，那么总时间（排队时间与维修时间之和）对我们来说更有意义，因为我们希望尽可能减少机器停机的总时间。在本书中，我们用Wq来表示顾客在队列中的平均等待时间，用W来表示顾客在系统中的平均等待时间。
相应地，权衡累积顾客数量也有两个指标：队列中的顾客数和系统中的顾客总数。如果需要确定等待空间的大小（例如，需要确定在理发店的等待区放置多少把椅子），我们将更关注队列中的顾客数；如果需要知道有多少机器无法使用（排队等待维修的机器和正在维修的机器的总和），我们将更关注系统中的顾客总数。我们用Lq来表示队列中的平均顾客数，用L来表示系统中的平均顾客数。此外，有两个空闲时间指标：任一服务员空闲的时间百分比和整个系统中没有顾客的时间百分比。
排队论的研究通常分为以下两方面：对于某个排队过程，确定衡量其效益的指标；根据某些准则设计“最优”系统。对于前者，要根据给定的顾客输入流和服务过程的属性来确定顾客等待时间和队列长度。对于后者，希望根据某种成本结构来平衡顾客的等待时间和服务员的空闲时间。例如，如果可以直接获得顾客等待和服务员空闲的成本，那么可以基于该成本来确定最优的服务员数。为了获得最优的系统设计，可能还需要考虑等待场所的空间成本，而要设计等待场所，就需要知道队列可能会有多长。在任何情况下，都可以首先尝试用解析法来解决问题。如果解析法不可行，可以考虑用仿真的方法。问题通常归结为服务质量（等待时间）和服务成本之间的权衡，增加服务成本可以减少顾客的等待时间。
定量评估排队系统需要对排队过程进行数学表征，多数情况下，可以用以下6个基本特征来描述排队系统：
• 顾客的到达过程；
• 服务员的服务过程；
• 服务员的数量和服务通道的数量；
• 排队规则；
• 系统容量；
• 服务阶段的数量。
后文将介绍用前5个特征来描述排队系统的标准表示法（见第1.2.7节）。
在常见的排队场景中，顾客的到达过程往往是随机的，因此有必要知道描述连续两个顾客到达的时间间隔的概率分布。泊松过程（Poisson process）是一种常见的到达过程，第2.2节将详细介绍泊松过程。如果存在多个顾客同时到达（批量到达）的情况，还需要知道描述批量到达的顾客数的概率分布。
顾客的到达过程可能会随时间而变化。不随时间变化的到达过程（即描述到达过程的概率分布与时间无关）称为平稳到达（stationary arrival），随时间变化的到达过程称为非平稳到达（nonstationary arrival）。餐厅是一个非平稳到达的系统，因为早中晚餐时间到达的顾客数往往比其他时间多。本文中的许多模型都假设到达过程是平稳的。
还有必要知道顾客到达系统时的反应。在某些情况下，无论队列多长，顾客都会排队等待；但在一些情况下，如果队列太长，顾客会决定不排队。如果顾客在到达时决定不排队，则称该顾客止步（balked）；如果顾客决定排队，但过一段时间就失去耐心，决定离开，则称该顾客中途退出（reneged）；如果有两个或多个队列，顾客可能从其中一个换到另一个，则称该顾客换队（jockey）。以上这3种情况都是不耐烦顾客（impatient customer）排队的例子。
前面关于到达过程的讨论大多也适用于服务过程。最重要的是，由于为顾客提供服务的时间通常是随机的，因此需要一个概率分布来描述服务员为顾客服务的时间序列。服务可以是一对一提供的，也可以是批量提供的。通常认为一个服务员一次为一个顾客提供服务，但在许多情况下，一个服务员可以同时为多个顾客提供服务，例如一台计算机并行处理多个操作，一个导游同时带领多个游客，一辆火车同时载有多个乘客。服务过程还可能取决于等待服务的顾客数。如果队列越来越长，服务员可能会加速工作，效率提高，也可能会变得慌乱，效率降低。依赖于等待的顾客数的服务过程称为状态相依服务（state-dependent service）。与到达过程类似，服务过程在时间上可以是平稳的或非平稳的，体现了时间相依性。例如，服务员在服务过程中可能随着经验的积累，服务效率变得越来越高，那么该服务过程就是非平稳的。时间相依性与状态相依性不同。前者取决于系统运行的时间（与系统的状态无关），后者取决于系统中的顾客数（与系统运行的时间无关）。当然，排队系统可以同时是非平稳的和状态相依的。
服务员的数量是排队系统的一个重要特征。企业需要权衡服务员的数量，因为增加服务员会增加企业的成本，但可以大大减少顾客排队的可能。因此，服务员数量的多少通常非常关键。第3.4节将介绍权衡服务员的数量和顾客排队长度的经验法则。
服务通道（排队队列）的配置也同样重要。对于多服务员系统，有几种可能的配置。图1.2展示了两种主要场景。在第一种场景下，多个服务员服务单个队列的顾客，例如，航空公司的行李托运柜台及理发店的等待区（假设没有顾客在等某个特定的发型师）。在第二种场景下，每个服务员只服务自己队列中的顾客，如超市的收银台。混合情况也可能发生，例如，机场排队等待办理登机手续的旅客队列最初可能是一个长队，之后会根据航班检票员的数量把长队分成多个短队。后面会介绍，多服务员排队系统通常最好服务一个队列的顾客，因此，在指定并行服务员数时，通常假设这些服务员服务一个队列的顾客。此外，通常假设服务员彼此独立工作。
排队规则是指当队列形成时，服务员选择顾客进行服务的方式。在日常生活中，最普遍的规则是先到先服务（first come first served, FCFS）。然而，还有许多其他规则：后到先服务（last come first served, LCFS），适用于许多库存系统，因为后到的货物更容易被拿到；随机服务（random selection for service, RSS），服务员从队列中随机选择顾客服务，与顾客到达时间无关；处理器共享（processor sharing, PS），服务员同时服务所有顾客（或并行处理所有任务），但分摊到的顾客（或任务）数越多，处理速度越慢（这在计算机系统中很常见）；轮询（polling），一个服务员为多个队列的顾客提供服务，先服务第一个队列的顾客，然后服务第二个队列的顾客，以此类推（如红绿灯是一种轮询系统）；此外，还有多种优先权方案，部分顾客在接受服务时有优先权。
优先权方案在第4.4节中有更详细的介绍。在这些规则中，优先级较高的顾客将先于优先级较低的顾客接受服务。在优先规则中有两种场景：抢占（preemptive）和非抢占（nonpreemptive）。在非抢占的场景下，具有最高优先级的顾客排在队列的最前面，但要一直等到当前正在接受服务的顾客的服务结束后，才能接受服务，即使正在接受服务的顾客的优先级更低。在抢占的场景下，即使优先级较低的顾客已经在接受服务，也允许优先级较高的顾客在到达时立即接受服务，中断服务员对该低优先级顾客的服务，只有在高优先级顾客接受完服务后，该低优先级顾客才能继续接受服务。这时又有两种情况：该低优先级顾客可以从被抢占的时刻继续接受服务，或者需要重新开始接受服务。
在某些系统中，顾客等待的物理空间受限，因此当队列达到限制长度时，在有可用空间之前，不允许其他顾客进入。这被称为有限排队场景，也就是说，系统大小是有上限的。当等待空间有限且队列长度达到上限时，新到达的顾客将被迫放弃排队。
排队系统可以只有一个服务阶段，也可以有多个服务阶段。例如，体检就是一个多阶段排队系统，每个病人必须经过几个阶段，包括病史问询、耳鼻喉检查、血液检查、心电图检查、眼科检查等。多阶段排队过程作为排队系统的一种特殊情况，在第5.1节中有更详细的介绍。在一些多阶段排队过程中，可能会有反馈（见图1.3）。反馈在制造过程中很常见：系统会在某些阶段之后进行质量检查，不符合质量标准的零件会被送回之前的阶段重新进行加工。类似地，电信网络中，可以通过随机选择的节点序列来处理消息，其中一些消息可能需要在同一阶段进行路由重选。
现代常用的表示法是依据英国数学家肯德尔（Kendall）1953年的研究提出的，该表示法已在排队论文献中作为一种标准使用。排队过程用一组符号和斜线来描述，如A/B/X/Y/Z，其中A表示到达时间间隔分布，B表示服务时间分布，X表示并行的服务员数，Y表示系统容量，Z表示排队规则。表1.1给出了这些特性的一些标准符号（关于文中使用的符号和缩写，另见附录A）。
例如，M/D/2/∞/FCFS表示这样一个排队系统：到达时间间隔服从指数分布，服务时间是定长的，有两个并行的服务员，系统容量无限（即允许进入系统的顾客数没有限制），排队规则是先到先服务。在许多情况下，只使用前3个符号。通常，如果系统容量没有限制（Y=∞[1]），则省略系统容量的符号；如果排队规则是先到先服务（Z=FCFS），则省略排队规则的符号。因此，M/D/2与M/D/2/∞/FCFS表达的含义相同。
表1.1中的符号大多数比较容易理解，下面对部分符号进行解释说明。首先，符号M用于表示指数分布可能看起来很奇怪，你可能希望用符号E，但是，E很容易与Ek混淆，Ek用于表示埃尔朗分布。M体现了指数分布的马尔可夫性（Markovian）或无记忆性（memoryless）（如第2.1节所述）。另外，符号G表示一般概率分布，即没有对分布的确切形式做任何假设，其结果适用于任何概率分布。最后需要说明的是这张表并不完整。例如，其中没有表示批量到达或串联排队的符号。许多情况下，本书介绍某个模型时，会相应地给出这个模型的符号。然而，有些模型没有对应的符号，或者其对应的符号没有被当作标准符号使用，这些模型通常在文献中较少分析。
本节讨论的6个特征足以描述许多常见的排队系统。然而，由于实际中会遇到各种各样的排队系统，因此了解所研究的系统以选择最能描述实际情况的模型是至关重要的。在模型选择过程中往往需要进行大量的思考，而了解这6个基本特征是其中必不可少的一步。
例如，以超市为例，假设有c个收银台。如果顾客完全随机地选择一个收银台（不考虑每个收银台前队列的长度），并且从不换队，那么就是c个独立的单服务员模型。如果所有收银台前只有一个队列，那么就是有c个服务员的单队列模型。当然，大多数超市的情况不是这样。通常情况下，每个收银台前都会排起长队，但刚来到收银台前的顾客会选择进入最短的队列（或者前面的顾客买的东西最少的队列），而且也有很多顾客在队列之间移动。我们需要决定哪种模型更适合描述这个场景。
如果顾客会在不同队列之间移动，使用c个服务员的单队列模型可能更适合，因为等待的顾客总是会移动到空闲的服务员处。因此，当有顾客在等待服务时，没有服务员会处于空闲状态。由于在超市收银台前排队的顾客很容易在队列间移动，因此有c个服务员的单队列模型可能比c个独立的单服务员模型更适合且更符合现实情况。在深入考虑该过程之前，我们可能会想当然地选择c个独立的单服务员模型。
本书主要讨论等待的效益指标，如W、Wq、L和Lq。这一节将简要地对等待进行定性介绍。管理者除了可以通过雇用更多服务员来优化等待的效益指标，也可以通过其他许多方式提升顾客的等待体验。本节总结了迈斯特尔（Maister）在1984年提出的与等待的体验和心理相关的原则。这些原则可以应用到日常的等待体验中，当某次等待的过程比我们预想的更令人恼火时，我们或许会联想到这些原则。迈斯特尔在1984年的论文中总结了以下8条原则。
无所事事的等待比有事可做的等待让人感觉时间长。如果顾客在等待时能保持忙碌，那么他感觉到的等待时间会比实际的等待时间短。例如，餐馆将菜单发给正在等待的顾客，或者邀请顾客到吧台等待，以此来减少顾客感觉到的等待时间。在队列中，顾客分阶段向前移动也会占用等待的时间。例如，为了购买一个三明治，队列中的顾客可能会经历多个阶段：顾客在第一个服务员处下单，在第二个服务员处选择三明治配料，最后在第三个服务员处付款。在队列中渐进式地向前移动会占用等待的时间，从而减少顾客感觉到的等待时间。
过程前的等待比过程中的等待让人感觉时间长。过程前的等待发生在服务开始之前，过程中的等待发生在服务开始之后。例如，当你在餐厅坐下时，如果服务员接待了你并为你先点了饮品，或者服务员对你说“请稍等，我马上就来”，你会觉得服务已经开始了。服务员与顾客的初次接触时间很重要，在此之前的等待可能会让顾客感到不耐烦。
焦虑使顾客感觉到的等待时间比实际时间长。顾客可能会有以下焦虑：是否排错了队，能否赶上飞机，能否赶上下一班班车，班车上会不会太拥挤，是否应该换到另一个速度更快的队列。在这些场景中，队列负责人可以通过一些举措减少顾客的焦虑，例如，引导顾客在正确的队列排队，告知顾客他们能赶上飞机，等等。
不确定的等待比已知且有限的等待让人感觉时间长。顾客通常可以通过快速扫视队列长度来预估等待时间。但是，当队列很长或移动缓慢时，顾客很难预估等待时间。此外，当队列是虚拟队列时（如呼叫中心），顾客无法“看到”队列长度，因此也无法预估等待时间。直接告知顾客预估的等待时间可以减少等待的不确定性。然而，这也提高了顾客的期望，如果实际等待时间超过被告知的等待时间，可能会让顾客感到更不耐烦；相反，如果过高地预估了等待时间，可能会让一些顾客直接放弃排队，而这部分顾客本来可以接受实际的等待时间。
没有说明理由的等待比说明了理由的等待让人感觉时间长。如果顾客知道等待的原因，尤其是当他们认为该原因合理的时候（例如，雷雨天气导致航班延误），顾客会更有耐心。当意外事件发生时，向顾客解释原因会让顾客更有耐心。然而，一般性的解释（例如，“目前我们的电话呼叫量很高”），可能会被顾客认为是不合理的（“呼叫量难道不是一直很高吗？”）。
不公平的等待比公平的等待让人感觉时间长。公平的原则之一是，早到的顾客应在晚到的顾客之前开始接受服务（先到先服务）。不遵循先到先服务原则的情况可能会被视为不公平。例如，在超市，可能会有多个收银员，每个收银员前都有一个队列。虽然每个队列都遵循先到先服务原则，但整个系统可能并不是这样的。可以设想一下，如果某个队列的移动速度比你所在的队列快，比你晚到的顾客在你之前接受了服务，你有可能会恼火。此外，没有排队的系统也可能是不公平的。例如，在公交车站，乘客不排队，一起往车上挤，但公交车空间有限，部分乘客需要等待下一辆车。然而，留下来等待下一辆车的乘客未必比已上车的乘客晚到达车站。基于优先级的系统（第4.4节）违反了先到先服务原则，这类系统可能被视为是公平的，也可能被视为是不公平的。在急诊室里，需要急救的病人可以在其他病人之前接受服务，这种情况不会被视为是不公平的。在其他系统中，支付额外费用的顾客可以优先接受服务（如游乐场的快速通行队列），这可能被视为是公平的，也可能被视为是不公平的。
服务的价值越高，顾客愿意等待的时间越长。为了获得更长时间的服务（假设服务时间越长，服务的价值越高），顾客可能会容忍更长时间的等待。例如，当在超市购买了大量商品时，与购买单件商品时相比，顾客对长时间排队等待结账的容忍度比购买单件商品时高。由此引出了另一个公平原则：其他条件相同时，服务时间较短的顾客应当比服务时间较长的顾客的等待时间少。这一原则可能会与先到先服务原则冲突。当仅购买了一件商品的顾客在购买了大量商品的顾客之后来到收银台，会发生什么？应不应该让购买商品少的顾客先结账？在餐馆中，是否可以优先为人数少的顾客团体安排座位？第4.4.3节将更详细地讨论这种冲突和公平问题。
一个人等待比许多人一起等待让人感觉时间长。
在排队论和本书中广泛使用的一个基本关系式由利特尔法则（Little's law，也称Little定理）给出。利特尔法则给出了3个基本量之间的关系：顾客到达系统的平均速率λ、单个顾客在系统中花费的平均时间W和系统中顾客的平均数L。这一关系的公式表达为L=λW。给定3个基本量中的两个，可以推算出第三个基本量。例如，观察顾客离开商店的情况（获得λ的估计值），并且询问每个顾客在商店里停留了多长时间（获得W的估计值），那么就可以估算出商店中顾客的平均数L。
利特尔法则的应用非常广泛，它适用于各类系统，也包括非排队系统。在正式介绍利特尔法则之前，我们用下面这个例子来说明该法则的原理。
■ 例1.1
一所小学有6个年级（一年级到六年级），每年有30名新生进入一年级，学生们每年升一个年级，并在完成六年级的学业后毕业。这所学校的学生总数是多少？
我们很容易计算出结果：每年30名新生，所以系统的到达速率λ=30名/年；每名学生在学校学习6年，所以W=6年；根据利特尔法则，可以计算出学生总数为L=λW=180。
这个例子可能会让读者认为利特尔法则是一种“显而易见”的关系。每个年级有30名学生，有6个年级，所以学生总数是180。然而，这一结论隐含了许多假设。例如，这个结论假设所有学生都是每年升1个年级。如果在某个年级，部分学生中途入学或退学怎么办？如果部分学生跳级或留级怎么办？如果入学人数逐年随机变化怎么办？如果入学人数随着时间的推移而缓慢增加怎么办？
为了进一步分析上述问题，我们用数学语言给出利特尔法则的精确描述。假定有一个系统（见图1.4），设A(k)为顾客k（顾客编号）进入系统的时间，A(k)是有序的，所以A(k+1)≥A(k)；设A(t)为时刻t前累计到达系统的顾客数；设W(k)为顾客k在系统中花费的时间，顾客在到达前不能离开，因此W(k)≥0；设N(t)是时刻t系统中的顾客数。那么∀t≥0，满足A(k)≤t且A(k)+W(k)≥t的k的个数与N(t)的值相等。当极限存在时，极限定义如下：
极限λ是长期平均到达速率，极限W是每个顾客在系统中花费的长期平均时间，极限L是系统中的长期平均顾客数。
定理1.1（利特尔法则）如果式（1.1）中的极限λ和W存在并且是有限的，则存在极限L，且
证明过程可以在诸如斯蒂达姆（Stidham, 1974）和沃尔夫（Wolff, 2011）等的论文中找到；惠特的论文（Whitt, 1991）证明了定理1.1的一个小的变形。对系统的随机过程进行不同的假设也可以证明定理1.1。在1961年利特尔（Little）的原始证明中，排队过程是严格平稳的，布鲁梅尔（Brumelle, 1971a）的证明过程也是基于同样的假设。其他版本的证明过程要求当系统被清空且重启时，有再生节点存在，例如，朱厄尔（Jewell, 1967）的证明。利特尔在一篇回顾性文章（Little, 2011）中给出了定理1.1在有限时间内的一些变形。
在给出例子之前，需要对利特尔法则进行一些一般性的解释说明。
第一，定理1.1用于计算长期平均值，即式（1.1）中的L、λ和W都被定义为无穷极限，本书中的许多结果也都是基于长期无穷平均值而得到的（可以从利特尔法则的推导过程中获得必要的关系式）。
第二，定理1.1要求λ和W有极限存在，这就排除了当时间无限增长时系统的指标无界的情况。这种情况发生在顾客到达速率超过最大服务速率的不稳定排队系统中，其队列长度会随着时间的推移而不受限制地增长（同理，排队时间也会不受限制地增长）。
第三，严格来说，定理1.1没有要求必须存在一个“队列”，但要求存在一个“系统”，顾客可以到达和离开该系统。该系统可以被视为一个黑盒，除了必须满足前面所述的限制外，定理1.1对黑盒内发生的事情没有特定的要求。例如，定理1.1没有要求顾客必须按照到达系统的顺序离开系统。此外，定理1.1没有要求系统必须满足泊松到达、指数型服务或先到先服务原则（本书中常见的假设）。定理1.1的关键要求是顾客必须在到达后才能离开（即W(k)≥0）。根据系统的定义，从利特尔法则中可以推导出多种关系，如例1.2。因此，利特尔法则被看作一个原理，而不是一个固定的方程。特别是对于一个给定的排队系统，系统定义不同，L、λ和W可能具有不同的含义。
■ 例1.2
图1.5展示了利特尔法则的一个常见表示。该系统包含一个队列和一个服务员，为本书中“系统”的典型设定。根据定义，L为系统中顾客总数的平均值，包括正在排队的顾客数和正在接受服务的顾客数。W为顾客从到达系统到离开系统所花费的总时间（排队时间与接受服务时间的总和）的平均值。因此，根据利特尔法则，可以得到L=λW。
图1.5展示的系统仅包含了一个队列和一个服务员，系统中有多个服务员或多个队列时，利特尔法则依然成立。
■ 例1.3
本例将“系统”视为单个队列（见图1.6）。根据利特尔法则，得到
Lq=λWq
其中，Lq表示队列中顾客的平均数，Wq表示顾客在队列中花费的平均时间。顾客到达队列的速率与到达整个系统的速率相同（以λ表示）。
■ 例1.4
本例将“系统”视为单个服务员（见图1.7）。在这种情况下，L表示正在接受服务的平均顾客数。由于只有一个服务员（假设一个服务员一次只能服务一个顾客），则正在接受服务的平均顾客数L=0·p0+1·(1-p0)=1-p0，其中p0表示系统空闲的时间占比。W表示顾客接受服务所花费的平均时间，也可以用E[S]来表示，其中S为随机服务时间。假设有一个稳定的队列（即顾客离开队列的长期平均速率与他们进入队列的长期平均速率相同），顾客到达服务员处的速率为λ。此时，“L=λW”变形为
这种关系是在非常一般的条件下推导出来的。特别是，式（1.2）不需要本书中用到的许多常见假设，例如泊松到达、指数型服务或先到先服务原则。然而，使用该等式的前提条件是系统中仅有一个服务员（如果有多个服务员，正在接受服务的平均顾客数将不再是1-p0，因为1-p0仅在单个服务员的场景下成立）。
■ 例1.5
本例考虑了一个阻塞队列（见图1.8）。阻塞发生在容量有限的系统中。假定到达的顾客发现系统已满，顾客将不进入系统就直接离开。这类模型在通信领域很常见，服务提供商处理电话呼入的能力有限（例子见第3.5节和第3.6节）。假设有比例为pb的顾客被阻塞而没有进入系统，则顾客进入系统的速率为(1-pb)λ。此时，根据利特尔法则，得出
L=(1-pb)λW
在本例中，需要关注W的含义。由于被阻塞的顾客不进入系统，因此这些顾客花费的时间不计入W的平均值。也就是说，W表示实际进入系统的顾客在系统中花费的平均时间。
本节将给出利特尔法则的一个粗略的几何证明。这不是一个严格的证明，但是可以帮助我们理解利特尔法则的主要思想。完整的证明过程可以在前文提到的参考文献中找到。在本节的几何证明中，假设系统的开始和结束状态都为空，且顾客按照到达系统的顺序离开系统（这一假设条件在后文会放宽）。
设A(t)和D(t)分别表示在时刻t之前累计到达和离开的顾客数。图1.9展示了A(t)（实线）和D(t)（虚线）的样本路径。在时刻t，系统中的顾客数为A(t)-D(t)，因此当A(t)=D(t)时，系统为空。在图1.9中，系统的开始和结束状态都为空。另外，在中间某个时间点，系统暂时为空。令N表示时间范围[0，T]内到达的顾客数，在图1.9中，N=6。
因为顾客是按照到达的顺序离开的，所以每个阴影矩形的面积代表某个特定顾客k在系统中花费的时间，即W(k)。所有顾客在系统中花费的总时间为W(1)+W(2)+…+W(N)，即N个阴影矩形的总面积。
此时，可以计算A(t)-D(t)在[0，T]上的积分，即计算所有矩形阴影的总面积：
等式两边同除以T，并在等号右边乘以并除以N，可得
等号左边为A(t)-D(t)的积分对时间取平均值，表示系统中的平均顾客数（即L）。在等号右边，第一项
表示单位时间内到达的顾客数（即λ），第二项为每个顾客在系统中花费的平均时间（即W）。因此，得到
L=λW
请注意，在这里定义L、λ和W为有限时间范围内的平均值，而在定理1.1中，L、λ和W被定义为无穷极限。
在本节中，顾客按到达顺序离开的假设并不是关键点。即使顾客离开的顺序没有规律可言，也可以得出类似的结论，图1.10对此进行了说明。在图1.10中，阴影矩形面积表示每位顾客在系统中花费的时间，这与前述一致。不同的是，顾客乱序离开：顾客2首先离开，然后顾客1离开，紧接着顾客5、6、4和3依次离开。此时，D(t)（虚线）与阴影矩形的边缘不重合。
然而，在虚线之外的每个阴影区域都正好对应于A(t)和D(t)之间一个面积相等的空白区域。例如，W(1)中超过D(t)的部分可以平移到其上方的空白区域，如图中的箭头所示。类似地，W(3)和W(4)中超过D(t)的部分也可以平移到其上方的空白区域（需要对阴影矩形进行切割和重新排列）。
综上所述，即使顾客乱序离开，顾客在系统中花费的总时间（即阴影矩形的总面积W(1)+W(2)+…+W(N)）等于A(t)-D(t)在[0，T]上的积分。我们可以这样进行计算的根本原因如下：顾客在系统中等待的每个单位时间正好占系统中顾客总数在时间上积分的一个单位。如果系统的开始和结束状态都为空，则每位顾客在系统中花费的时间都计入[0，T]上的积分中。
如果系统不以空状态结束会发生什么？在这种情况下，至少会有一个矩形W(i)延伸超过T，则阴影矩形的总面积将不等于A(t)-D(t)在[0，T]上的积分。然而，可以合理地设想，当T→∞时，这两者的差值相对于总积分来说是很小的，所以L=λW成立。在定理1.1的假设下，即式（1.1）中的长期平均到达速率的极限λ和系统中顾客花费的平均时间的极限W存在，这种设想是正确的。
L=λW是更一般的关系H=λG的一种特殊情况。在H=λG中，G表示与每位顾客相关的平均成本，H表示系统在单位时间内产生的总的平均成本。
更具体地说，假设顾客k在时刻A(k)到达系统，并在时刻A(k)+W(k)永久离开。设fk(t)表示时刻t与顾客k相关的成本关于时间的加权函数，当t∈/[A(k), A(k)+W(k)]时，fk(t)=0。该加权函数的值可以为负，但规定
。定义了以下量：
G(k)表示与顾客k相关的总成本，H(t)表示系统在时刻t产生的总成本。类似于式（1.1），定义以下极限：
定理1.2 若式(1.4)中的极限λ和G存在并且有限，且当k→∞时，W(k)/A(k)→0，那么H存在，且H=λG。
有关该定理的证明，请参阅参考文献（Wolff, 2011）。要求W(k)/A(k)→0是为了避免离开时刻被拖得离到达时刻越来越远。利特尔法则是该定理的一个特例，在利特尔法则中，当时刻t在区间[A(k), A(k)+W(k)]内时，fk(t)=1。
■ 例1.6
一家公司有两种机器（1型和2型）。机器发生故障后，会被送到修理厂。一台i型机器的修理费用为ci，其中c1=500美元/h, c2=200美元/h。所有机器中，平均每40 h就会有一台机器出现故障。所有故障中，1型和2型机器各占一半。修理一台机器平均需要3 h，不分类型。公司每小时花费在机器故障修理上的平均费用H是多少？
当t∈[A(k), A(k)+W(k)]时，设fk(t) =ci(k)［当t不属于该区间时，fk(t)=0］，其中A(k)是出现第k次故障的时间；W(k)是第k次故障持续的时间；i(k)是第k次出现故障的机器类型，且i(k)∈{1, 2；G(k)是修复第k次故障的费用。因为两种机器出现故障的可能性相同，所以修复机器故障的平均费用为G=3×(500+200)/2=1050（美元/台）。由于
台/h，可得H=(1/40)×1050=26.25（美元/h）。
■ 例1.7
一个游乐场每天有5000个游客，开放时间为上午10点到晚上10点。游乐场里的游乐设施之一是过山车，每位游客每次来游乐场平均坐1.2次过山车，每次坐过山车的平均排队时间为30 min，那么坐过山车的平均排队人数是多少？
设A(k)为游客k到达游乐场的时间，A(k)+W(k)为游客离开游乐场的时间。当游客k在时间t排队坐过山车时，fk(t)=1［其他情况下，fk(t)=0］。G(k)是游客k一天中排队坐过山车的总时间。所有游客的平均排队时间为G=1.2×0.5=0.6（h），因为每个游客平均坐1.2次过山车，每次排队时间为0.5 h。在本例中，“系统”为游乐场，因此，到达速率λ是游客到达游乐场的速率，而不是到达过山车设施的速率，所以
个/h。坐过山车的平均排队人数为H=λG=(5000/12)×0.6=250。本例说明了加权函数可用于处理顾客多次访问子系统的情况。
利特尔法则给出了N(t)≡A(t)-D(t)（在时刻t，系统中的顾客数）的一阶矩和W(k)之间的关系。你可能还想知道是否有可能把N(t)的二阶矩与W(k)联系起来，答案是肯定的。事实上，N(t)的所有高阶矩都可以与W(k)联系起来，这些结果可以从利特尔法则的分布形式得出。然而，与定理1.1所述的利特尔法则的基本形式相比，我们需要基于更严格的假设来得出这些与高阶矩相关的结果。
为了说明利特尔法则的分布形式，考虑这样一个系统，顾客到达、离开该系统，且假设该系统具有以下特性：（1）到达过程是平稳的；（2）顾客按照到达的顺序离开系统；（3）第k个顾客在系统中所花费的时间W(k)是平稳的；(4)W(k)与顾客k到达后的其他顾客的到达过程无关，则有
式（1.5）将系统中顾客数N(t)的分布与在W(k)期间到达的顾客数A(·)的分布联系起来。也就是说，如果随机生成等待时间W(k)和在时间段W(k)内随机到达的顾客数，则该随机的到达顾客数与系统中的顾客数具有相同的分布。参考文献（Haji et al., 1971；Brumelle, 1972；Keilson et al., 1988；Bertsimaset al., 1995；Wolff, 2011）给出了该结果的各种形式。
当到达过程是泊松过程时，会出现一种重要的特殊情况。由式（1.5）可推导出以下关系，即j阶矩之间的关系：
例如，j=2时，二阶矩之间的关系如下：
对于M/G/1排队模型，这些公式可以直接推导出，见第6.1.5节的式（6.30）。
在使用利特尔法则的分布形式时，必须注意假设是否成立。例如M/M/c多服务员排队模型，顾客按到达顺序离开这一假设通常不成立（对于M/D/c排队模型，该假设成立）。这是因为如果有多个服务员，顾客可能会在被服务期间相互超越，为后获得服务的顾客提供的服务可能先完成。但对于一个队列本身，先入先出（first in first out, FIFO）原则是成立的，前提是顾客在队列中保持顺序不变，并且不会发生中途退出的情况（提前离开队列的顾客违反了先入先出原则）。因此，利特尔法则的分布形式不适用于整个M/M/c排队系统（队列和多服务员），它仅适用于队列。
优先级排队系统的情况类似。优先级排队系统违反了先入先出原则，因为后到达的高优先级顾客可以先于先到达的低优先级顾客接受服务，所以利特尔法则的分布形式不适用于整个优先级排队系统，但可以分别应用于顾客级别相同的队列（前提是满足前面的假设）。例如，在有两个等级的M/G/1优先级排队系统中，利特尔法则的分布形式可以单独应用于低优先级顾客的队列，也可以单独应用于高优先级顾客的队列。
最后，我们注意到，如果到达过程不是更新过程（即顾客到达的时间间隔不独立且分布不相同），则违反了假设（4）。因为到达的时间间隔不是独立的，所以在顾客k到达之前的其他顾客的到达时间和在顾客k到达之后的其他顾客的到达时间之间可能存在依赖关系，这意味着顾客k的等待时间不仅取决于之前其他顾客的到达时间，也可能取决于随后其他顾客的到达时间。在本书中，我们通常假设到达过程是一个更新过程。
后续各章将介绍一些特定模型。在此之前，本节介绍G/G/1和G/G/c排队模型的一些一般结果，这些结果在后续各章中非常有用。
表1.2列出了一些关键符号的含义。设λ表示顾客到达排队系统的平均速率，S表示随机服务时间。每个服务员为顾客提供服务的平均速率µ≡1/E[S]。系统的总负荷用输入负荷（offered load）r≡λ/µ=λE[S]来衡量。由于λ为单位时间内到达的顾客平均数，并且每位顾客需要的平均工作量为E[S]，因此输入负荷λE[S]表示单位时间内系统的工作量。与此密切相关的是，衡量流量拥塞程度的指标为ρ≡λ/cµ，即流量强度（traffic intensity）或服务员利用率（serverutilization）。流量强度等于输入负荷除以服务员的数量，表示单位时间内每个服务员的平均工作量。
设Tq表示某个（处于稳态的）顾客在接受服务前在队列中等待的随机时间，T表示顾客在系统中花费的随机时间。因此，T=Tq+S，其中S为随机服务时间。顾客在队列中的平均等待时间Wq和顾客在系统中花费的平均时间W是衡量系统效益的两个常用指标，即
Wq≡E[Tq]，且W≡E[T]
设Nq表示稳态下队列中的顾客数（随机变量），N表示稳态下系统中的顾客数（随机变量）。与之相关的两个指标为队列中的平均顾客数Lq和系统中的平均顾客数L。设pn=Pr{N=n}表示系统中存在n个顾客的稳态概率。那么对于有c个服务员的系统，L和Lq可以表示如下：
使用利特尔法则（第1.4节），可以得到效益指标L、Lq、W和Wq之间的关系（见图1.11）。具体地说，应用于系统的利特尔法则给出L=λW（例1.2），应用于队列的利特尔法则给出Lq=λWq（例1.3）。另外，由于T=Tq+S（一位顾客在系统中花费的时间等于在队列中花费的时间加上在服务中花费的时间），因此基于期望值得出
W=Wq+1/µ
接着，可以基于这几个关系式，得出L和Lq之间的关系：
在后面各章中，将重点对4个效益指标之一进行推导。最初的推导可能比较困难，但是一旦推导出4个效益指标中的一个，就可以依据图1.11轻松地推导出其他3个效益指标。
对于单个服务员系统(c=1)，式（1.7）具有特定形式：
当c=1时，r=ρ，因此得到
ρ=1-p0或p0=1-ρ
也就是说，对于单个服务员系统，系统为空的时间占比为1-ρ（在例1.4中，通过对服务员系统应用利特尔法则，也可以直接得到这种关系）。这些结果汇总在表1.3中。
输入负荷r定义为平均到达速率λ和平均服务速率µ的比值。式（1.7）表明，r也可以被解释为预期的正在接受服务的顾客数或忙碌的服务员的平均数量（因为r=L-Lq，即系统中的顾客数减去队列中的顾客数就是正在接受服务的顾客数）[2]。输入负荷表示满足特定流量所需的最少服务员数。例如，如果顾客以λ=12个/h的速率到达，并且每个顾客所需的平均服务时间为E[S]=0.5h，则该系统至少需要6个服务员才能不发生拥塞。
类似地，流量强度ρ≡λ/cµ可以解释为每个服务员都处于忙碌状态的时间占比。由于在任何时刻都处于稳态且忙碌的服务员的预期数量为r，并且一共有c个服务员，因此每个服务员都处于忙碌状态的时间占比为r/c=ρ，其中假设服务员的对称性——顾客对任何一个服务员都没有偏好。
可以证明，要使稳态存在，就必须有ρ<1或λ<cµ。也就是说，顾客进入系统的平均速率必须严格小于系统的最大平均服务速率。当ρ>1时，顾客到达的平均速率大于接受服务的平均速率，随着时间的流逝，队列变得越来越长。因为队列长度一直在增长，所以没有稳态。当ρ=1时，顾客的到达速率恰好等于最大服务率。在这种情况下，除非顾客的到达时间和服务时间固定且进行了合理的安排（例如，所有顾客均每隔1 min到达队列，且每个顾客均需要1 min的服务时间），否则将不会有稳态。综上，如果知道平均到达速率和平均服务速率，则可以找到满足ρ=λ/cµ<1的c的最小值，即保证稳态所需的并行服务员数的最小值。
在现实中，队列长度不可能没有边界地一直增长。无边界队列是建模假设的结果，即假设所有到达的顾客都会加入队列并在接受服务之前一直留在系统中。实际上，当λ>cµ且队列变得非常长时，有几个因素有助于稳定队列：顾客可能因为队列太长而选择不排队（止步），队列中的顾客可能会变得不耐烦并选择离开队列（中途退出），顾客可能由于空间限制而无法加入队列（阻塞）。第3.10节将讨论这些情景。
本节使用基于事件的记录方式来说明到达和服务的随机事件是如何相互关联从而形成队列的。在记录过程中，需要关注事件发生时系统状态的更新、相关项目的记录及效益指标的计算。基于事件的记录方式只在事件发生时（例如，顾客到达或离开时）更新系统状态。主时钟的值每次都可能增加不同的量（这与基于时间的记录方式不同，在基于时间的记录中，无论何时发生事件，主时钟的值在每一步骤都会增加某个固定的量）。
表1.4中给出的到达和服务的数据举例说明了基于事件的记录方式，这些数据记录了顾客到达排队系统的时间以及每个顾客的服务时间。根据这些数据可以确定队列是如何形成的，假设该排队系统只有一个服务员且排队规则为先到先服务。
为了进行分析，我们定义了与每个顾客相关的多个变量，如表1.5所示。变量A(n)和S(n)是输入变量，其余的变量可以通过这两个输入变量导出。表1.5中还给出了变量之间的各种关系，例如，顾客离开系统的时间是顾客开始接受服务的时间加上顾客的服务时间。有一个重要的关系，U(n+1)=max{D(n), A(n+1)}，它表示当第n个顾客离开时，第n+1个顾客开始接受服务；当然，第n+1个顾客不能在自己到达之前开始接受服务，因此U(n+1)在两个变量中取最大值。这一关系式仅针对单个服务员且排队规则为先到先服务的排队系统。表1.5中的其他关系式适用于更一般的情况。
为了计算排队等待时间，我们观察到任何满足先到先服务规则的单服务员排队模型中两个相继到达的顾客的等待时间Wq(n)和Wq(n+1)都有以下的递归关系：
式（1.8）被称为林德利方程（Lindley's equation），该方程是一个重要的一般关系式，会在后文中使用到。我们可以通过图1.12来理解该方程。该方程表明，一个顾客的排队时间等于前一个到达的顾客的排队时间加上前一个顾客的服务时间，再减去两个顾客到达时间的间隔（图1.12中的场景1）；然而，如果这两个顾客到达的时间间隔较长，等式中的第一个值可能为负（图中的场景2），因此，在式（1.8）中，通过取两个值中的最大值来确保Wq(n+1)永不为负。
林德利方程也可以通过表1.5中的关系得到
根据表1.5中的关系，表1.6展示了基于表1.4中的输入数据而得出的记录结果。在电子表格中输入每个变量的计算公式，并在每一列下拉复制对应的公式，可得到表1.6中各个变量的值。利用林德利方程，通过S(n)和T(n)的值可以得出Wq(n)的值，因此没有必要记录所有变量的值。
接下来将介绍如何计算效益指标。可以通过计算表1.6中Wq(n)和W(n)列的平均值来得到Wq和W的样本平均值，即Wq=29/12，W=56/12。为了计算L和Lq，必须先定义计算样本平均值的时间范围。由于最后一位顾客在时间点29离开，可以定义时间范围为[0, 29]。在该时间段内，系统以空状态开始和结束，在这种情况下，可以基于利特尔法则得到L、λ和W样本值之间的关系（参见图1.9和相关讨论）。该时间段内的样本到达速率λ=12/29。因此，
或者，可以直接用N(t)在时间上的平均值来确定L的值，N(t)是时刻t系统中的顾客数。假设系统在空状态下启动（略早于t=0），把N(t)写作
图1.13展示了N(t)的样本路径。在每个顾客的到达时间，N(t)的值增加1，在每个顾客的离开时间，N(t)的值减少1。系统中顾客数在时间上的平均值为
其中，N(t)=1有10个时间单位，N(t)=2有9个时间单位，以此类推，可得N(t)在时间上的平均值。类似地，也可以通过Nq(t)在时间上的平均值来确定Lq的样本平均值，其中Nq(t)=max{N(t)-1, 0}。
请注意，记录方法是基于数据样本路径的观察结果来实现的。由于结果是直接从数据中推导出来的，因此无论到达间隔或服务时间所基于的概率公式是什么，都不需要为这些概率公式做任何假设。
如今，电子表格是工程师和运筹学研究专家不可或缺的工具。有几篇参考文献（Bodyal, 1986；Leon et al., 1996；Grossman, 1999）讨论了电子表格在各种运筹学分支中的应用，如最优化和排队论。为了便于学习，本书提供了一组实现排队模型的电子表格，统称为QtsPlus。本书中分析的大部分模型都可以用QtsPlus实现。有关QtsPlus的运行说明，请参阅附录E。
我们用一个涉及马尔可夫链平稳分布的例子（见下一章的例2.6）来说明如何使用QtsPlus。按照附录E中的说明启动软件，成功启动软件后，从列表中选择“Basic”模型类别，然后从可用列表中选择“Discrete-Time Markov Chain”模型。打开模型工作簿（marchain.xlsm）后，在“Number of States”处中输入“2”。此时可能会弹出消息框，并显示如下消息：
“This will cause existing model parameters to be discarded. Do you wishto continue?”（该操作会导致现有模型参数丢失，是否继续？）
点击“Yes”来设置新的矩阵P。使用Excel公式，用初始参数填充工作表中矩阵P的各个元素，如下所示：
=3/5 =2/5
=1/5 =4/5
点击“Solve”按钮，答案出现在工作表的左侧（如图1.14所示），与第2.3.2节中得出的结果一致。
1.1 根据第1.2节中给出的特征讨论下列排队场景。
（a）在机场降落的飞机。
（b）超市结账过程。
（c）邮局或银行服务窗口。
（d）桥梁或公路上的收费站。
（e）有若干个加油机的加油站。
（f）自动洗车设施。
（g）打入客服中心的电话。
（h）有预约的病人进入医生办公室就诊。
（i）希望在导游带领下参观景点的游客。
（j）装配流水线上的电子部件，装配流水线包括3项操作和1项检查。
（k）在中央计算机上对来自局域网上若干独立源的程序进行处理。
1.2 给出3个排队的例子（习题1.1中所列场景除外），根据第1.2节中给出的特征讨论这3种排队场景。
1.3 印度一家快餐店想要确定提供多少并行的服务通道。他们估计，在就餐高峰期，平均每小时有40人到达，一般情况下，一个服务通道服务一个顾客平均需要5.5 min。根据现有信息，建议开通多少个服务通道？
1.4 一家小型的本地航空公司设有顾客服务呼叫中心。他们想知道提供多少来电等待席位最合适。他们计划雇用足够多的客服，这样在一天中最繁忙的时间段内，来电者的平均等待时间将不超过75 s。他们估计在这段时间内，平均每分钟打入3个电话。你有什么建议？
1.5 一家烧烤店仅有外卖业务。在订单高峰期，有两个服务员在值班，老板注意到，在这段时间内，服务员几乎没有空闲。老板估计每个服务员的空闲时间百分比为1%。理想情况下，空闲时间的百分比为10%时，服务员才有足够的休息时间。
（a）如果老板决定在这段时间内增加一个服务员，那么每个服务员有多少空闲时间？
（b）假设增加了一个服务员后，服务员的压力减小了，并且他们可以更仔细地工作，但是他们的服务输出率降低了20%。那么，服务员的空闲时间百分比是多少？
（c）假设老板决定雇用一名助手（其工资比服务员低很多）来协助两个服务员（而不是雇用一个全职服务员），两个服务员的平均服务时间因此减少20%（相对于原来的服务时间）。现在这两个服务员的空闲时间百分比是多少？
1.6 冻酸奶摊在炎热夏季的夜晚生意火爆，即便如此，在任何时候都只有一个服务员值班。服务时间（包括制作酸奶和收钱的时间）服从正态分布，期望为2.5 min，标准差为0.5 min（尽管正态分布允许有负值，但相对于期望，标准差很小，负值比期望低4个标准差以上，有负值的概率基本为0）。你在某个晚上到这个冻酸奶摊来买你最喜欢的松脆巧克力酸奶蛋卷，发现前面有8个人。请估算你买到酸奶蛋卷前的等待时间。你等待超过0.5 h的可能性有多大？（提示：正态随机变量之和也服从正态分布。）
1.7 一个足球联赛有32支球队，每队有67名现役队员，球队每年都通过一场选拔赛来选拔新球员，每支球队每年选拔7名新球员。每队的现役队员人数必须始终是67，因此，每个球队每年必须裁减一些现役球员，为新球员腾出位置。
（a）假设一名足球运动员只能通过选拔加入一个队，请估算他在联赛中的平均职业生涯长度。
（b）现在假设球员可以通过以下两种方式之一加入一个球队：➀在选拔赛中被选中；➁不通过选拔，直接与球队签约。假设足球运动员的平均职业生涯为3.5年，请估算联赛中每年不通过选拔入队的球员的平均人数。
1.8 表1.7给出了某大学本科生的入学统计数据。根据这些数据，请估算一个本科生在该校就读的平均时间长度（本题应该考虑到正常毕业的学生以及转入或退学的学生）。
1.9 假设你要卖房子。经观察，在任何一个特定的时间，你所在的地区通常有50套左右的房子在出售，新房以每周5套左右的速度上市。你的房子大概要多久才能卖出？为了得到答案，你做了哪些假设？
1.10 假设M/G/1/K排队模型的队列阻塞概率为pK=0.1，其中λ=µ=1，L=5。求W、Wq和p0。
1.11 假设生产一剂疫苗需要3美元，一剂疫苗生产出来后，保质期为90天，过期不能再使用。生产商希望在任何给定的时间，都能有平均3亿剂疫苗可用。
（a）执行该计划每年的费用是多少？
（b）假设疫苗的保质期满足埃尔朗分布，平均值为90天，标准差为30天。执行这个计划每年的费用是多少？
（c）假设可以生产保质期更长的疫苗，但成本更高。研究发现，生产保质期为x天的疫苗的成本为a+bx2，其中a=2.5美元，b=0.000 05美元。生产保质期为多少天的疫苗可以使每年的成本最低？
1.12 购买了某品牌笔记本电脑的顾客可以致电顾客支持中心寻求技术帮助。电话接通后先由普通客服接听，如果普通客服无法处理该问题，则会将电话转接给专家，平均20%的电话转接给了专家，该系统如图1.15所示。平均而言，有40个顾客正在接受或正在等待普通客服的服务，有10个顾客正在接受或正在等待专家的服务。平均每小时有100个来电，顾客支持中心有30名普通客服和10名专家。
（a）任意顾客在系统中平均花费的时间是多少？请说明你为回答这个问题所做的假设。
（b）需要专家服务的顾客在系统中平均花费的时间是多少？
1.13 考虑以下非常简化的社会保障模式。每年有300万人年满65岁，年满65岁的人开始领取社会保障金，每人每年4万美元。不考虑其他因素，每个65岁以上的人每年有5%的死亡概率。
（a）一个人可以领取社会保障金的平均时间是多久？
（b）社会保障金的年平均支出总额是多少？
1.14 飞机按照泊松过程到达圆形空域，每小时有20架飞机到达该区域，该区域的半径是40 km，每架飞机以400 km/h的速度飞行。如图1.16所示，该区域有4个可能的入口/出口A、B、C、D。飞机从A、B、C、D点到达和离开的可能性是一样的（但飞机不能从同一点进出）。例如，飞机到达A点的概率为1/4，由于是从A点到达的，其从B、C或D点离开的概率均为1/3。假设飞机的飞行路径是直线，并且在该区域内不会发生碰撞且没有为避免相撞而产生的飞行。
（a）一架飞机在该区域的平均飞行路径长度是多少？
（b）该区域内的平均飞机数量是多少？
（c）假设飞机有时会为避免相撞而执行躲避机动，那么（b）的答案是增加还是减少？
1.15 在购买新车之前，美国一个人使用一辆车的平均时间为5年，并且服从三阶埃尔朗分布。假设美国大约有1.5亿辆汽车。
（a）假设美国人将在购买新车时毁掉旧车。汽车行业每年预计销售多少辆汽车？
（b）假设美国人在购买新车时会将旧车卖给其他人。购买二手车的人使用二手车的平均时间为7年，并且服从三阶埃尔朗分布；当购买二手车的人购买下一辆二手车时，手头这辆二手车将被毁掉。汽车行业每年预计销售多少辆新车？
1.16 飞机进入如图1.17所示的区域，该区域长为50 km，进入该区域的飞机的间距为5 km加上平均值为1 km的指数分布随机变量。假设飞机始终以400 km/h的速度飞行，该区域的平均飞机数量是多少？
1.17 表1.8给出了关于满足先到先服务规则的单服务员排队模型中的顾客的观察结果。
（a）计算顾客在队列中的平均等待时间和在系统中的平均时间。
（b）计算必须等待服务的顾客在系统中的平均等待时间（即不包括到达系统后立即接受服务的顾客）。计算队列的平均长度、系统中的平均顾客数和服务员空闲时间的比例。
1.18 某检查站的初始状态为空，物品以每5 min一个的速度到达该检查站，第一个物品的到达时间设置为第5分钟，前10个物品检查完成的时间分别为第7分钟、第17分钟、第23分钟、第29分钟、第35分钟、第38分钟、第39分钟、第44分钟、第46分钟和第60分钟。请利用这些数据，模拟运行该检查站从第0到第60分钟的过程，计算该检查站中的平均物品数和检查站空闲时间百分比。
1.19 表1.9列出了满足先到先服务规则的单服务员排队模型中顾客的到达时间和服务时间。根据这些数据，计算Lq（队列中的平均顾客数）和Lq(A)（新到达的顾客观察到的已在队列中的平均顾客数）。对于Lq，假设时间范围为[0, 15.27]，其中15.27是最后一个顾客离开系统的时间。假设t=0时系统为空。
[1]本书中∞表示正无穷，-∞表示负无穷。
[2]该解释对G/G/c排队模型有效。对于有阻塞的模型，例如M/M/c/K排队模型，若假设系统中有无穷多的服务员，则输入负荷可以解释为正在接受服务的平均顾客数。
