第1章 绪论 1
1.1 离散事件动态系统 1
离散事件动态系统的研究背景 1
离散事件 2
离散事件动态系统 2
离散事件动态系统示例 3
1.2 离散事件动态系统的建模和分析方法 5
DEDS建模问题的基本性 5
DEDS的建模和分析方法 6
DEDS建模与分析中的困难因素 7
本书的体系结构 8
1.3 本书的论述范围 8
本书的基本内容 9
第2章 性能层次的建模与分析方法之一：排队网络方法 11
2.1 排队网络模型及其特性 11
排队网络 11
排队网络的特性 12
2.2 单一服务中心模型 12
单一服务中心模型的特性 12
M/M/1系统的稳定性能分析 12
对Little公式的注记 15
M/M/c系统的稳态性能分析 17
生灭过程稳态解的表达方式 19
2.3 生灭过程模型 19
生灭过程 19
损失制M/M/c/K排队网络模型 21
服务速率依赖状态的M/M/1模型 22
2.4 Jackson排队网络模型 23
Jackson开环排队网络的特性 24
Jackson开环排队网络的稳态分析 24
Jackson闭环排队网络 31
Buzen算法 32
2.5 排队网络的推广模型 33
BCMP排队网络 33
Kelly排队网络 34
2.6 基于排队网络模型的实用分析方法 40
操作分析法的变量和假设 40
操作分析法分析系统的性能 42
平均值分析法 44
2.7 Fork-Join排队网络 45
Fork-Join排队网络的背景和描述 46
两个并联服务台Fork-Join系统 47
M个并联服务台Fork-Join系统 52
具有集中缓冲器的批输入Fork-Join系统 55
2.8 排队网络方法在柔性制造系统研究中的应用 59
2.9 小结和评述 60
第3章 性能层次的建模与分析方法之二：摄动分析方法(PA) 62
3.1 PA方法的基本模型和研究思路 62
基本模型 62
研究思路 63
三个核心步骤 63
3.2 PA方法的基本分析步骤之一：样本轨道的描述 64
服务中心的三种工况状态 64
事件和变量 64
系统状态方程 65
由随机变量均值的摄动导出随机变量样本值的摄动 66
3.3 PA方法的基本分析步骤之二：摄动的产生 66
摄动样本轨道的构造 67
寻找NP和PP上的相应事件 68
3.4 PA方法的基本分析步骤之三：摄动的传播 69
无穷小摄动下摄动的传播 69
有限摄动下摄动的传播 71
3.5 PA方法的基本分析步骤之四：估计系统性能对参数的灵敏度 72
排队网络输出率对平均服务时间的灵敏度 72
服务中心输出率对系统内顾客数的灵敏度 74
服务中心输出率对路径概率的灵敏度 74
顾客在服务中心的平均逗留时间对平均服务时间的灵敏度 75
3.6 PA方法估计的无偏性和强一致性问题 76
服务中心平均队长对服务中心平均服务时间的灵敏度 76
PA基本方法存在的问题 77
PA方法用于灵敏度估计的无偏性条件 78
PA方法用于灵敏度估计的强一致性条件 80
3.7 PA方法的推广形式 81
推广摄动分析 82
平滑摄动分析 84
3.8 一类Fork-Join排队网络的摄动分析 85
一类无限缓冲Fork-Join排队系统的摄动分析 85
一类有限缓冲树型Fork-Join排队系统的摄动分析 90
3.9 PA方法分析制造系统优化问题的应用举例 91
3.10 小结和评述 95
第4章 代数层次的建模与分析方法：极大代数方法 96
4.1 离散事件动态系统的代数层次模型 96
缓冲区容量无限的串行生产线 96
状态、输入和输出 97
系统的代数层次模型 98
4.2 离散事件动态系统在极大代数下的线性模型 99
极大代数及其基本运算 100
串行生产线的开环线性模型 101
串行生产线的闭环线性模型 103
4.3 离散事件动态系统在极大代数上的特征结构 105
有向图分析法 105
系统矩阵的不可简约性 108
不可简约矩阵在极大代数上的特征值 109
可简约矩阵在极大代数上的特征值 112
不可简约矩阵在极大代数上的特征向量 114
可简约矩阵在极大代数上的特征向量 115
矩阵的周期性 115
4.4 离散事件动态系统的稳定性和周期性稳态 116
系统输出的演化过程 117
系统输出演化过程的稳定性 119
不可简约系统的周期性稳态 119
可简约系统的周期性稳态 122
不可简约系统的周期性稳态特征参量配置 124
4.5 离散事件动态系统周期性稳态特征参量的配置 124
4.6 离散事件动态系统直接进入均匀周期性稳态的途径 125
均匀周期性稳态 125
直接进入均匀周期性稳态的途径 ：不可简约系统情况 126
直接进入均匀周期性稳态的途径：可简约系统情况 129
4.7 小结和评述 132
第5章 代数层次的建模与分析方法：对极大代数方法的进一步讨论 134
5.1 离散事件动态系统周期性稳态性能的摄动分析 134
问题提法和基本约定 134
基本极大代数运算下矩阵摄动量的估计 135
系统参数摄动下稳态参量λ改变值的估计 138
5.2 离散事件动态系统周期性稳态性能的鲁棒性 140
基本概念 140
单个参数摄动情形的鲁棒性分析 141
多个参数同时增性摄动情形的鲁棒性分析 144
5.3 离散事件动态系统特征结构参数的辨识 146
问题的提法 146
对系统特征值的估计 147
利用稳态数据辨识系统的特征值和特征向量 151
5.4 离散事件动态系统的能控性及其判据 153
系统模型 153
系统状态的能控性 154
系统状态能控性的判据 155
系统能控性在状态反馈作用下的不变性 158
不完全能控系统的结构分解 159
5.5 离散事件动态系统的集结与输入-输出等价 161
集结与输入-输出特价 162
极大代数上线性系统状态空间模型的集结与等价 162
几点讨论 167
5.6 有限缓冲容量串行生产线的建模和周期性稳态 168
有限缓冲容量的串行生产线 168
有限缓冲容量串行生产线的状态空间模型 168
有限缓冲容量串行生产线的闭环动态模型和稳态周期过程 174
阻塞现象和无阻塞性定义 175
5.7 有限缓冲容量串行生产线的阻塞问题 175
单批次加工过程的无阻塞条件 176
多批次加工过程的无阻塞条件 180
系统结构无阻塞性及其判别准则 184
缓冲区容量的最小配置 187
加工参数区间摄动下的系统无阻塞性 188
5.8 离散事件动态系统事件序列性的鲁棒性 189
基本概念 190
事件序列性鲁棒性的判据：仿射线性函数情形 191
事件序列性鲁棒性的判据：多项式函数情形 194
极大代数上的Z变换 199
5.9 离散事件动态系统的传递函数 199
极大代数上的传递函数 200
图方法确定系统传递函数矩阵 202
广义分式及其约简 205
5.10 基于传递函数的离散事件动态系统的稳态分析和控制 210
有理式的周期性 210
系统在周期输入下的稳态分析 213
稳态反馈控制 216
5.11 装配生产线的建模 221
装配生产线 221
装配生产线的变量和参量 221
装配生产线的状态空间模型 223
5.12 小结和评述 228
第6章 逻辑层次的建模与分析方法之一：佩特里网方法 230
6.1 佩特里网及其规则 230
佩特里网 230
佩特里网图 231
变迁的发射规则 232
6.2 佩特里网的动态运行过程 233
分析动态运行过程的算法 233
运行过程分析举例 234
6.3 佩特里网的基本性质 235
可达性 235
活性 236
有界性和安全性 236
死锁 237
冲突 237
6.4 佩特里网可达性的分析方法 237
可达树分析方法 238
矩阵方程分析方法 241
6.5 佩特里网可达性分析的计算复杂性问题 244
算法与问题复杂性 244
佩特里网可达性分析的计算复杂性问题 247
6.6 佩特里网的活性分析 247
状态机和子网 247
子网间的连接 248
模块 249
环 250
网的锁定性质 251
6.7 佩特里网的控制问题 252
受控佩特里网和受控标识图 252
受控标识图的禁止/允许状态规范控制：谓词方法 253
受控标识图的控制策略的活性 257
受控标识图的禁止/允许状态规范控制：代数方法 258
6.8 佩特里网的综合 268
制造系统的佩特里网模型 269
并联互斥连接 271
串联互斥连接 273
6.9 扩展佩特里网 277
赋时佩特里网 277
随机佩特里网 277
加色佩特里网 278
高级佩特里网 278
6.10 佩特里网方法在离散制造系统研究中的应用 279
6.11 小结和评述 281
第7章 逻辑层次的建模与分析方法之二：自动机/形式语言方法 282
7.1 自动机和形式语言 282
形式语言 282
语言的运算 284
正规集 287
自动机 289
7.2 事件反馈监控 292
受控自动机 292
监控器 293
闭环离散事件过程 294
闭环离散事件过程F/Gc产生的语言 294
7.3 系统能控性和监控器的存在性 296
能控性 296
系统能控性和监控器 299
7.4 基本监控综合问题和最大能控子语言 301
基本监控综合问题 302
目标语言和最大能控子语言的一些属性 302
语言集合上的右不变等价关系和正规语言判据 303
最大能控语言的生成 305
Ω算子的算法 306
最大能控语言的另一种算法 309
7.5 能观测性和观测约束下的监控器 309
语言的能观测性 310
观测约束下的监控器 310
观测约束下的基本监控问题 312
可识别性 313
7.6 分散监控和分散化监控 314
分散监控 315
分散化监控 319
7.7 状态反馈监控 321
谓词及其运算 321
状态反馈 323
对状态反馈的闭环系统的分析 324
两类反馈监控问题的关系 330
7.8 其他形式的监控问题 331
允许阻塞的监控问题 331
赋时自动机的监控问题 333
符号串空间中自动机的可达树 335
7.9 事件反馈监控问题基于可达树的分析 335
监控作用的实现 338
7.10 小结与评述 339
第8章 离散制造系统的调度问题 341
8.1 生产调度问题的分类和描述 341
开环车间型和闭环车间型调度问题 341
Job-Shop调度问题和Flow-Shop调度问题 342
调度问题的基本假定 342
调度问题的描述：图论形式 343
调度问题的描述：代数形式 344
调度问题性能指标的典型形式 345
调度问题的可行解 345
调度问题类型的简明表示法 348
调度问题的求解方法 348
8.2 正规性能指标的活动调度和等价关系 348
基于正规性能指标的活动调度 348
性能指标的等价性 351
8.3 单机调度 352
问题和基本假定 352
n/1//F最优调度问题 353
n/1//Lmax最优调度问题 353
n/1//nT最优调度问题 354
双机调度问题的Johnson算法 357
8.4 双机调度 357
多机Flow-Shop最优调度的属性 358
Johnson算法调度解的最优性 359
Johnson算法对一类三机Flow-Shop调度问题的应用 360
8.5 分支定界法 361
分支定界法的基本思路 362
分支定界法求解转换Flow-Shop调度问题 363
分支定界法求解Job-Shpo调度问题 364
8.6 求解Flow-Shop排序问题的搜索型启发式算法 366
属于NP完全问题的调度问题示例 366
启发式算法之三：BG(Bonney-Gundry)方法 367
启发式算法之二：Gupta方法 367
启发式算法之一：Palmer方法 367
启发式算法之四 ：CDS(Campleu-Dudek-Smith)方法 368
启发式算法之五：Dannenbring方法 368
8.7 规则型调度方法和典型调度规则 368
规则型调度方法的基本思路 368
静态调度问题和动态调度问题 369
调度规则及分类 369
典型的调度规则 370
8.8 邻域搜索方法 374
邻域搜索的基本思路 375
邻域结构 375
SA算法的寻优机制 376
8.9 模拟退火优化方法 376
SA算法的描述 377
基于非齐次马氏链模型的SA算法的收敛性分析 378
一个典型的Job-Shop调度问题 379
8.10 遗传算法的基本原理和基本框架 380
遗传算法的基本机理 380
遗传算法的基本框架 381
Job-Shop调度问题的基因链编码方式 383
GA的特点 384
对GA的改进 385
一类GA/SA混合算法 386
8.11 GA/SA混合算法 386
GA/SA混合算法的提出 386
GA/SA混合算法的收敛性 388
8.12 图灵机和语言的NP完全问题 392
图灵机 393
语言的NP完全性 394
8.13 调度问题的计算复杂性 394
3-划分问题 395
调度问题计算复杂性的一些基本结论 395
8.14 制造系统的非传统调度问题 396
E/T调度问题 397
问题的背景 397
批处理机调度问题 402
多处理机任务调度问题 405
考虑机器不可用情况的调度问题 406
8.15 小结和评述 407
第9章 混合动态系统 409
9.1 概述 409
HDS的工程背景 409
HDS的特点和分类 410
HDS的建模和分析方法 412
HDS的一个工程实例 413
问题和模型 414
9.2 切换型 混合动态系统 414
稳定性 415
能控性 417
镇定问题 419
几点注记 420
9.3 水箱型 混合动态系统 421
问题和模型 421
稳定性 423
稳定调度策略 424
性能分析和估计 430
9.4 集中控制型 混合动态系统 433
几点注记 433
问题和模型 434
稳定性 435
稳定调度策略 435
EFS策略的鲁棒性 442
几点注记 444
9.5 旅行商型 混合动态系统 444
问题和模型 445
旅行商型HDS的时间最短调度问题 446
一个例子 451
递阶型HDS 453
9.6 递阶型和交互型混合动态系统 453
时间划分产生的递阶型HDS 454
空间划分产生的递阶型HDS 456
一个例子 461
对递阶型HDS的注记 462
交互型HDS 462
9.7 混合佩特里网 464
混合佩特里网的形式化定义 464
混合佩特里网的运行规则 465
混合佩特里网的关联矩阵 467
混合佩特里网的不变量 468
混合佩特里网的状态 469
混合佩特里网的结构性质 471
几点注记 471
9.8 SIGNAL语言 471
SIGNAL语言模型 472
信号与时钟 472
SIGNAL语言的基本语句 473
SIGNAL语言中语句的编码 475
SIGNAL语言对HDS的建模举例 477
几点注记 479
9.9 小结和评述 479
参考文献 481