排序問題是一類重要的組合最優(yōu)化問題，是運(yùn)籌學(xué)研究的一個(gè)非�；钴S的分支，廣泛地應(yīng)用于管理科學(xué)、計(jì)算機(jī)科學(xué)、工程技術(shù)、制造業(yè)、運(yùn)輸業(yè)、分派銷售和其他服務(wù)行業(yè)。它研究如何在有限的資源限制和約束下對(duì)于給定的一些“工件”或“活動(dòng)”從時(shí)間上和順序上進(jìn)行合理的安排和分配，以使某目標(biāo)（如生產(chǎn)效率、資源利用率和合格率等）達(dá)到或接近最優(yōu)。

　　動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支。動(dòng)態(tài)規(guī)劃方法是研究多階段決策過程最優(yōu)化的一種數(shù)學(xué)方法，通過把多階段過程劃分為一系列相互聯(lián)系的單階段過程，再逐個(gè)階段求解，從而使整個(gè)過程達(dá)到目標(biāo)最優(yōu)。動(dòng)態(tài)規(guī)劃方法在工程技術(shù)、經(jīng)濟(jì)管理、工業(yè)生產(chǎn)和軍事等方面都有著廣泛的應(yīng)用。動(dòng)態(tài)規(guī)劃方法沒有統(tǒng)一的標(biāo)準(zhǔn)模型，沒有統(tǒng)一的處理格式。它必須依據(jù)問題本身的特性，利用靈活的數(shù)學(xué)技巧來處理。在排序與調(diào)度領(lǐng)域中，存在大量NP難的多階段決策問題，用動(dòng)態(tài)規(guī)劃方法求得精確最優(yōu)解是非常有效的方法之一。

　　現(xiàn)有討論排序問題的書籍中，絕大多數(shù)是從問題的模型角度進(jìn)行分類研究，很少?gòu)慕鉀Q問題的方法角度展開討論。本書系統(tǒng)地介紹了排序理論和動(dòng)態(tài)規(guī)劃理論方面的研究成果，討論動(dòng)態(tài)規(guī)劃方法在解決排序與調(diào)度問題中的應(yīng)用。從眾多用動(dòng)態(tài)規(guī)劃方法求解的排序問題中選取有代表性的部分問題，進(jìn)行總結(jié)和分析。讀者通過本書可以對(duì)動(dòng)態(tài)規(guī)劃在排序問題中的應(yīng)用有全面的了解和認(rèn)識(shí)。

　　本書共分7章。第1章介紹動(dòng)態(tài)規(guī)劃的基礎(chǔ)知識(shí)；第2章介紹排序問題的基本理論；第3章討論經(jīng)典的單機(jī)排序問題的動(dòng)態(tài)規(guī)劃求解方法；第4章研究若干新型排序問題的動(dòng)態(tài)規(guī)劃解法，其中包括分批排序問題、成組加工排序問題、可控排序問題以及可拒絕排序問題；第5章討論如何用動(dòng)態(tài)規(guī)劃方法解決供應(yīng)鏈排序問題；第6章研究雙代理排序問題的動(dòng)態(tài)規(guī)劃解法；第7章討論利用動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)完全多項(xiàng)式時(shí)間近似方案（FPTAS）的應(yīng)用成果。其中第1章、第5章由沈陽(yáng)師范大學(xué)柏孟卓撰寫，第6章、第7章由重慶師范大學(xué)張新功撰寫，第2章至第4章由柏孟卓、張新功共同撰寫。

　　本書內(nèi)容既包含了用動(dòng)態(tài)規(guī)劃方法求解排序問題的經(jīng)典研究成果，也包含了作者多年來研究工作積累的成果。本書從最初的構(gòu)想到最終的成稿，一直得到唐國(guó)春教授的大力推動(dòng)與悉心指導(dǎo)。此外，我們還得到了清華大學(xué)出版社編輯的細(xì)心幫助。在此向唐國(guó)春教授和清華大學(xué)出版社表示深深的感謝！

　　本書可以作為運(yùn)籌與管理、計(jì)算機(jī)和自動(dòng)化等相關(guān)學(xué)科的教師和學(xué)生的參考書。由于作者時(shí)間有限，書中或會(huì)有不妥之處，懇請(qǐng)讀者批評(píng)指正！

第1章 動(dòng)態(tài)規(guī)劃基礎(chǔ)
1.1 多階段決策過程
1.2 動(dòng)態(tài)規(guī)劃的基本思想
1.3 動(dòng)態(tài)規(guī)劃基礎(chǔ)知識(shí)
1.3.1 基本概念和常用術(shù)語
1.3.2 動(dòng)態(tài)規(guī)劃基本模型及基本原理
1.3.3 可用動(dòng)態(tài)規(guī)劃求解的問題的特征
1.4 動(dòng)態(tài)規(guī)劃在組合優(yōu)化問題中的應(yīng)用
1.4.1 資源分配問題
1.4.2 背包問題
1.4.3 設(shè)備更新問題
第2章 排序問題基本理論
2.1 排序的記號(hào)與術(shù)語
2.2 算法和復(fù)雜性
2.3 局部置換法
2.3.1 加權(quán)完工時(shí)間問題
2.3.2 最大延遲問題
2.3.3 帶有到達(dá)時(shí)間的情形
2.3.4 總誤工時(shí)間問題
第3章 單機(jī)排序問題
3.1 單臺(tái)機(jī)器排序問題1□（數(shù)理化公式）
3.1.1 問題1□（數(shù)理化公式）的動(dòng)態(tài)規(guī)劃算法
3.1.2 問題1□（數(shù)理化公式）的動(dòng)態(tài)規(guī)劃算法
3.1.3 工件有先后約束的單臺(tái)機(jī)器排序問題1□（數(shù)理化公式）
3.1.4 加工允許中斷的單臺(tái)機(jī)器排序問題1□（數(shù)理化公式）
3.2 單臺(tái)機(jī)器排序問題1||fmax
3.2.1 單臺(tái)機(jī)器排序問題1||fmax的逆向解法
3.2.2 單臺(tái)機(jī)器排序問題1||fmx的順向解法
3.2.3 工件有先后約束的單臺(tái)機(jī)器排序問題1|prec|fmax
第4章 幾類新型排序問題
4.1 分批排序問題
4.1.1 加權(quán)總完工時(shí)間問題1|p-batch, b=∞□（數(shù)理化公式）
4.1.2 最大延遲問題1|p-batch, b=∞|Lmax
4.2 成組排序問題
4.2.1 必須滿足成組技術(shù)要求的成組誤工問題1□（數(shù)理化公式）
4.2.2 不受成組技術(shù)限制的成組排序問題
4.3 加工時(shí)間可控的排序問題
4.3.1 誤エエ件數(shù)問題1□（數(shù)理化公式）
4.3.2 最大延遲問題1□（數(shù)理化公式）
4.3.3 最大完工時(shí)間問題1□（數(shù)理化公式）
4.4 工件可拒絕排序問題
4.4.1 工件可拒絕的分批排序問題1□（數(shù)理化公式）
4.4.2 帶權(quán)總完工時(shí)間排序問題1□（數(shù)理化公式）
第5章 供應(yīng)鏈排序問題
5.1 供應(yīng)鏈排序問題簡(jiǎn)介及數(shù)學(xué)模型
5.2 樹狀供應(yīng)鏈排序問題
5.2.1 總流程問題1□（數(shù)理化公式）
5.2.2 輔助問題的構(gòu)造及其求解
5.3 網(wǎng)狀供應(yīng)鏈排序問題
5.3.1 供應(yīng)商問題
5.3.2 制造商問題
第6章 雙代理排序問題
6.1 單臺(tái)機(jī)器的雙代理問題1□（數(shù)理化公式）
6.1.1 問題的復(fù)雜性
6.1.2 問題的動(dòng)態(tài)規(guī)劃算法
6.2 自由作業(yè)的遞推刻畫
6.2.1 問題□（數(shù)理化公式）
6.2.2 最小化最大完工時(shí)間加權(quán)和問題□（數(shù)理化公式）
第7章 動(dòng)態(tài)規(guī)劃刻畫FPTAS
7.1 序關(guān)系和問題描述
7.2 ex-benevolent問題
7.2.1 兩臺(tái)同型機(jī)下的時(shí)間表長(zhǎng)問題P2||Cmax
7.2.2 兩臺(tái)同型機(jī)下的總權(quán)完工時(shí)間問題□（數(shù)理化公式）
7.2.3 具有時(shí)間相關(guān)加工時(shí)間的兩臺(tái)同型機(jī)的總完工時(shí)間問題□（數(shù)理化公式）
7.3 cc-benevolent問題
7.3.1 單機(jī)下加權(quán)誤工工件個(gè)數(shù)問題1□（數(shù)理化公式）
7.3.2 單機(jī)下退化效應(yīng)相關(guān)的時(shí)間表長(zhǎng)問題1|Deteriorate|Cmax
7.3.3 單機(jī)下誤工損失問題1□（數(shù)理化公式）
7.3.4 單機(jī)下加權(quán)誤工損失問題1□（數(shù)理化公式）
7.4 本章小結(jié)
參考文獻(xiàn)
附錄 英漢排序與調(diào)度詞匯
索引