排序是一类重要的组合最优化问题,它广泛应用于管理科学、计算机科学和工程技术等众多领域。本书主要讨论确定性排序和随机排序的基本理论和算法。书中所用到的有关运筹学的知识在附录中给出,所以只需具有高等数学的知识就可阅读本书,每章后附有习题,以便加深理解书中的内容。
本书可作为应用数学、运筹学与控制论、管理科学与工程、系统工程和计算机软件及理论等专业研究生和本科生高年级排序(调度)课程的教材,也可供相关领域的科技人员和管理人员阅读。
样章试读
目录
- 第一章 绪论
1·1排序问题
1·2排序问题的求解
习题一
参考文献
第二章 单机排序问题
2·1加权总完工时间问题
2·2最大延误问题
2·3误工任务数问题
2·4总误工问题
2·5成组加工问题
习题二
参考文献
第三章 平行机排序问题
3·1不可中断时间表长问题
3·2可中断时间表长问题
3·3总完工时间问题
3·4最大延误问题
习题三
参考文献
第四章 车间作业排序问题
4·1同顺序作业问题
4·2自由顺序作业问题
4·3异顺序作业问题
习题四
参考文献
第五章 柔性流水作业排序问题
5·1时间表长问题
5·2总完工时间问题
习题五
参考文献
第六章 资源约束排序问题
6·1离散资源约束排序问题
6·2加工时间依赖资源的排序问题
习题六
参考文献
第七章 排序的近似算法
7·1分派规则
7·2局部搜索算法
7·3过滤束搜索算法
习题七
参考文献
第八章 随机排序引言
8·1随机排序
8·2单调完成率分布类
8·3随机序
8·4优先策略
习题八
参考文献
第九章 单机随机排序问题
9·1任意分布的加工时间问题
9·2具有似然比随机序的加工时间问题
9·3具有特殊分布的加工时间问题
习题九
参考文献
第十章 平行机随机排序问题
10·1不可中断问题
10·2可中断问题
习题十
参考文献
第十一章 车间作业随机排序问题
11·1缓存区无限的随机流水作业问题
11·2缓存区有限的随机流水作业问题
11·3开放作业随机排序问题
11·4异顺序作业随机排序问题
习题十一
参考文献
第十二章 随机排序中的随机过程
12·1Gittins指标
12·2马尔科夫决策过程模型
12·3更新过程模型
12·4随机JIT排序问题
12·5随机排序的随机规划方法
习题十二
参考文献
附录
附录A 图与网络
附录B 线性规划和整数线性规划
附录C 算法复杂性理论
附录D 分枝定界法
附录E 动态规划方法
附录F 近似算法
附录G 确定性排序问题的复杂性
附录H 概率论基础
附录I 凸函数
附录J 具有最优优先策略的随机排序问题
附录K 几个常用的随机过程
参考文献
汉英词汇对照