出版者的話
譯者序
序言
前言
致謝
第一部分　排隊(duì)論簡介
第1章　分析建模的功能及實(shí)例2
　1.1　什么是排隊(duì)論2
　1.2　排隊(duì)論實(shí)例3
第2章　排隊(duì)論術(shù)語8
　2.1　我們將去向何方8
　2.2　單服務(wù)器網(wǎng)絡(luò)8
　2.3　排隊(duì)網(wǎng)絡(luò)的分類9
　2.4　開放網(wǎng)絡(luò)10
　2.5　更多指標(biāo)：吞吐量和利用率10
　2.6　封閉網(wǎng)絡(luò)12
　　2.6.1　交互式（終端驅(qū)動）系統(tǒng)13
　　2.6.2　批處理系統(tǒng)14
　　2.6.3　封閉系統(tǒng)中的吞吐量14
　2.7　封閉網(wǎng)絡(luò)和開放網(wǎng)絡(luò)之間的差異15
　2.8　閱讀材料16
　2.9　習(xí)題16
第二部分　必要的概率背景知識
第3章　概率知識復(fù)習(xí)18
　3.1　樣本空間和事件18
　3.2　事件定義的概率18
　3.3　事件的條件概率19
　3.4　獨(dú)立事件和有條件獨(dú)立事件20
　3.5　總概率定律21
　3.6　貝葉斯定律22
　3.7　離散隨機(jī)變量與連續(xù)隨機(jī)變量22
　3.8　概率和密度23
　　3.8.1　離散：概率質(zhì)量函數(shù)23
　　3.8.2　連續(xù)：概率密度函數(shù)25
　3.9　期望和方差27
　3.10　聯(lián)合概率和獨(dú)立性29
　3.11　條件概率和期望30
　3.12　基于條件化的概率和期望34
　3.13　期望的線性性質(zhì)35
　3.14　正態(tài)分布36
　　3.14.1　線性變換特性37
　　3.14.2　中心極限定理39
　3.15　隨機(jī)變量的隨機(jī)數(shù)的和40
　3.16　習(xí)題41
第4章　生成用于模擬的隨機(jī)變量45
　4.1　逆變換方法45
　　4.1.1　連續(xù)情況45
　　4.1.2　離散情況46
　4.2　接受拒絕方法47
　　4.2.1　離散情況47
　　4.2.2　連續(xù)情況48
　　4.2.3　一些更難的問題50
　4.3　閱讀材料50
　4.4　習(xí)題50
第5章　樣本路徑、收斂和均值52
　5.1　收斂52
　5.2　強(qiáng)/弱大數(shù)定律55
　5.3　時(shí)間均值與整體均值56
　　5.3.1　動機(jī)56
　　5.3.2　定義57
　　5.3.3　解釋57
　　5.3.4　等價(jià)性58
　　5.3.5　模擬59
　　5.3.6　系統(tǒng)時(shí)間均值60
　5.4　閱讀材料60
　5.5　習(xí)題60
第三部分　簡單運(yùn)籌定律的預(yù)測能力：“假設(shè)”問題和答案
第6章　Little定律和其他運(yùn)籌定律62
　6.1　開放系統(tǒng)的Little定律62
　6.2　直覺62
　6.3　封閉系統(tǒng)的Little定律63
　6.4　開放系統(tǒng)的Little定律證明63
　　6.4.1　基于時(shí)間均值的陳述64
　　6.4.2　證明64
　　6.4.3　推論65
　6.5　封閉系統(tǒng)的Little定律證明66
　　6.5.1　基于時(shí)間均值的陳述66
　　6.5.2　證明66
　6.6　廣義的Little定律67
　6.7　應(yīng)用Little定律的示例67
　6.8　更多運(yùn)籌定律：強(qiáng)制流定律69
　6.9　運(yùn)籌定律組合70
　6.10　設(shè)備需求72
　6.11　與Little定律相關(guān)的閱讀和其他主題73
　6.12　習(xí)題73
第7章　修改分析：封閉系統(tǒng)的“假設(shè)”75
　7.1　回顧75
　7.2　封閉系統(tǒng)的漸近界限76
　7.3　封閉系統(tǒng)的修改分析78
　7.4　更多修改分析示例78
　7.5　封閉網(wǎng)絡(luò)和開放網(wǎng)絡(luò)的比較80
　7.6　閱讀材料81
　7.7　習(xí)題81
第四部分　從馬爾可夫鏈到簡單隊(duì)列
第8章　離散時(shí)間馬爾可夫鏈84
　8.1　離散時(shí)間與連續(xù)時(shí)間馬爾可夫鏈84
　8.2　DTMC的定義85
　8.3　有限狀態(tài)DTMC的示例85
　　8.3.1　維修設(shè)施問題85
　　8.3.2　雨傘問題86
　　8.3.3　程序分析問題86
　8.4　P的冪：n步轉(zhuǎn)移概率87
　8.5　平穩(wěn)方程88
　8.6　平穩(wěn)分布等于極限分布89
　8.7　求解平穩(wěn)方程的示例90
　　8.7.1　維修設(shè)施成本問題90
　　8.7.2　雨傘問題91
　8.8　無限狀態(tài)DTMC91
　8.9　無限狀態(tài)平穩(wěn)性結(jié)果91
　8.10　求解無限狀態(tài)DTMC中的平穩(wěn)方程93
　8.11　習(xí)題95
第9章　遍歷性理論97
　9.1　遍歷性問題97
　9.2　有限狀態(tài)DTMC98
　　9.2.1　極限分布的存在98
　　9.2.2　訪問狀態(tài)之間的平均時(shí)間101
　　9.2.3　時(shí)間均值102
　9.3　無限狀態(tài)馬爾可夫鏈102
　　9.3.1　常返與瞬時(shí)103
　　9.3.2　無限隨機(jī)游走示例106
　　9.3.3　正常返與零常返108
　9.4　馬爾可夫鏈的遍歷定理109
　9.5　時(shí)間均值110
　9.6　極限概率解釋為速率112
　9.7　時(shí)間可逆性定理113
　9.8　當(dāng)鏈?zhǔn)侵芷谛缘幕蛘卟豢杉s的114
　　9.8.1　周期鏈115
　　9.8.2　不可約的鏈119
　9.9　結(jié)論119
　*9.10　馬爾可夫鏈的遍歷定理的證明119
　9.11　習(xí)題124*
第10章　真實(shí)世界的示例：Google、Aloha和Harder Chains129
　10.1　Google的PageRank算法129
　　10.1.1　Google的DTMC算法129
　　10.1.2　真實(shí)網(wǎng)絡(luò)圖的問題131
　　10.1.3　死角和蜘蛛陷阱問題的Google解決方案131
　　10.1.4　PageRank算法的評估132
　　10.1.5　實(shí)際實(shí)現(xiàn)的注意事項(xiàng)132
　10.2　Aloha協(xié)議分析132
　　10.2.1　Slotted Aloha協(xié)議133
　　10.2.2　Aloha馬爾可夫鏈133
　　10.2.3　Aloha馬爾可夫鏈的性質(zhì)134
　　10.2.4　改進(jìn)Aloha協(xié)議135
　10.3　Aloha為更難的馬爾可夫鏈生成函數(shù)136
　　10.3.1　z變換136
　　10.3.2　求解鏈136
　10.4　閱讀材料138
　10.5　習(xí)題138
第11章　指數(shù)分布和泊松過程141
　11.1　指數(shù)分布的定義141
　11.2　指數(shù)的無記憶特性142
　11.3　通過δ-步將指數(shù)與幾何相關(guān)聯(lián)143
　11.4　指數(shù)的更多屬性144
　11.5　著名的泊松過程146
　11.6　合并獨(dú)立泊松過程149
　11.7　泊松分裂149
　11.8　均勻性151
　11.9　習(xí)題152
第12章　轉(zhuǎn)換到連續(xù)時(shí)間馬爾可夫鏈154
　12.1　定義CTMC154
　12.2　解決CTMC問題157
　12.3　泛化和解釋159
　　12.3.1　解釋CTMC的平衡方程160
　　12.3.2　CTMC的概要定理160
　12.4　習(xí)題160
第13章　M/M/1和PASTA161
　13.1　M/M/1隊(duì)列161
　13.2　使用M/M/1隊(duì)列的示例163
　13.3　PASTA164
　13.4　進(jìn)一步閱讀166
　13.5　習(xí)題166
第五部分　服務(wù)器機(jī)群與網(wǎng)絡(luò)：多服務(wù)器和多隊(duì)列系統(tǒng)
第14章　服務(wù)器機(jī)群：M/M/k與M/M/k/k排隊(duì)系統(tǒng)173
　14.1　連續(xù)時(shí)間馬爾可夫鏈的時(shí)間可逆性173
　14.2　M/M/k/k損失系統(tǒng)174
　14.3　M/M/k176
　14.4　三種服務(wù)器組織模式的比較180
　14.5　閱讀材料181
　14.6　習(xí)題181
第15章　服務(wù)器機(jī)群的容量規(guī)劃184
　15.1　在M/M/k中，負(fù)載的真正含義是什么184
　15.2　M/M/∞185
　　15.2.1　M/M/∞分析185
　　15.2.2　M/M/k容量規(guī)劃的首次削減規(guī)則186
　15.3　平方根配置187
　15.4　閱讀材料189
　15.5　習(xí)題189
第16章　時(shí)間可逆性和Burke定理193
　16.1　有限狀態(tài)CTMC的更多示例193
　　16.1.1　緩沖空間有限的網(wǎng)絡(luò)193
　　16.1.2　M/M/2 I/O的批處理系統(tǒng)194
　16.2　反向鏈195
　16.3　Burke定理198
　16.4　Burke定理的另一種(部分)證明198
　16.5　應(yīng)用：串聯(lián)式服務(wù)器199
　16.6　具有概率路由的一般非循環(huán)網(wǎng)絡(luò)200
　16.7　閱讀材料201
　16.8　習(xí)題201
第17章　隊(duì)列網(wǎng)絡(luò)和Jackson乘積形式203
　17.1　Jackson網(wǎng)絡(luò)的定義203
　17.2　到達(dá)每個(gè)服務(wù)器的過程204
　17.3　解決Jackson網(wǎng)絡(luò)205
　17.4　本地平衡法205
　17.5　閱讀材料209
　17.6　習(xí)題209
第18章　分類隊(duì)列網(wǎng)絡(luò)212
　18.1　概述212
　18.2　分類網(wǎng)絡(luò)的動機(jī)212
　18.3　分類Jackson網(wǎng)絡(luò)的符號和建模214
　18.4　單服務(wù)器分類網(wǎng)絡(luò)215
　18.5　乘積形式定理216
　18.6　分類網(wǎng)絡(luò)示例220
　　18.6.1　面向連接的ATM網(wǎng)絡(luò)示例220
　　18.6.2　作業(yè)類別分布示例221
　　18.6.3　CPU密集型和I/O密集型作業(yè)示例222
　18.7　閱讀材料224
　18.8　習(xí)題224
第19章　封閉隊(duì)列網(wǎng)絡(luò)226
　19.1　動機(jī)226
　19.2　乘積形式的解227
　　19.2.1　封閉網(wǎng)絡(luò)的局部平衡方程227
　　19.2.2　推導(dǎo)極限概率的示例229
　19.3　均值分析230
　　19.3.1　到達(dá)定理230
　　19.3.2　平均響應(yīng)時(shí)間的迭代推導(dǎo)232
　　19.3.3　MVA示例233
　19.4　閱讀材料234
　19.5　習(xí)題234
第六部分　實(shí)際工作負(fù)載：高可變性和重尾
第20章　尾巴的故事：實(shí)際工作負(fù)載的案例研究239
　20.1　研究生院的故事——過程遷移239
　20.2　UNIX進(jìn)程壽命測量240
　20.3　帕累托分布的性質(zhì)241
　20.4　有界帕累托分布242
　20.5　重尾242
　20.6　活動進(jìn)程遷移的益處243
　20.7　帕累托分布無處不在243
　20.8　習(xí)題244
第21章　相位型分布和矩陣分析方法246
　21.1　用指數(shù)代表一般分布246
　21.2　PH工作負(fù)載的馬爾可夫鏈建模249
　21.3　矩陣分析法251
　21.4　時(shí)變負(fù)載分析252
　　21.4.1　高級別的想法252
　　21.4.2　生成矩陣Q252
　　21.4.3　R求解254
　　21.4.4　尋找π→0254
　　21.4.5　性能指標(biāo)255
　21.5　更復(fù)雜的鏈256
　21.6　閱讀材料和進(jìn)一步的評論258
　21.7　習(xí)題258
第22章　具有分時(shí)服務(wù)器的網(wǎng)絡(luò)261
　22.1　乘積形式網(wǎng)絡(luò)261
　22.2　BCMP結(jié)果261
　　22.2.1　FCFS服務(wù)器的網(wǎng)絡(luò)261
　　22.2.2　PS服務(wù)器的網(wǎng)絡(luò)262
　22.3　M/M/1/PS264
　22.4　M/Cox/1/PS264
　22.5　M/G/1/PS服務(wù)器的串聯(lián)網(wǎng)絡(luò)268
　22.6　具有概率路由的PS服務(wù)器網(wǎng)絡(luò)269
　22.7　閱讀材料270
　22.8　習(xí)題270
第23章　M/G/1隊(duì)列與檢驗(yàn)悖論271
　23.1　檢驗(yàn)悖論271
　23.2　M/G/1隊(duì)列及其分析271
　23.3　更新獎勵理論273
　23.4　申請更新獎勵以獲得預(yù)期的超量收益275
　23.5　回到檢驗(yàn)悖論276
　23.6　回到M/G/1隊(duì)列277
　23.7　習(xí)題278
第24章　服務(wù)器機(jī)群的任務(wù)分配策略280
　24.1　FCFS服務(wù)器機(jī)群的任務(wù)分配281
　24.2　PS服務(wù)器機(jī)群的任務(wù)調(diào)度288
　24.3　最佳服務(wù)器機(jī)群設(shè)計(jì)291
　24.4　閱讀材料和進(jìn)一步跟進(jìn)294
　24.5　習(xí)題296
第25章　變換分析298
　25.1　變換的定義和一些示例298
　25.2　從變換中獲取矩：剝洋蔥300
　25.3　變換的線性性質(zhì)302
　25.4　條件303
　25.5　M/M/1系統(tǒng)中響應(yīng)時(shí)間的分布304
　25.6　結(jié)合拉普拉斯變換和z變換305
　25.7　變換的更多結(jié)果305
　25.8　閱讀材料306
　25.9　習(xí)題306
第26章　M/G/1變換分析309
　26.1　系統(tǒng)中數(shù)字的z變換309
　26.2　系統(tǒng)中時(shí)間的拉普拉斯變換311
　26.3　閱讀材料313
　26.4　習(xí)題313
第27章　功率優(yōu)化應(yīng)用314
　27.1　功率優(yōu)化問題314
　27.2　M/G/1的繁忙時(shí)段分析315
　27.3　M/G/1與設(shè)置成本318
　27.4　比較ON/IDLE與ON/OFF320
　27.5　閱讀材料321
　27.6　習(xí)題321
第七部分　M/G/1中的智能調(diào)度
第28章　性能指標(biāo)327
　28.1　傳統(tǒng)度量標(biāo)準(zhǔn)327
　28.2　單一隊(duì)列的常用度量標(biāo)準(zhǔn)327
　28.3　當(dāng)下流行的度量標(biāo)準(zhǔn)328
　28.4　饑餓/公平指標(biāo)328
　28.5　導(dǎo)出性能指標(biāo)329
　28.6　閱讀材料329
第29章　調(diào)度：非搶占式、非基于規(guī)模的策略330
　29.1　FCFS、LCFS和RANDOM330
　29.2　閱讀材料332
　29.3　習(xí)題332
第30章　調(diào)度：搶占式、非基于規(guī)模的策略333
　30.1　PS333
　　30.1.1　PS的起源333
　　30.1.2　M/G/1/PS系統(tǒng)中的作業(yè)年齡334
　　30.1.3　響應(yīng)時(shí)間作為作業(yè)規(guī)模的函數(shù)335
　　30.1.4　對PS結(jié)果的直覺336
　　30.1.5　理解FCFS的PS結(jié)果的含義337
　30.2　搶占式LCFS338
　30.3　FB調(diào)度339
　30.4　閱讀材料342
　30.5　習(xí)題343
第31章　調(diào)度：非搶占式、基于規(guī)模的策略345
　31.1　優(yōu)先級排隊(duì)345
　31.2　非搶占式優(yōu)先級346
　31.3　最短作業(yè)優(yōu)先348
　31.4　關(guān)于非搶占式策略的問題350
　31.5　習(xí)題350
第32章　調(diào)度：搶占式、基于規(guī)模的策略351
　32.1　動機(jī)351
　32.2　搶占式優(yōu)先級排隊(duì)351
　32.3　搶占式最短作業(yè)優(yōu)先354
　32.4　PSJF的變換分析355
　32.5　習(xí)題357
第33章　調(diào)度：SRPT與公平性358
　33.1　最短剩余處理時(shí)間358
　*33.2　SRPT等待時(shí)間的精確推導(dǎo)360
　33.3　與其他策略的比較361
　　33.3.1　與PSJF的比較361
　　33.3.2　SRPT與FB362
　　33.3.3　所有調(diào)度策略的比較362
　33.4　SRPT的公平性363
　33.5　閱讀材料366
參考文獻(xiàn)367