本书系统地介绍了排序理论和动态规划理论方面的研究成果，讨论动态规划方法在解决排序与调度问题中的应用。

　　排序问题是一类重要的组合最优化问题，是运筹学研究的一个非常活跃的分支，广泛地应用于管理科学、计算机科学、工程技术、制造业、运输业、分派销售和其他服务行业。它研究如何在有限的资源限制和约束下对于给定的一些“工件”或“活动”从时间上和顺序上进行合理的安排和分配，以使某目标（如生产效率、资源利用率和合格率等）达到或接近最优。

　　动态规划是运筹学的一个重要分支。动态规划方法是研究多阶段决策过程最优化的一种数学方法，通过把多阶段过程划分为一系列相互联系的单阶段过程，再逐个阶段求解，从而使整个过程达到目标最优。动态规划方法在工程技术、经济管理、工业生产和军事等方面都有着广泛的应用。动态规划方法没有统一的标准模型，没有统一的处理格式。它必须依据问题本身的特性，利用灵活的数学技巧来处理。在排序与调度领域中，存在大量NP难的多阶段决策问题，用动态规划方法求得精确最优解是非常有效的方法之一。

　　现有讨论排序问题的书籍中，绝大多数是从问题的模型角度进行分类研究，很少从解决问题的方法角度展开讨论。本书系统地介绍了排序理论和动态规划理论方面的研究成果，讨论动态规划方法在解决排序与调度问题中的应用。从众多用动态规划方法求解的排序问题中选取有代表性的部分问题，进行总结和分析。读者通过本书可以对动态规划在排序问题中的应用有全面的了解和认识。

　　本书共分7章。第1章介绍动态规划的基础知识；第2章介绍排序问题的基本理论；第3章讨论经典的单机排序问题的动态规划求解方法；第4章研究若干新型排序问题的动态规划解法，其中包括分批排序问题、成组加工排序问题、可控排序问题以及可拒绝排序问题；第5章讨论如何用动态规划方法解决供应链排序问题；第6章研究双代理排序问题的动态规划解法；第7章讨论利用动态规划算法设计完全多项式时间近似方案（FPTAS）的应用成果。其中第1章、第5章由沈阳师范大学柏孟卓撰写，第6章、第7章由重庆师范大学张新功撰写，第2章至第4章由柏孟卓、张新功共同撰写。

　　本书内容既包含了用动态规划方法求解排序问题的经典研究成果，也包含了作者多年来研究工作积累的成果。本书从最初的构想到最终的成稿，一直得到唐国春教授的大力推动与悉心指导。此外，我们还得到了清华大学出版社编辑的细心帮助。在此向唐国春教授和清华大学出版社表示深深的感谢！

　　本书可以作为运筹与管理、计算机和自动化等相关学科的教师和学生的参考书。由于作者时间有限，书中或会有不妥之处，恳请读者批评指正！

第1章动态规划基础

1.1多阶段决策过程

1.2动态规划的基本思想

1.3动态规划基础知识

1.3.1基本概念和常用术语

1.3.2动态规划基本模型及基本原理

1.3.3可用动态规划求解的问题的特征

1.4动态规划在组合优化问题中的应用

1.4.1资源分配问题

1.4.2背包问题

1.4.3设备更新问题

第2章排序问题基本理论

2.1排序的记号与术语

2.2算法和复杂性

2.3局部置换法

2.3.1加权完工时间问题

2.3.2最大延迟问题

2.3.3带有到达时间的情形

2.3.4总误工时间问题 

第3章单机排序问题

3.1单台机器排序问题1‖∑fj(Cj)

3.1.1问题1‖∑Tj的动态规划算法

3.1.2问题1|dj=d|∑wjTj的动态规划算法

3.1.3工件有先后约束的单台机器排序问题1|prec|∑fj

3.1.4加工允许中断的单台机器排序问题1|pmtn,rj|∑wjUj

3.2单台机器排序问题1‖fmax

3.2.1单台机器排序问题1‖fmax的逆向解法

3.2.2单台机器排序问题1‖fmax的顺向解法

3.2.3工件有先后约束的单台机器排序问题1|prec|fmax

第4章几类新型排序问题

4.1分批排序问题

4.1.1加权总完工时间问题1|p-batch,b=∞|∑wjCj

4.1.2最大延迟问题1|p-batch,b=∞|Lmax

4.2成组排序问题

4.2.1必须满足成组技术要求的成组误工问题1|sf,GT|∑Ui

4.2.2不受成组技术限制的成组排序问题

4.3加工时间可控的排序问题

4.3.1误工工件数问题1|B，dis_cpt|∑Uj+∑ni=1∑hk=1ckIk(xi)

4.3.2最大延迟问题1|B，dis_cpt|Lmax+∑ni=1∑hk=1ckIk(xi)

4.3.3最大完工时间问题1|B，dis_cpt|Cmax+∑ni=1∑hk=1ckIk(xi)

4.4工件可拒绝排序问题

4.4.1工件可拒绝的分批排序问题1rej，B∑j∈ej+Cmax

4.4.2带权总完工时间排序问题1rej∑j∈ej+∑j∈SwjCj

第5章供应链排序问题

5.1供应链排序问题简介及数学模型

5.2树状供应链排序问题

5.2.1总流程问题1→G，Pm‖∑Fj+∑Dgyg

5.2.2辅助问题的构造及其求解

5.3网状供应链排序问题

5.3.1供应商问题

5.3.2制造商问题

第6章双代理排序问题

6.1单台机器的双代理问题1‖ε∑wjVAj(σ):∑CBj(σ)

6.1.1问题的复杂性

6.1.2问题的动态规划算法

6.2自由作业的递推刻画

6.2.1问题O2‖CAmax(σ):CBmax(σ)

6.2.2最小化最大完工时间加权和问题O2‖CAmax+αCBmax

第7章动态规划刻画FPTAS

7.1序关系和问题描述

7.2ex-benevolent问题

7.2.1两台同型机下的时间表长问题P2‖Cmax

7.2.2两台同型机下的总权完工时间问题P2‖∑wjCj

7.2.3具有时间相关加工时间的两台同型机的总完工时间问题

P2time-dep|∑Cj

7.3cc-benevolent 问题

7.3.1单机下加权误工工件个数问题1|batch|∑wjUj

7.3.2单机下退化效应相关的时间表长问题1|Deteriorate|Cmax

7.3.3单机下误工损失问题1‖∑Vj

7.3.4单机下加权误工损失问题1‖∑wjVj

7.4本章小结

参考文献

附录英汉排序与调度词汇

索引

国家出版基金、十三五国家重点图书出版规划项目《排序与调度丛书》。

柏孟卓,博士，沈阳师范大学数学与系统科学学院教师，中国运筹学会排序分会理事。主要研究领域是组合**化理论、生产排序理论。主要研究排序问题的动态规划算法及全多项式时间近似方案。