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

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