Power grids, flexible manufacturing, cellular communications: interconnectedness has consequences. This remarkable book gives the tools and philosophy you need to build network models detailed enough to capture essential dynamics but simple enough to expose the structure of effective control solutions and to clarify analysis. Core chapters assume only exposure to stochastic processes and linear algebra at the undergraduate level; later chapters are for advanced graduate students and researchers/practitioners. This gradual development bridges classical theory with the state-of-the-art. The workload model that is the basis of traditional analysis of the single queue becomes a foundation for workload relaxations used in the treatment of complex networks. Lyapunov functions and dynamic programming equations lead to the celebrated MaxWeight policy along with many generalizations. Other topics include methods for synthesizing hedging and safety stocks, stability theory for networks, and techniques for accelerated simulation. Examples and figures throughout make ideas concrete. Solutions to end-of-chapter exercises available on a companion website.
Author(s): Sean Meyn
Edition: 1
Year: 2007
Language: English
Pages: 582
Half-title......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 7
List of Illustrations......Page 11
Preface......Page 15
Acknowledgments......Page 17
Dedication......Page 19
1 Introduction......Page 23
1.1.1 Flexible manufacturing......Page 24
1.1.2 The Internet......Page 25
1.1.4 Power distribution......Page 26
1.2.1 A range of probabilistic models......Page 29
1.2.2 What is a good model?......Page 31
1.3.1 Linear programs......Page 32
1.3.2 Some probability theory......Page 33
1.3.3 Random walks......Page 34
1.3.4 Renewal processes......Page 36
1.3.5 Martingales......Page 37
1.3.6 Markov models......Page 40
1.4 Notes......Page 43
Part I: Modeling and Control......Page 45
2.1 Modeling the single server queue......Page 47
2.1.1 Sampling......Page 49
2.1.3 Heavy traffic and Brownian models......Page 50
2.1.4 Transient behavior and fluid models......Page 52
2.2 Klimov model......Page 53
2.4 Multiple-access communication......Page 56
2.5 Processor sharing model......Page 58
2.7 Power transmission network......Page 59
2.8 Optimization in a simple re-entrant line......Page 61
2.9 Contention for resources and instability......Page 65
2.10 Routing model......Page 68
2.11 Braess' paradox......Page 71
2.12 Notes......Page 72
3 The Single Server Queue......Page 74
3.1.1 Lindley recursion......Page 77
3.1.2 Skorokhod map......Page 78
3.1.3 Loynes construction......Page 79
3.2 Approximations......Page 80
3.2.1 Fluid models......Page 81
3.2.2 Heavy traffic and Brownian models......Page 82
3.3.1 Fluid and stochastic Lyapunov functions......Page 84
3.3.2 Consequences of Foster's criterion......Page 85
3.3.3 Stability of the RBM model......Page 87
3.4 Invariance equations......Page 88
3.4.1 The M/M/1 queue......Page 89
3.4.2 Existence of......Page 90
3.4.3 Refined comparison theorems......Page 91
3.4.5 Computation of the discounted cost......Page 94
3.4.6 Invariance equations for the RBM model......Page 96
3.5.1 Time reversal and reversibility......Page 98
3.5.2 Most likely behavior in the general model......Page 100
3.6 Model selection......Page 102
Exercises......Page 104
4 Scheduling......Page 109
4.1 Controlled random-walk model......Page 111
4.1.1 Basic model......Page 112
4.1.2 Policies......Page 115
4.1.3 Optimization......Page 117
4.2 Fluid model......Page 119
4.3 Control techniques for the fluid model......Page 125
4.3.1 Time-optimality......Page 127
4.3.2 Myopic policies......Page 128
4.3.3 Balancing long- and short-term costs......Page 130
4.4 Comparing fluid and stochastic models......Page 137
4.4.1 Buffer priority policies......Page 138
4.4.2 Myopic policies......Page 140
4.5 Structure of optimal policies......Page 141
4.6 Safety-stocks......Page 144
4.6.1 Static safety-stocks......Page 145
4.6.2 Dynamic safety stocks......Page 148
4.7 Discrete review......Page 150
4.8 MaxWeight and MinDrift......Page 153
4.9 Perturbed value function......Page 156
4.10 Notes......Page 160
Part II: Workload......Page 165
5 Workload and Scheduling......Page 167
5.1.1 Workload in units of time......Page 168
5.1.2 Workload, delay, and Little's law......Page 169
5.2.1 Workload in units of inventory Definition 5.2.1......Page 171
5.2.2 Workload in units of time......Page 173
5.3 Relaxations for the fluid model......Page 175
5.3.1 Minimal process......Page 177
5.3.2 Effective cost......Page 182
5.3.3 Value functions......Page 188
5.3.4 Optimization......Page 191
5.4.1 Relaxations for the CRW model......Page 194
5.4.2 Controlled Brownian model......Page 197
5.5.1 Klimov model......Page 200
5.5.2 Single station re-entrant......Page 203
5.5.3 Workload models......Page 204
5.6.1 Height process......Page 205
5.6.2 Case study: Simple re-entrant line......Page 208
5.7 Notes......Page 214
6 Routing and Resource Pooling......Page 217
6.1 Workload in general models......Page 220
6.2 Resource pooling......Page 226
6.3 Routing and workload......Page 231
6.3.1 Resource pooling and maximal flows......Page 232
6.3.2 Bellman–Ford algorithm......Page 235
6.4.1 MaxWeight and back-pressure routing......Page 237
6.4.2 Simultaneous routing and scheduling......Page 238
6.5 Simultaneous resource possession......Page 240
6.6.1 Relaxations of the fluid model......Page 243
6.6.2 Effective cost......Page 246
6.6.3 Coupling the relaxation......Page 250
6.7 Relaxations and policy synthesis for stochastic models......Page 255
6.7.1 State-space collapse under a myopic policy......Page 256
6.7.2 Coupling mean behavior......Page 257
6.7.3 Hedging for MaxWeight......Page 260
6.8 Notes......Page 262
Exercises......Page 264
7 Demand......Page 268
7.1 Network models......Page 271
7.1.1 Pull to push translation......Page 272
7.1.2 What is workload?......Page 273
7.2.1 GTO policy......Page 277
7.2.2 Hot-lots......Page 283
7.2.3 Unanticipated breakdown......Page 286
7.2.4 Preventative maintenance......Page 287
7.3.1 One-dimensional relaxations......Page 289
7.3.2 Multidimensional relaxations and control......Page 292
7.4 Hedging in a simple inventory model......Page 296
7.4.1 CRW model......Page 297
7.4.2 CBM model......Page 301
7.5.1 One-dimensional relaxation......Page 302
7.5.2 Two-dimensional relaxation......Page 303
7.6 Summary of steady-state control techniques......Page 313
7.7 Notes......Page 314
Exercises......Page 315
Part III: Stability and Performance......Page 317
8 Foster–Lyapunov Techniques......Page 319
8.1.1 Irreducibility......Page 324
8.1.2 Comparison Theorem......Page 325
8.2 Lyapunov functions for networks......Page 327
8.2.1 Irreducibility......Page 328
8.2.2 Value functions......Page 329
8.2.3 Geometric ergodicity......Page 331
8.2.4 Drift vector field......Page 332
8.2.4.1 Foster’s criterion......Page 333
8.3.1 Markovian realizations......Page 337
8.3.2 Stability of DR policies......Page 338
8.4.1 Roadmap......Page 341
8.4.2 Perturbed linear function......Page 342
8.4.3 Perturbed value function......Page 344
8.5 MaxWeight and the average-cost optimality equation......Page 347
8.6 Linear programs......Page 350
8.6.1 Linear test for stability......Page 351
8.6.2 The Drift and Performance LPs......Page 354
8.6.3 Duality......Page 357
8.7.1 The extended generator......Page 358
8.7.2 Linear programs......Page 361
8.8 Notes......Page 364
Exercises......Page 365
9 Optimization......Page 370
9.1 Reachability and decomposibility......Page 374
9.2 Linear programming formulations......Page 376
9.2.1 Linear programming and the Comparison Theorem......Page 378
9.2.2 Convex-analytic and sample-path approaches......Page 379
9.2.3 Duality......Page 383
9.3 Multiobjective optimization......Page 384
9.4.1 Shortest path......Page 387
9.4.2 Discounted cost......Page 389
9.4.3 Average cost......Page 391
9.5.1 Value iteration......Page 397
9.5.2 VIA and shortest path formulations......Page 401
9.5.3 Policy iteration......Page 402
9.6.1 Reachability in networks......Page 403
9.6.2 Optimality equations......Page 404
9.6.3 Monotonicity and irreducibility......Page 406
9.7 One-dimensional inventory model......Page 407
9.8 Hedging and workload......Page 413
9.8.1 Discounted cost......Page 414
9.8.2 Average cost......Page 418
9.9 Notes......Page 424
Exercises......Page 426
10 ODE Methods......Page 429
10.1 Examples......Page 434
10.2.1 Continuity and convergence......Page 438
10.2.2 Laws of large numbers......Page 440
10.3 Fluid limit model......Page 441
10.3.1 Properties......Page 442
10.3.2 Consequences and characterizations......Page 444
10.4.1 ODE criterion for regularity......Page 445
10.4.2 Converse theorems......Page 449
10.5 Safety stocks and trajectory tracking......Page 453
10.6.1 Discounted cost......Page 459
10.6.2 Infinite horizon......Page 463
10.7 Brownian workload model......Page 465
10.7.1 Value functions......Page 466
10.7.2 Regeneration and ergodicity......Page 467
10.8 Notes......Page 470
Exercises......Page 472
11 Simulation and Learning......Page 474
11.1.1 Central Limit Theorem......Page 480
11.1.2 Large deviations......Page 481
11.2.1 Central Limit Theorem......Page 483
11.2.2 Large deviations......Page 485
11.3 The single-server queue......Page 487
11.3.1 Asymptotic variance......Page 488
11.3.2 Large deviations......Page 491
11.4.1 Optimizing shadow functions......Page 492
11.4.3 Shadow functions for the single-server queue......Page 494
11.4.4 Quadratic estimator......Page 496
11.4.5 Fluid estimator......Page 500
11.4.6 Shadow functions and workload......Page 501
11.5 Estimating a value function......Page 505
11.5.1 Stochastic approximation......Page 506
11.5.2 Least-Squares Temporal Difference learning for discounted cost......Page 508
11.5.3 Adjoint equations and TD learning......Page 511
11.5.4 Average cost......Page 514
11.5.5 Optimizing shadow functions......Page 517
11.6 Notes......Page 520
Exercises......Page 521
Appendix: Markov Models......Page 527
Bibliography......Page 559
Index......Page 581
