前言

排序问题自20世纪50年代提出以后，得到了专家学者们的广泛关注，通过几十年的发展，成果丰富。排序理论逐步形成并得到快速发展，成为运筹学中一个独立的研究领域，理论日趋完善。

排序理论最初研究的对象主要是制造业，因此术语都与制造业有关，例如“工件”“机器”“加工时间”等，我们往往将早期研究的排序模型称为经典排序。经过几十年的发展，研究对象扩展到各类非制造业，其应用领域越来越广泛，从而归纳出许多有别于经典排序的新型排序模型，包括分批排序、可控排序、工件可拒绝排序、资源受限排序、在线排序等。由于排序理论的应用领域越来越广泛，使其所研究的问题及其类型呈现出多样性，并且复杂程度更高，从而进一步推动了排序理论的发展。

我们现在所要研究的各类排序问题往往是NP困难的，对于一个NP困难排序问题要设计一个有效的近似算法并不容易。数学规划松弛方法是一种有效的方法，可应用于设计求解排序问题的近似算法。数学规划松弛方法包括线性规划松弛、凸二次规划松弛、半定规划松弛以及拉格朗日松弛等。能否通过数学规划松弛设计出性能良好的近似算法，关键是决策变量的选取，并将所讨论的排序问题归纳成一个数学规划，最后再通过这一数学规划的解得到相对应排序问题的解。

本书介绍了排序问题的数学规划松弛方法，所讨论的排序模型除了经典排序模型，重点包括工件可拒绝排序模型和工件加工时间可控排序模型。本书内容分为三大部分。第一部分（第1章）介绍排序论的基本概念，包括排序问题的三参数表示。第二部分（第2章、第3章、第4章）介绍线性规划松弛方法，其中第2章讨论经典排序，所讨论的排序问题包括工件具有前后约束关系、工件具有就绪时间、工件加工可中断等。第3章讨论工件可拒绝排序，首先介绍了工件可拒绝排序的基本概念，接着讨论了若干工件可拒绝排序问题。第4章讨论工件加工时间可控排序，首先介绍了工件加工时间可控排序的基本概念，接着讨论了若干工件加工时间可控排序问题。第三部分（第5章、第6章、第7章）介绍凸二次规划松弛方法，其中第5章讨论经典排序，第6章讨论工件可拒绝排序，第7章讨论工件加工时间可控排序。

本书是《排序与调度丛书》中的一本，在撰写过程中得到了《排序与调度丛书》编辑委员会的大力支持，编辑委员会的各位同仁为本书所提出的宝贵意见，提升了本书的质量。上海交通大学出版社以及本书责任编辑汪俪老师为本书的顺利出版付出了辛勤劳动。在此，作者对于上述各位表示衷心的感谢。本书的出版同时得到了作者所在单位上海第二工业大学的鼎力支持，同事刘丽丽教授非常仔细地审阅了书稿，并提出了修改建议，在此对于学校的支持和同事的帮助表示深深的谢意。

由于作者学术水平有限，本书难免存在不足之处或错误，敬请读者批评指正。

张峰

上海第二工业大学

2020年12月