排序問題自20世紀50年代提出以后，得到了專家學者們的廣泛關注，通過幾十年的發(fā)展，成果豐富。排序理論逐步形成并得到快速發(fā)展，成為運籌學中一個獨立的研究領域，理論日趨完善。
排序理論最初研究的對象主要是制造業(yè)，因此術語都與制造業(yè)有關，例如工件機器加工時間等，我們往往將早期研究的排序模型稱為經典排序。經過幾十年的發(fā)展，研究對象擴展到各類非制造業(yè)，其應用領域越來越廣泛，從而歸納出許多有別于經典排序的新型排序模型，包括分批排序、可控排序、工件可拒絕排序、資源受限排序、在線排序等。由于排序理論的應用領域越來越廣泛，使其所研究的問題及其類型呈現(xiàn)出多樣性，并且復雜程度更高，從而進一步推動了排序理論的發(fā)展。
我們現(xiàn)在所要研究的各類排序問題往往是NP困難的，對于一個NP困難排序問題要設計一個有效的近似算法并不容易。數(shù)學規(guī)劃松弛方法是一種有效的方法，可應用于設計求解排序問題的近似算法。數(shù)學規(guī)劃松弛方法包括線性規(guī)劃松弛、凸二次規(guī)劃松弛、半定規(guī)劃松弛以及拉格朗日松弛等。能否通過數(shù)學規(guī)劃松弛設計出性能良好的近似算法，關鍵是決策變量的選取，并將所討論的排序問題歸納成一個數(shù)學規(guī)劃，最后再通過這一數(shù)學規(guī)劃的解得到相對應排序問題的解。
本書介紹了排序問題的數(shù)學規(guī)劃松弛方法，所討論的排序模型除了經典排序模型，重點包括工件可拒絕排序模型和工件加工時間可控排序模型。本書內容分為三大部分。第一部分（第1章）介紹排序論的基本概念，包括排序問題的三參數(shù)表示。第二部分（第2章、第3章、第4章）介紹線性規(guī)劃松弛方法，其中第2章討論經典排序，所討論的排序問題包括工件具有前后約束關系、工件具有就緒時間、工件加工可中斷等。第3章討論工件可拒絕排序，首先介紹了工件可拒絕排序的基本概念，接著討論了若干工件可拒絕排序問題。第4章討論工件加工時間可控排序，首先介紹了工件加工時間可控排序的基本概念，接著討論了若干工件加工時間可控排序問題。第三部分（第5章、第6章、第7章）介紹凸二次規(guī)劃松弛方法，其中第5章討論經典排序，第6章討論工件可拒絕排序，第7章討論工件加工時間可控排序。
本書是《排序與調度叢書》中的一本，在撰寫過程中得到了《排序與調度叢書》編輯委員會的大力支持，編輯委員會的各位同仁為本書所提出的寶貴意見，提升了本書的質量。上海交通大學出版社以及本書責任編輯汪儷老師為本書的順利出版付出了辛勤勞動。在此，作者對于上述各位表示衷心的感謝。本書的出版同時得到了作者所在單位上海第二工業(yè)大學的鼎力支持，同事劉麗麗教授非常仔細地審閱了書稿，并提出了修改建議，在此對于學校的支持和同事的幫助表示深深的謝意。
由于作者學術水平有限，本書難免存在不足之處或錯誤，敬請讀者批評指正。

張峰
上海第二工業(yè)大學
2020年12月