求解作業(yè)車間調(diào)度問(wèn)題的高效算法研究
定 價(jià)：20 元
叢書名：博士論叢
- 作者：尹愛(ài)華 著
- 出版時(shí)間：2010/2/1
- ISBN：9787312026690
- 出 版 社：中國(guó)科學(xué)技術(shù)大學(xué)出版社
- 中圖法分類：F406.2
- 頁(yè)碼：130
- 紙張：膠版紙
- 版次：1
- 開本：16開
本書專門討論了作業(yè)車間調(diào)度問(wèn)題，提出了改進(jìn)的轉(zhuǎn)換瓶頸算法、一個(gè)混合式鄰域搜索算法、擴(kuò)展HLS的算法、基礎(chǔ)的擬物擬人算法、帶禁忌規(guī)則的擬物擬人算法等一系列求解該問(wèn)題的高效算法。
本書適合計(jì)算機(jī)專業(yè)本科高年級(jí)學(xué)生、研究生閱讀，可供計(jì)算性與算法復(fù)雜性的研究人員閱讀。
從有資源分配的時(shí)代開始，人類就開始接觸到調(diào)度問(wèn)題。從人們?cè)趹?zhàn)爭(zhēng)中對(duì)軍隊(duì)的調(diào)度到從事農(nóng)耕、娛樂(lè)、運(yùn)輸、制作中對(duì)人力和物資的分配與調(diào)度，人類很早就感受到了在有限資源條件下完成指定的任務(wù)需要調(diào)度。然而，一個(gè)很有意思的現(xiàn)象是，雖然調(diào)度問(wèn)題在軍事、生活等方面的活動(dòng)中普遍存在，但是嚴(yán)格地研究這個(gè)問(wèn)題卻是在數(shù)千年之后。提出調(diào)度問(wèn)題的數(shù)學(xué)模型的出現(xiàn)是很晚的，1954年，S.M.Johnson提出了求解流水車間兩臺(tái)機(jī)器下調(diào)度問(wèn)題最優(yōu)解的法則，這是第一個(gè)求解調(diào)度問(wèn)題的數(shù)學(xué)模型，Ramser于1959年首次提出交通調(diào)度問(wèn)題。這既不同于歐拉研究哥尼斯堡七橋問(wèn)題從而導(dǎo)致圖論的創(chuàng)立，又不同于17世紀(jì)人們從研究投骰子賭博現(xiàn)象而提出的概率論。筆者很早就注意到了這一現(xiàn)象，并做了一些調(diào)查研究，但是到目前為止都沒(méi)有找到解釋這個(gè)現(xiàn)象的文獻(xiàn)�；谌藗兡壳皩�(duì)各種調(diào)度問(wèn)題的研究成果，筆者猜想人們數(shù)千年以來(lái)都是采用增加資源和人為強(qiáng)制介入的辦法（某種強(qiáng)權(quán)干預(yù)資源分配）來(lái)解決現(xiàn)實(shí)中的調(diào)度問(wèn)題，從而誤導(dǎo)人們認(rèn)為“該問(wèn)題不是數(shù)學(xué)問(wèn)題”。當(dāng)然，也可能因?yàn)檫@個(gè)問(wèn)題過(guò)于復(fù)雜，不顯得“有趣”。
1999年起，筆者開始攻讀博士學(xué)位，師從國(guó)際知名的NP難問(wèn)題研究專家黃文奇教授。我因此有機(jī)會(huì)更加深入地了解了調(diào)度問(wèn)題，并選擇了作業(yè)車間調(diào)度問(wèn)題作為我博士論文的研究?jī)?nèi)容。眾所周知，NP難問(wèn)題是理論計(jì)算機(jī)科學(xué)領(lǐng)域的重要研究對(duì)象，作業(yè)車間調(diào)度問(wèn)題不僅是NP難的，還被認(rèn)為是最難的組合最優(yōu)化問(wèn)題之一。人們已經(jīng)知道，為解決工業(yè)生產(chǎn)、物流、經(jīng)濟(jì)管理和網(wǎng)絡(luò)通信等諸多方面的問(wèn)題，可以借助于求解作業(yè)車間調(diào)度問(wèn)題的結(jié)果。所以，高效、快速地求解作業(yè)車間調(diào)度問(wèn)題，既有重要的理論意義，又有重大的應(yīng)用價(jià)值。
人們?yōu)榱饲蠼庾鳂I(yè)車間調(diào)度問(wèn)題提出了許多方法。在黃文奇教授的悉心指導(dǎo)下，我認(rèn)真總結(jié)了前人的研究結(jié)論，提出了一套求解該問(wèn)題的方法并完成我的博士論文。特別要指出的是，用我的方法找到了一個(gè)大規(guī)模實(shí)例（50個(gè)作業(yè)，20臺(tái)機(jī)器，1000個(gè)工序）到目前為止的最好解。博士畢業(yè)后，我進(jìn)一步鉆研求解這個(gè)問(wèn)題的高效率算法的設(shè)計(jì)，提出了擬物擬人方法。擬物擬人方法同原有的方法都不同，雖然這方面的研究剛剛起步，但是可以預(yù)見(jiàn)到它有很好的發(fā)展前景，本書將這個(gè)研究的相關(guān)結(jié)果收錄進(jìn)來(lái)了。
……
前言
第1章 緒論
1.1 組合最優(yōu)化問(wèn)題
1.2 實(shí)際難解性和NP完全問(wèn)題
1.3 啟發(fā)式方法
1.3.1 基本策略
1.3.2 性能評(píng)價(jià)
1.3.3 算法類型
1.3.4 擬物擬人算法
1.4 作業(yè)車間調(diào)度問(wèn)題及其算法概論
1.5 本書研究?jī)?nèi)容及工作安排
1.6 本章 小結(jié)
第2章 改進(jìn)的轉(zhuǎn)換瓶頸算法
2.1 問(wèn)題的描述及其形式化
2.1.1 問(wèn)題的描述
2.1.2 問(wèn)題的形式化
2.2 轉(zhuǎn)換瓶頸算法
2.2.1 問(wèn)題的一種直觀表示和一個(gè)定理
2.2.2 轉(zhuǎn)換瓶頸算法
2.3 定理2.2的證明
2.3.1 一個(gè)關(guān)于單機(jī)調(diào)度的引理
2.3.2 定理2.2的證明
2.4 改進(jìn)的轉(zhuǎn)換瓶頸算法ISB
2.4.1 帶擾動(dòng)的Schrage算法
2.4.2 關(guān)于擾動(dòng)系數(shù)
2.5 部分回溯算法
2.6 對(duì)典型實(shí)例的計(jì)算結(jié)果
2.7 本章 小結(jié)
第3章 一個(gè)混合式鄰域搜索算法
3.1 Tabu搜索與作業(yè)車間調(diào)度問(wèn)題
3.1.1 Tabu搜索
3.1.2 作業(yè)車間調(diào)度問(wèn)題中的Tabu搜索
3.2 鄰域搜索算法HLS
3.2.1 鄰域結(jié)構(gòu)
3.2.2 初始解和禁忌表
3.2.3 一個(gè)基于擬人策略的吸引準(zhǔn)則
3.2.4 集中和分散策略
3.2.5 新的鄰域搜索算法
3.3 對(duì)實(shí)例的計(jì)算結(jié)果
3.4 本章 小結(jié)
第4章 擴(kuò)展HLS的算法
4.1 常用的鄰域結(jié)構(gòu)
4.2 新鄰域結(jié)構(gòu)的基礎(chǔ)
4.2.1 兩種新的移動(dòng)
4.2.2 關(guān)于新移動(dòng)的兩個(gè)定理
4.3 新的混合算法TSISB
4.3.1 新鄰域的定義
4.3.2 新的禁忌表
4.4 含隨機(jī)策略的鄰域搜索算法SHLS
4.5 對(duì)實(shí)例的計(jì)算結(jié)果
4.6 關(guān)于最長(zhǎng)路徑長(zhǎng)度的計(jì)算
4.7 本章 小結(jié)
第5章 各種啟發(fā)式算法的比較
5.1 基于鄰域搜索算法之比較
5.2 與典型啟發(fā)式算法的比較和分析
5.3 本章 小結(jié)
第6章 基礎(chǔ)的擬物擬人算法
6.1 作業(yè)車間調(diào)度問(wèn)題的物理模型
6.1.1 作業(yè)車間調(diào)度問(wèn)題的彈性物理模型
6.1.2 彈性力和位移量
6.2 擬物算法的基礎(chǔ)
6.3 初始算法
6.4 擬物擬人算法
6.4.1 反向擠壓策略
6.4.2 分組計(jì)算策略
6.4.3 隨機(jī)策略
6.5 實(shí)驗(yàn)結(jié)果
6.6 本章 小結(jié)
第7章 帶禁忌規(guī)則的擬物擬人算法
7.1 禁忌搜索算法概述
7.2 帶禁忌規(guī)則的擬物擬人算法
7.2.1 初始解和鄰域結(jié)構(gòu)
7.2.2 禁忌表
7.2.3 搜索和跳坑策略
7.3 算法的實(shí)驗(yàn)結(jié)果
7.4 本章 小結(jié)
第8章 總結(jié)及展望
8.1 主要工作總結(jié)及創(chuàng)新
8.2 未來(lái)的研究方向
8.3 本章 小結(jié)
參考文獻(xiàn)
�。�1）不能保證算法一定得到最優(yōu)解；
（2）性能不穩(wěn)定。啟發(fā)式算法對(duì)同一個(gè)問(wèn)題的不同實(shí)例的計(jì)算會(huì)產(chǎn)生不同的效果。有些實(shí)例所得的解的優(yōu)度很高，而另一些則相反。在工程應(yīng)用中，啟發(fā)式算法的這種不穩(wěn)定性使得計(jì)算結(jié)果不可信；
（3）啟發(fā)式算法的優(yōu)劣依賴于具體問(wèn)題以及設(shè)計(jì)者的經(jīng)驗(yàn)、技術(shù)等，這一點(diǎn)很難總結(jié)成規(guī)律，同時(shí)使不同算法之間難于比較。
雖說(shuō)啟發(fā)式方法有諸多優(yōu)點(diǎn)，但是它本身固有的一個(gè)很嚴(yán)重的缺陷--無(wú)法保證得到最優(yōu)解，使得對(duì)啟發(fā)式算法的評(píng)價(jià)顯得尤為重要。一個(gè)好的啟發(fā)式算法可以使其解盡可能地接近最優(yōu)解，同時(shí)保持很好的穩(wěn)定性。評(píng)價(jià)啟發(fā)式算法的性能有很多不同的方法，主要是對(duì)算法的復(fù)雜性和它的計(jì)算效能進(jìn)行分析。下面就簡(jiǎn)要地介紹幾種常用的方法。
1.最壞情形分析
最壞情形分析考慮計(jì)算復(fù)雜性和所得解的效果兩個(gè)方面。最壞情形計(jì)算復(fù)雜性分析關(guān)注算法基本運(yùn)算總次數(shù)同實(shí)例的計(jì)算機(jī)二進(jìn)制輸入長(zhǎng)度之間的關(guān)系，從最壞實(shí)例--規(guī)模相同基本計(jì)算步數(shù)最多的實(shí)例的角度來(lái)研究、分析算法的計(jì)算時(shí)間復(fù)雜性。
2.概率分析
由于最壞情形分析是以最壞的實(shí)例來(lái)評(píng)價(jià)一個(gè)算法或者它所得到的解，這樣難免因?yàn)橐粋�(gè)實(shí)例導(dǎo)致對(duì)某個(gè)算法或它所求得解的優(yōu)劣的評(píng)價(jià)完全顛倒。人們認(rèn)識(shí)到應(yīng)該從總體上而非極端的實(shí)例上來(lái)評(píng)價(jià)算法，概率分析方法正是著眼于此。這個(gè)方法是從理論上考慮的，針對(duì)一個(gè)算法，我們可以從它的計(jì)算時(shí)間復(fù)雜性和計(jì)算所得解的效果兩個(gè)方面進(jìn)行概率分析。無(wú)論作哪一個(gè)方面的分析，都假設(shè)實(shí)例的數(shù)據(jù)服從某一種概率分布。在這些數(shù)據(jù)的一個(gè)已知概率分布的假設(shè)條件下，研究算法或其解的某種平均效果。
概率方法在評(píng)價(jià)算法方面的一個(gè)成功、典型的應(yīng)用是對(duì)線性規(guī)劃單純形法的評(píng)價(jià)。概率發(fā)現(xiàn)方法是一種理論分析方法，它需要對(duì)問(wèn)題本身有很深入的理解，并且掌握概率模型的建立和概率理論。
最壞情形分析和概率分析方法有一個(gè)共同的特點(diǎn)：用理論的方法分析算法所得到的解同最優(yōu)解之間的誤差界，要求分析者具有堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，而且分析過(guò)程很繁復(fù)。
3.大規(guī)模計(jì)算分析
前兩種方法都是理論分析方法，要求有多的數(shù)學(xué)工具和繁復(fù)的推演，而且分析過(guò)程很復(fù)雜。
……
書單推薦
