排序问题的数学规划松弛方法

　　对于NP困难的排序问题，研究其近似算法既是排序理论重要组成部分，具有深刻的理论意义，又是推进排序理论应用的关键，具有广泛的实际应用价值。数学规划松弛方法是一种可用于设计组合最优化问题近似算法的重要方法，本书讨论排序问题的数学规划松弛方法，介绍应用数学规划松弛方法设计求解NP困难排序问题近似算法的基本原理与方法，以及该领域的相关研究成果。本书可作为应用数学、运筹学、计算机科学、管理科学和工业工程等专业教师和研究生开展排序理论及相关学科领域研究的参考书。

暂缺《排序问题的数学规划松弛方法》作者简介

第1章排序论概述1
  1.1排序问题1
  1.2排序问题的三参数表示2
  1.3本书内容简介4
第2章线性规划松弛方法： 经典排序9
  2.1问题1|prec|∑wjCj9
  2.2问题1|rj， prec|∑wjCj16
  2.3问题1|rj， prec， pmtn|∑wjCj19
  2.4问题1|rj|∑wjCj21
  2.5问题1|rj， pmtn|∑wjCj43
  2.6问题P|rj|∑wjCj47
  2.7问题P|rj， prec， pmtn|∑wjCj54
  2.8问题P|prec，  delays dij|∑wjCj56
  2.9问题R|rij|∑wjCj60
第3章线性规划松弛方法：  工件可拒绝排序68
  3.1工件可拒绝排序的基本概念68
  3.2问题1|rej|∑j∈S－ej＋∑j∈SwjCj70
  3.3问题1|rej， rj|∑j∈S－ej＋∑j∈SwjCj75
  3.4问题R|rej， pmtn|∑j∈S－ej＋Cmax81
第4章线性规划松弛方法： 工件加工时间可控排序89
  4.1工件加工时间可控排序的基本概念89
  4.2问题1|cpt， prec|∑cjtj＋∑wjCj91
  4.3问题P|dis_cpt， pmtn|∑cj＋Cmax101
第5章凸二次规划松弛方法： 经典排序112
  5.1问题R||∑wjCj112
  5.2问题R|rij|∑wjCj122
第6章凸二次规划松弛方法： 工件可拒绝排序130
  6.1问题1|rej|∑j∈S－ej＋∑j∈SwjCj130
  6.2问题1|rej， rj|∑j∈S－ej＋∑j∈SwjCj139
第7章凸二次规划松弛方法：  工件加工时间可控排序146
  7.1问题R|cpt|∑∑cijtij＋∑wjCj146
  7.2问题R|cpt， rij|∑∑cijtij＋∑wjCj154
  7.3问题1|dis_cpt|∑∑cjiIji（t）＋∑wjCj167
附录英汉排序与调度词汇174
参考文献182
索引185