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

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